Form Largest Integer With Digits That Add up to Target: DP Greedy Reconstruction

You are given an array cost of length 9, where cost[i] is the cost of painting digit i + 1. You are also given an integer target. Return the largest number you can paint such that the total cost of its digits sums to exactly target. Each digit can be used as many times as you want. If it is impossible to paint any number that costs exactly target, return "0".

This is LeetCode 1449: Form Largest Integer With Digits That Add up to Target. It combines unbounded knapsack DP with a greedy reconstruction step, making it one of the best problems for learning how to extract an optimal solution from a DP table.

Why this problem matters

At first glance, this looks like a standard coin-change variant. You have 9 "coins" (the digits), each with a cost, and you want to reach a target sum. But there is a twist: you are not minimizing the number of coins. You are maximizing the number of digits, and then among all maximum-length results, you want the lexicographically largest one. This two-layer optimization is what makes the problem interesting.

The pattern you learn here, computing an optimal count with DP and then reconstructing the actual answer greedily, shows up across many DP problems. Once you internalize it, problems like "Coin Change" become just the first phase, and you gain the ability to also produce the solution itself, not just the count.

Understanding this reconstruction technique also helps with problems where you need to trace back through a DP table to produce a specific sequence, path, or arrangement. It is a fundamental skill for DP problems at every difficulty level.

The key insight

There are two key insights that make this problem click.

First, maximize the number of digits. A number with more digits is always larger than a number with fewer digits, regardless of what those digits are. For example, 1111 is larger than 999. So the primary goal is to fit as many digits as possible within the budget.

Second, among same-length options, greedily pick the largest digit at each position. Once you know the maximum number of digits you can afford, you build the result from left to right. At each position, you try digit 9 first, then 8, then 7, and so on. You pick the largest digit whose cost still leaves enough budget to fill the remaining positions with valid digits.

The DP array dp[t] stores the maximum number of digits achievable with total cost exactly t. You fill this using an unbounded knapsack approach. Then you reconstruct the answer by walking through the DP table greedily.

The solution

def largest_number(cost: list[int], target: int) -> str:
    dp = [-1] * (target + 1)
    dp[0] = 0

    for t in range(1, target + 1):
        for i in range(9):
            if cost[i] <= t and dp[t - cost[i]] >= 0:
                dp[t] = max(dp[t], dp[t - cost[i]] + 1)

    if dp[target] < 0:
        return "0"

    result = []
    remaining = target
    for digit in range(9, 0, -1):
        while remaining >= cost[digit - 1] and dp[remaining] == dp[remaining - cost[digit - 1]] + 1:
            result.append(str(digit))
            remaining -= cost[digit - 1]

    return "".join(result)

Let's break down how each part works.

The DP table dp has target + 1 entries. dp[0] = 0 means you can form zero digits with zero cost. Every other entry starts at -1, meaning that cost value has not been reached yet. The nested loop iterates over each possible total cost t and tries all 9 digits. If using digit i + 1 (with cost cost[i]) leaves a sub-problem t - cost[i] that was already achievable, you update dp[t] to be the maximum of its current value and dp[t - cost[i]] + 1. This is the standard unbounded knapsack recurrence, but instead of minimizing cost, you are maximizing the count of items (digits).

After filling the table, if dp[target] is still -1, no combination of digits sums to exactly target, so you return "0".

The reconstruction loop is where the greedy insight kicks in. You iterate digits from 9 down to 1. For each digit, you check: can I use this digit here? The condition dp[remaining] == dp[remaining - cost[digit - 1]] + 1 confirms that using this digit leads to an optimal sub-solution. If so, you append the digit and subtract its cost. The while loop allows the same digit to be used multiple times consecutively. By trying the largest digit first, you guarantee the result is the largest possible number.

Visual walkthrough

Let's trace through the full example with cost = [4,3,2,5,6,7,2,5,5] and target = 9. Watch how the DP table fills up and how the greedy reconstruction picks digits.

