题目描述

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

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

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

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

样例

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

 数字     成本
  1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5

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

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

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

限制

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

算法

(贪心，动态规划) $O(9 \cdot target)$

1. 我们需要拼出尽可能多的位数。参考完全背包模型，每个数字表示一个物品，其代价为 cost 数组，价值为 1。
2. 设 $f(i, j)$ 表示考虑了前 $i$ 个数字，成本为 $j$ 时的所能得到的最大位数。
3. 初始时，$f(0, 0) = 0$，其余为负无穷。
4. 转移时，对于一个数字，按照完全背包的模型转移 $f(i, j) = \max(f(i, j), f(i - 1, j - cost[i]) + 1)$。
5. 最终的最大位数为 $f(9, target)$。完全背包可以优化为一维的状态表示。如果最大位数小于 0，则直接返回 "0"。
6. 接下来需要找具体方案，最优答案一定是大的数字尽可能地放在前边。我们从最大的数字开始往回拼，得到最优答案。

时间复杂度

• 状态数为 $O(9 \cdot target)$，每次转移需要常数时间，故时间复杂度为 $O(9 \cdot target)$。

空间复杂度

• 优化后的空间复杂度为 $O(target)$，另外答案也需要 $O(target)$ 的空间。

C++ 代码

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<int> f(target + 1, INT_MIN);

        f[0] = 0;
        for (int i = 0; i < 9; i++)
            for (int j = cost[i]; j <= target; j++)
                f[j] = max(f[j], f[j - cost[i]] + 1);

        if (f[target] < 0)
            return "0";

        string ans;
        for (int i = 8, j = target; i >= 0; i--) {
            while (j >= cost[i] && f[j] == f[j - cost[i]] + 1) {
                ans += to_string(i + 1);
                j -= cost[i];
            }
        }

        return ans;
    }
};