Hard

题目描述

给定一个整数数组 cost 和一个整数 target，在满足以下规则的条件下，返回你可以绘制的最大整数：

  • 绘制数字 (i + 1) 的成本由 cost[i] 给出（下标从 0 开始）
  • 使用的总成本必须等于 target
  • 整数不能包含数字 0

由于答案可能很大，请以字符串形式返回。如果在给定条件下无法绘制任何整数，则返回 “0”。

示例 1：

输入：cost = [4,3,2,5,6,7,2,5,5], target = 9
输出："7772"
解释：绘制数字 '7' 的成本是 2，数字 '2' 的成本是 3。那么 cost("7772") = 2*3+ 3*1 = 9。你也可以绘制 "977"，但 "7772" 是更大的数字。

示例 2：

输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：绘制数字 '8' 的成本是 7，数字 '5' 的成本是 5。那么 cost("85") = 7 + 5 = 12。

示例 3：

输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：不可能绘制任何总成本等于 target 的整数。

约束条件：

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

解题思路

这道题需要分两步解决：

第一步：动态规划求最大位数 使用 DP 确定能否达到目标成本以及最大位数。定义 dp[i] 为成本为 i 时能构成的最大位数。状态转移方程为：

dp[i] = max(dp[i], dp[i - cost[j]] + 1)  // 对所有数字 j+1

第二步：贪心构造最大数字 在确定了最大位数后，需要构造字典序最大的数字。关键思路是：

  • 从最大的数字9开始尝试
  • 对于每个数字，检查使用它后剩余成本是否还能构成足够的位数
  • 优先选择较大的数字，这样可以保证字典序最大

例如，如果目标成本是9，可以构成3位数，那么优先选择成本最小的数字来填充更多位数，但在前面的位置优先选择更大的数字。

时间复杂度主要来自两部分：DP 计算 O(target × 9) 和构造结果 O(最大位数)。

推荐解法： 动态规划 + 贪心构造，这是最直接有效的方法。

代码实现

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<int> dp(target + 1, -1);
        dp[0] = 0;
        
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < 9; j++) {
                if (i >= cost[j] && dp[i - cost[j]] != -1) {
                    dp[i] = max(dp[i], dp[i - cost[j]] + 1);
                }
            }
        }
        
        if (dp[target] == -1) return "0";
        
        string result = "";
        int remain = target;
        
        for (int digits = dp[target]; digits > 0; digits--) {
            for (int digit = 9; digit >= 1; digit--) {
                int c = cost[digit - 1];
                if (remain >= c && dp[remain - c] == digits - 1) {
                    result += char('0' + digit);
                    remain -= c;
                    break;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp = [-1] * (target + 1)
        dp[0] = 0
        
        for i in range(1, target + 1):
            for j in range(9):
                if i >= cost[j] and dp[i - cost[j]] != -1:
                    dp[i] = max(dp[i], dp[i - cost[j]] + 1)
        
        if dp[target] == -1:
            return "0"
        
        result = ""
        remain = target
        
        for digits in range(dp[target], 0, -1):
            for digit in range(9, 0, -1):
                c = cost[digit - 1]
                if remain >= c and dp[remain - c] == digits - 1:
                    result += str(digit)
                    remain -= c
                    break
        
        return result

public class Solution {
    public string LargestNumber(int[] cost, int target) {
        int[] dp = new int[target + 1];
        Array.Fill(dp, -1);
        dp[0] = 0;
        
        for (int i = 1; i <= target; i++) {
            for (int j = 0; j < 9; j++) {
                if (i >= cost[j] && dp[i - cost[j]] != -1) {
                    dp[i] = Math.Max(dp[i], dp[i - cost[j]] + 1);
                }
            }
        }
        
        if (dp[target] == -1) return "0";
        
        StringBuilder result = new StringBuilder();
        int remain = target;
        
        for (int digits = dp[target]; digits > 0; digits--) {
            for (int digit = 9; digit >= 1; digit--) {
                int c = cost[digit - 1];
                if (remain >= c && dp[remain - c] == digits - 1) {
                    result.Append(digit);
                    remain -= c;
                    break;
                }
            }
        }
        
        return result.ToString();
    }
}

var largestNumber = function(cost, target) {
    const dp = new Array(target + 1).fill(-1);
    dp[0] = 0;
    
    for (let i = 1; i <= target; i++) {
        for (let j = 0; j < 9; j++) {
            if (i >= cost[j] && dp[i - cost[j]] !== -1) {
                dp[i] = Math.max(dp[i], dp[i - cost[j]] + 1);
            }
        }
    }
    
    if (dp[target]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(target × 9 + 最大位数 × 9) = O(target)
空间复杂度O(target)