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

Categories:

题目描述
思路分析
1. 解法一：DP 长度 + 贪心重建（推荐）
相似题目

题目描述

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

思路分析

解法一：DP 长度 + 贪心重建（推荐）

核心思路：

dp[t] 记录凑出总成本 t 的最大数字长度。

转移：dp[t] = max(dp[t], dp[t - cost[d]] + 1)。

最后从 9 到 1 贪心重建，保证字典序最大。

复杂度分析：

时间复杂度：O(9 * target)。

空间复杂度：O(target)。

class Solution {
    public String largestNumber(int[] cost, int target) {
        int[] dp = new int[target + 1];
        for (int i = 1; i <= target; i++) {
            dp[i] = -1_000_000;
        }
        dp[0] = 0;

        for (int t = 1; t <= target; t++) {
            for (int d = 1; d <= 9; d++) {
                int c = cost[d - 1];
                if (t >= c) {
                    dp[t] = Math.max(dp[t], dp[t - c] + 1);
                }
            }
        }

        if (dp[target] < 0) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        int t = target;
        for (int d = 9; d >= 1; d--) {
            int c = cost[d - 1];
            while (t >= c && dp[t] == dp[t - c] + 1) {
                sb.append(d);
                t -= c;
            }
        }
        return sb.toString();
    }
}

func largestNumber(cost []int, target int) string {
    dp := make([]int, target+1)
    for i := 1; i <= target; i++ {
        dp[i] = -1 << 30
    }
    dp[0] = 0

    for t := 1; t <= target; t++ {
        for d := 1; d <= 9; d++ {
            c := cost[d-1]
            if t >= c {
                if dp[t-c]+1 > dp[t] {
                    dp[t] = dp[t-c] + 1
                }
            }
        }
    }

    if dp[target] < 0 {
        return "0"
    }

    res := make([]byte, 0)
    t := target
    for d := 9; d >= 1; d-- {
        c := cost[d-1]
        for t >= c && dp[t] == dp[t-c]+1 {
            res = append(res, byte('0'+d))
            t -= c
        }
    }
    return string(res)
}

相似题目

题目	难度	考察点
322. 零钱兑换	中等	DP
518. 零钱兑换 II	中等	DP
198. 打家劫舍	中等	DP
279. 完全平方数	中等	DP
1049. 最后一块石头的重量 II	中等	DP

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/19343868