1449. 数位成本和为目标值的最大数字

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

  • 给当前结果添加一个数位（i + 1）的成本为 cost[i] （cost 数组下标从 0 开始）。
  • 总成本必须恰好等于 target 。
  • 添加的数位中没有数字 0 。

由于答案可能会很大，请你以字符串形式返回。

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

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：添加数位 '7' 的成本为 2 ，添加数位 '2' 的成本为 3 。所以 "7772" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字，但 "7772" 是较大的数字。
 数字   成本
  1  -> 4
  2  -> 3
  3  -> 2
  4  -> 5
  5  -> 6
  6  -> 7
  7  -> 2
  8  -> 5
  9  -> 5

示例 2：

1
2
3
输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。

示例 3：

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

示例 4：

1
2
输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"

提示：

  • cost.length == 9
  • 1 <= cost[i] <= 5000
  • 1 <= target <= 5000
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public String largestNumber(int[] cost, int target) {
        int n = cost.length;
        // 通过完全背包获得最大整数的长度，再通过回溯倒推得到目标整数字符串
        // f[i][j]: 考虑前i个整数，总成本恰好等于j，可以获得的数位长度
        int f[][] = new int[n+1][target+1];
        Arrays.fill(f[0], Integer.MIN_VALUE);
        f[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= target; j++) {
                f[i+1][j] = f[i][j];
                if (j-cost[i] >= 0)
                    f[i+1][j] = Math.max(f[i+1][j], f[i+1][j-cost[i]] + 1);
            }
        }
        if (f[n][target] < 0) return "0";
        String res = "";
        for (int i = n, j = target; i > 0; i--) {  // 回溯倒推，优先考虑使用后面的数字
            while (j-cost[i-1] >= 0 && f[i][j] == f[i][j-cost[i-1]] + 1) {
                res += (char)(i+48);
                j -= cost[i-1];
            }
        }
        return res;
    }
}