leetcode 1449. 数位成本和为目标值的最大数字-一一网

这是我参与更文挑战的第12天
，活动详情查看更文挑战

题目

给你一个整数数组 cost 和一个整数 target 。请你返回满足如下规则可以得到的最大整数：

给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
总成本必须恰好等于 target 。
添加的数位中没有数字 0 。
由于答案可能会很大，请你以字符串形式返回。

如果按照上述要求无法得到任何整数，请你返回 “0” 。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出：”7772″
解释：添加数位 ‘7’ 的成本为 2 ，添加数位 ‘2’ 的成本为 3 。所以 “7772” 的代价为 23+ 31 = 9 。 “977” 也是满足要求的数字，但 “7772” 是较大的数字。

 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5
复制代码

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出：”85″
解释：添加数位 ‘8’ 的成本是 7 ，添加数位 ‘5’ 的成本是 5 。”85″ 的成本为 7 + 5 = 12 。

示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出：”0″
解释：总成本是 target 的条件下，无法生成任何整数。

示例 4：

输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出：”32211″

解题思路

数组定义

dp[i][j]代表选择前i个数位，成本为j时，组成最大整数的长度
log[i][j]记录当前dp[i][j]的情况是由dp[i][log[i][j]]转移而来的

状态转移

j-cost[i]<0

当前总成本太小了，不足以取第i位，因此

dp[i+1][j]=dp[i][j];

j-cost[i]>=0

成本足够了，可以选择是否取当前数位。判断取当前数位或者不取的情况下，哪种情况下产生的数位更多，选择产生数位最多的一种情况。

                  if (dp[i][j]>dp[i+1][j-cost[i]]+1)
                    {
                        dp[i+1][j]=dp[i][j];
                        log[i+1][j]=j;
                    }else {
                        dp[i+1][j]=dp[i+1][j-cost[i]]+1;
                        log[i+1][j]=j-cost[i];
                    }
复制代码

代码

class Solution {
    public String largestNumber(int[] cost, int target) {

        int[][] dp = new int[10][target + 1];
        int[][] log = new int[10][target + 1];
        for (int i=0;i<10;i++)
        {
            Arrays.fill(dp[i],Integer.MIN_VALUE);
        }
        dp[0][0]=0;
        for (int i=0;i<9;i++)
        {
            for (int j = 0; j <= target; j++) {
                if(j-cost[i]<0){
                           dp[i+1][j]=dp[i][j];
                        log[i+1][j]=j;

                }else{
                    if (dp[i][j]>dp[i+1][j-cost[i]]+1)
                    {
                        dp[i+1][j]=dp[i][j];
                        log[i+1][j]=j;
                    }else {
                        dp[i+1][j]=dp[i+1][j-cost[i]]+1;
                        log[i+1][j]=j-cost[i];
                    }
                }
            }
        }
        
        StringBuilder res = new StringBuilder();
        int i=9,j=target;
        if(dp[i][j]<0)  return "0";
        while (i>0){
            if(log[i][j]==j)
            {
                i--;
            }else{
                j=log[i][j];
                res.append(i);
            }

        }
        return res.toString();

    }
}
复制代码