LeetCode 1449: Form Largest Integer With Digits That Add Up To Target ·

基本資料
#

難易度: hard 第一次嘗試：2026-08-19 來源：Day 46 learning note

學習脈絡
#

這篇是從 learning note 裡該 LeetCode 題目的段落重新整理出來的版本。我保留當天筆記中的修正點、比較點、容易犯錯的地方，並移除同一天其他非 LeetCode 主題，避免文章內容混題。

筆記中提到的相關提醒
#

explain LC 1449 as unbounded cost DP plus greedy reconstruction

當天筆記摘錄
#

Problem 2 - LC 1449 Form Largest Integer With Digits That Add Up To Target
#

Pattern: unbounded knapsack optimization plus greedy reconstruction.

Why This Fits
#

Each digit 1..9 has:

a cost
unlimited reuse

The objective is not just:

can I hit target?

It is:

form the numerically largest integer whose total cost is target

That means:

maximize digit count first
among equal-length answers, reconstruct the lexicographically largest digit sequence

Core State / Invariant
#

dp[t] = maximum number of digits we can build with total cost t

Use a very negative sentinel for unreachable states.

Base Case
#

dp[0] = 0

Reason:

cost 0 can form a number with 0 digits

Transition
#

For a digit with cost c:

dp[t] = max(dp[t], dp[t - c] + 1)

Iterate target cost forward because digit reuse is allowed.

Reconstruction
#

After DP, rebuild from digit 9 down to 1.

Greedy rule:

take digit d if its cost fits and dp[remaining] == dp[remaining - cost[d]] + 1

This preserves max length while making the leftmost digits as large as possible.

Complexity
#

Time: O(9 * target)
Space: O(target)

Common Mistakes
#

solving only feasibility and forgetting reconstruction
optimizing digit value directly instead of digit count first
using backward loop and accidentally turning it into 0/1
not handling unreachable target cleanly

Strong Spoken Explanation
#

This is an unbounded knapsack on digit cost. I first use DP to maximize how many digits can be formed for each total cost, because any number with more digits is always numerically larger than a shorter valid number. So dp[t] stores the maximum digit count for cost t, with dp[0] = 0 and unreachable states set to negative infinity. Since digits can be reused, the transition is unbounded: dp[t] = max(dp[t], dp[t - cost] + 1). After I know the maximum digit count for the target, I reconstruct greedily from digit 9 down to 1, taking a digit whenever it preserves the optimal count. That gives the lexicographically largest number among all max-length answers.

正確解法
#

上面的筆記保留了推理脈絡和當天需要修正的點。下面是我會提交的版本。

from typing import List, Optional

class Solution:
    def largestNumber(self, cost: List[int], target: int) -> str:
        dp: List[Optional[str]] = [None] * (target + 1)
        dp[0] = ''

        def better(a: str, b: Optional[str]) -> str:
            if b is None or len(a) > len(b) or (len(a) == len(b) and a > b):
                return a
            return b

        for t in range(1, target + 1):
            for digit in range(1, 10):
                c = cost[digit - 1]
                if t >= c and dp[t - c] is not None:
                    dp[t] = better(dp[t - c] + str(digit), dp[t])

        return dp[target] if dp[target] is not None else '0'