Code Implementation

class Solution:
    def largestNumber(self, cost, target):
        dp = [''] + [None] * target
        for t in range(1, target + 1):
            for d in range(9, 0, -1):
                c = cost[d-1]
                if t >= c and dp[t-c] is not None:
                    cand = dp[t-c] + str(d)
                    if dp[t] is None or len(cand) > len(dp[t]) or (len(cand) == len(dp[t]) and cand > dp[t]):
                        dp[t] = cand
        return dp[target] if dp[target] is not None else "0"
      

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<string> dp(target+1, "");
        for (int i = 1; i <= target; ++i) {
            dp[i] = "0";
            for (int d = 9; d >= 1; --d) {
                int c = cost[d-1];
                if (i >= c && dp[i-c] != "0") {
                    string cand = dp[i-c] + char('0'+d);
                    if (dp[i] == "0" || cand.length() > dp[i].length() || (cand.length() == dp[i].length() && cand > dp[i]))
                        dp[i] = cand;
                }
            }
        }
        return dp[target] == "0" ? "0" : dp[target];
    }
};
      

class Solution {
    public String largestNumber(int[] cost, int target) {
        String[] dp = new String[target + 1];
        dp[0] = "";
        for (int t = 1; t <= target; ++t) {
            dp[t] = null;
            for (int d = 9; d >= 1; --d) {
                int c = cost[d-1];
                if (t >= c && dp[t-c] != null) {
                    String cand = dp[t-c] + d;
                    if (dp[t] == null || cand.length() > dp[t].length() || (cand.length() == dp[t].length() && cand.compareTo(dp[t]) > 0)) {
                        dp[t] = cand;
                    }
                }
            }
        }
        return dp[target] == null ? "0" : dp[target];
    }
}
      

var largestNumber = function(cost, target) {
    let dp = Array(target + 1).fill(null);
    dp[0] = "";
    for (let t = 1; t <= target; ++t) {
        for (let d = 9; d >= 1; --d) {
            let c = cost[d-1];
            if (t >= c && dp[t-c] !== null) {
                let cand = dp[t-c] + d.toString();
                if (dp[t] === null || cand.length > dp[t].length || (cand.length === dp[t].length && cand > dp[t])) {
                    dp[t] = cand;
                }
            }
        }
    }
    return dp[target] === null ? "0" : dp[target];
};
      

Problem Description

Given an array cost of length 9, where cost[i] is the cost of using digit i+1, and an integer target, your goal is to construct the largest integer (as a string) whose digits sum to target when their costs are added up. You can use each digit as many times as you like. If it's not possible to reach exactly target cost, return "0".

• Each digit from 1 to 9 can be used any number of times.
• You must use digits so that the sum of their costs is exactly target.
• If there are multiple ways, return the numerically largest integer (as a string).
• If there is no valid solution, return "0".

Thought Process

At first glance, the problem resembles the classic "coin change" problem, where you want to use coins (here, digits) with given costs to sum up to a target. But instead of just counting the number of ways, we want to maximize the integer formed by the chosen digits.

A brute-force approach would try all combinations of digits, but this is very inefficient due to the exponential number of possibilities. Instead, we need to optimize by always trying to use the largest digits possible, and by using dynamic programming to avoid redundant calculations.

The main insight is: for each possible total cost from 1 to target, keep track of the largest number (as a string) that can be formed using digits with that total cost. This allows us to build up solutions for larger targets from smaller ones, just like in dynamic programming.

Solution Approach

• Dynamic Programming Setup:
  • Create a DP array dp of size target + 1, where dp[t] stores the largest number (as a string) that can be formed with total cost t.
  • Initialize dp[0] to the empty string (since zero cost means no digits), and the rest to None or a marker for "not possible".
• Filling the DP Array:
  • For each total cost t from 1 to target:
  • For each digit d from 9 down to 1 (to prioritize larger digits):
  • If t is at least cost[d-1] and dp[t - cost[d-1]] is not impossible:
  • Form a candidate number by appending d to dp[t - cost[d-1]].
  • If this candidate is longer or lexicographically larger than the current dp[t], update dp[t].
• Result:
  • After filling dp, if dp[target] is not impossible, return it. Otherwise, return "0".
• Why This Works:
  • By always considering larger digits first and updating only when we find a longer or lexicographically larger number, we ensure the final answer is the largest possible.
  • Dynamic programming ensures we don't recompute solutions for the same cost multiple times.

Example Walkthrough

Sample Input:
cost = [4,3,2,5,6,7,2,5,5], target = 9

• We want the largest number whose digits cost exactly 9.
• For each t from 1 to 9, we try using digits 9 down to 1:
• For t = 2, digit 3 and 7 both cost 2. So dp[2] can be "3" or "7", but since we try larger digits first, "7" is picked.
• For t = 4, digit 1 costs 4, so "1", but also two 3's ("33") is possible since 2+2=4. "7" + "7" is also possible ("77").
• As we proceed, always try to append the largest possible digit to previous solutions.
• At t = 9, the largest possible is "7772" (three 7's and a 2), but if there's a way to use more digits, like "222222222", that's considered. But due to cost, the best is "7772".
• The answer is the largest such number found at dp[9].

Time and Space Complexity

• Brute-Force:
  • Would try all combinations of digits, which is exponential in target. Impractical for large target.
• Optimized DP Approach:
  • Time Complexity: O(target * 9) — For each t (up to target), we check all 9 digits.
  • Space Complexity: O(target * L), where L is the maximum possible length of the number string (at most target // min(cost)).
  • Both are efficient for reasonable values of target (up to 5000 on Leetcode).

Summary

The problem is a variation of the coin change problem focused on maximizing the integer value formed by chosen digits. By using dynamic programming and always trying larger digits first, we efficiently build up the solution and ensure the answer is the largest possible. The key insight is to store, for each total cost, the best (largest) number we can make, and to build up to the target using previous results. This approach is both elegant and efficient.