The DP table tells us that with a budget of 9, we can fit at most 4 digits. The greedy reconstruction then picks 7, 7, 7, 2 from left to right, always choosing the largest digit that preserves optimality. The total cost is 2 + 2 + 2 + 3 = 9, which hits the target exactly.

Complexity analysis

Time is O(target * 9). The DP phase iterates over each value from 1 to target and, for each value, checks all 9 digit costs. The reconstruction phase also takes at most O(target) steps, since each step reduces remaining by at least 1. The dominant term simplifies to O(target).

Space is O(target) for the DP array. The result string takes at most O(target) characters as well (in the extreme case where the cheapest digit costs 1), so total space is O(target).

The building blocks

1. Unbounded knapsack for maximizing count

dp = [-1] * (target + 1)
dp[0] = 0

for t in range(1, target + 1):
    for i in range(9):
        if cost[i] <= t and dp[t - cost[i]] >= 0:
            dp[t] = max(dp[t], dp[t - cost[i]] + 1)

This is a variant of the unbounded knapsack where each "item" (digit) can be used unlimited times, and you maximize the count of items used rather than their total value. The recurrence dp[t] = max(dp[t], dp[t - cost[i]] + 1) says: if I can reach cost t - cost[i] with some number of digits, then I can reach cost t with one more digit. You keep the maximum across all choices. This same pattern appears in Coin Change (minimizing count), Coin Change II (counting combinations), and any problem where items have costs and can be reused.

2. Greedy reconstruction from DP table

result = []
remaining = target
for digit in range(9, 0, -1):
    while remaining >= cost[digit - 1] and dp[remaining] == dp[remaining - cost[digit - 1]] + 1:
        result.append(str(digit))
        remaining -= cost[digit - 1]

The reconstruction phase works backwards through the DP table. At each step, it asks: "Can I place this digit here and still have an optimal sub-solution for the remaining budget?" The condition dp[remaining] == dp[remaining - cost[digit - 1]] + 1 verifies that choosing this digit maintains the maximum digit count. By iterating digits from 9 down to 1, you guarantee the leftmost (most significant) positions get the largest possible digits. This greedy-on-top-of-DP reconstruction pattern is reusable whenever your DP gives you an optimal value and you need to recover the actual choices that led to it.

Edge cases

Before submitting, think through these scenarios:

• Target is impossible: no combination of digit costs sums to target. dp[target] stays at -1. Return "0".
• All digits have the same cost: every digit costs the same, so you use as many as the budget allows and pick digit 9 for every position.
• Single digit uses entire target: only one digit's cost equals target, and all others are too expensive. The answer is that single digit.
• Multiple digits share the cheapest cost: you pick the largest digit among those sharing the minimum cost to maximize the number value.
• Target equals 0: the problem constraints guarantee target is at least 1, but if it were 0, no digits can be painted, so the answer would be "0".
• Very large target with cheap digits: the answer can be very long. The algorithm handles this naturally since reconstruction runs in O(target) time.

From understanding to recall

You now understand the two-phase approach: fill a DP table to find the maximum digit count for each sub-target, then reconstruct the answer greedily from largest to smallest digit. The logic is clean and each phase is short. But reproducing it under pressure requires more than understanding.

The details that trip people up are in the reconstruction. Which direction do you iterate digits? What is the exact condition for choosing a digit? Do you use a for loop or a while loop for repeated digits? These are recall gaps, not conceptual ones.

Spaced repetition closes them. You practice writing the unbounded knapsack fill, the reconstruction loop, and the edge case checks from memory at increasing intervals. After a few rounds, you see "maximize digits then maximize value" in a problem statement, and the two-phase template flows out without hesitation.

Related posts

• Coin Change - The classic unbounded knapsack DP that this problem extends
• Coin Change II - Counting combinations in unbounded knapsack problems
• Decode Ways - Another DP problem that requires careful reconstruction

CodeBricks breaks Form Largest Integer into its unbounded knapsack and greedy reconstruction building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a DP reconstruction problem shows up in your interview, you do not think about it. You just write it.