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

文章发布较早，内容可能过时，阅读注意甄别。

# 题目

给你一个整数数组 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" 的代价为 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：

输入：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"

提示：

cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000

# 思路

完全背包

# 解法

class Solution {
public String largestNumber(int[] cost, int target) {
        int[][] dp = new int[target+1][10];
        dp[0][9] = 1;
        for (int i = 0; i < 9; i++) {
            if (cost[i] > target) continue;
            for (int j = cost[i]; j <= target; j++) {
                if (dp[j - cost[i]][9] == 0) continue;
                if (f(dp[j - cost[i]], dp[j], i)) {
                    dp[j] = Arrays.copyOf(dp[j - cost[i]], 10);
                    dp[j][9]++;
                    dp[j][i]++;
                }
            }
        }
        if (dp[target][9] <= 0) return "0";
        StringBuilder sb = new StringBuilder();
        for (int i = 8; i >= 0; i--) {
            if (dp[target][i] == 0) continue;
            while (dp[target][i] > 0) {
                dp[target][i]--;
                sb.append(i+1);
            }
        }
        return sb.toString();
    }
    private boolean f(int[] dp1, int[] dp2, int t) {
        if (dp1[9] + 1 != dp2[9]) return dp1[9] + 1 > dp2[9];
        for (int i = 8; i >= 0; i--) {
            if (dp1[i] + (t == i ? 1 : 0) > dp2[i]) return true;
            if (dp1[i] + (t == i ? 1 : 0) < dp2[i]) return false;
        }
        return false;
    }
}

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
27
28
29
30
31
32
33
34
35
36

# 总结

分析出几种情况，然后分别对各个情况实现

#Java