题目分析

本题难度较大，题目的信息绕人，虽然能够想到动态规划，但是很难想到最优的状态转移方程。

动态规划

本题的亮点是dp[i][j]不是最终求得的结果，而是最终解的位数，因为最终解一定是位数最多的解。通过另一个状态转移方程from[i][j]记录位数的变化，逆推出选择的数字。

先来分析dp[i][j]，dp[i][j]表示前i个数字，满足成本为j时，产生的最大位数。而且数字可以重复使用，满足完全背包的性质。当成本小于第i个数字的成本时，dp[i][j] = dp[i - 1][j]，当成本大于等于第i个数字的成本时dp[i][j] = max(dp[i - 1][j], dp[i][j - cost[i]] + 1)

$$\begin{cases} dp[i][j] = max(dp[i - 1][j], dp[i][j - cost[i]] + 1) & j \ge cost[i] \ dp[i - 1][j] & else \end{cases}$$

然后分析from[i][j]，from[i][j]表示前i个数字，满足成本为j时，上一个状态的成本。假设没有使用第i个数字，那么上一个状态就是dp[i - 1][j]，因此成本为j，则from[i][j] = j，如果使用第i个数字，那么上一个状态就是dp[i][j - cost[i]]，因此成本为j - cost[i]。要注意的是，如果从在遍历中发现dp[i][j - cost[i]] + 1 = dp[i - 1][j]。说明在之前的遍历中，已经找到了一种方法使得产生的位数最大，这时from[i][j]是否需要更新呢？是使用之前的数字呢还是使用当前的数字呢？因为我们对数字从1搜索到9，因此当前的数字更大，应该使用当前的数字，当dp[i][j - cost[i]] + 1 = dp[i - 1][j]时，from[i][j] = j - cost[i]。

$$\begin{cases} from[i][j] = j & j < cost[i] && dp[i][j - cost[i]] + 1 < dp[i - 1][j] \ j -cost[i] & else \end{cases}$$

在完成dp和from的正向遍历后，逆序确定所选择的数字，如果j == from[i][j]，说明dp[i][j]是从dp[i - 1][j]转移而来的，没用选择第i个数字，–i。否则选择了第i个数字，然后将当前成本j变为上一个状态的成本from[i][j]。

算法的时间复杂度为$O(10 \times target)$，空间复杂度为$O(20 \times target)$

下面是Java语言的题解

class Solution {
    public String largestNumber(int[] cost, int target) {
        int[][] dp = new int[10][target + 1];
        int[][] from = new int[10][target + 1];
        for (int i = 0; i < 10; ++i) {
            for (int j = 0; j <= target; ++j) {
                dp[i][j] = 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] || dp[i + 1][j - cost[i]] + 1 < dp[i][j]) {
                    dp[i + 1][j] = dp[i][j];
                    from[i + 1][j] = j;
                } else {
                    dp[i + 1][j] = dp[i + 1][j - cost[i]] + 1;
                    from[i + 1][j] = j - cost[i];
                }
            }
        }
        if (dp[9][target] <= 0) { return "0"; }
        StringBuilder res = new StringBuilder();
        int i = 9;
        int j = target;
        while (i > 0) {
            if (j == from[i][j]) {
                --i;
            } else {
                res.append(i);
                j = from[i][j];
            }
        }
        return res.toString();
    }
}

下面是Kotlin语言的题解

class Solution {
    fun largestNumber(cost: IntArray, target: Int): String {
        val dp = Array(10) {IntArray(target + 1)}
        val from = Array(10) {IntArray(target + 1)}
        for (i in 0..9) {
            for (j in 0..target) {
                dp[i][j] = Int.MIN_VALUE
            }
        }
        dp[0][0] = 0
        for (i in 0..8) {
            for (j in 0..target) {
                if (j < cost[i] || dp[i + 1][j - cost[i]] + 1 < dp[i][j]) {
                    dp[i + 1][j] = dp[i][j]
                    from[i + 1][j] = j
                } else {
                    dp[i + 1][j] = dp[i + 1][j - cost[i]] + 1
                    from[i + 1][j] = j - cost[i]
                }
            }
        }
        if (dp[9][target] <= 0) { return "0" }
        val res = StringBuilder()
        var i = 9
        var j = target
        while (i >= 0) {
            if (j == from[i][j]) { --i }
            else {
                res.append(i)
                j = from[i][j]
            }
        }
        return res.toString()
    }
}

优化动态规划

因为这个问题是一个完全背包问题，第i层的状态仅和第i层和第i - 1层有关，因此可以对空间复杂度进行压缩。

dp[i]表示成本为i时，产生的最大位数。
$$dp[i] = max(dp[i], dp[i - cost[i]])$$

遍历dp以后，可以根据dp[i - cost[i]] + 1和dp[i]的关系来判断是否选择了第i个数字，如果选择了第i个数字，那么dp[i - cost[i]] + 1的值等于dp[i]的值

算法的时间复杂度为$O(10 \times target)$，空间复杂度为$O(target)$

下面是Java语言的题解

class Solution {
    public String largestNumber(int[] cost, int target) {
        int[] dp = new int[target + 1];
        for (int i = 0; i <= target; ++i) {
                dp[i] = Integer.MIN_VALUE;
        }
        dp[0] = 0;
        for (int x : cost) {
            for (int i = x; i <= target; ++i) {
                dp[i] = Math.max(dp[i], dp[i - x] + 1);
            }
        }
        if (dp[target] <= 0) { return "0"; }
        StringBuilder res = new StringBuilder();
        int i = 8;
        int j = target;
        while (i >= 0) {
            if (j >= cost[i] && dp[j - cost[i]] + 1 == dp[j]) {
                res.append(i + 1);
                j -= cost[i];
            } else {
                --i;
            }
        }
        return res.toString();
    }
}

下面是Kotlin语言的题解

class Solution {
    fun largestNumber(cost: IntArray, target: Int): String {
        val dp = IntArray(target + 1)
        for (i in 0..target) {
            dp[i] = Int.MIN_VALUE
        }
        dp[0] = 0
        for (x in cost) {
            for (i in x..target) {
                dp[i] = Math.max(dp[i], dp[i - x] + 1)
            }
        }
        if (dp[target] <= 0) { return "0" }
        val res = StringBuilder()
        var i = 8
        var j = target
        while (i >= 0) {
            if (j >= cost[i] && dp[j - cost[i]] + 1 == dp[j]) {
                res.append(i + 1)
                j -= cost[i]
            } else {
                --i
            }
        }
        return res.toString()
    }
}

刷题总结

这个题目看了答案之后发现并不是很困难，但是在看答案之前觉得非常复杂，在一般的背包问题中，数组最后一维的值就是问题的最优解，而这个题目最后一维的值只是一个中间步骤，这个题目非常好，开阔了我们的思维，需要多多练习这类题目，对自己的提升才能更快。