# 1449. Form Largest Integer With Digits That Add up to Target

• Time: $O(target)$
• Space: $O(target)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public: string largestNumber(vector& cost, int target) { // dp[i] := max length that cost i can achieve vector dp(target + 1, INT_MIN); dp[0] = 0; // When cost = 0, the best is empty string "" for (int i = 1; i <= target; ++i) for (int d = 0; d < 9; ++d) if (i >= cost[d]) dp[i] = max(dp[i], dp[i - cost[d]] + 1); if (dp[target] < 0) return "0"; string ans; // Greedily build the ans string for (int d = 8; d >= 0; --d) while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) { target -= cost[d]; ans += '1' + d; } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public String largestNumber(int[] cost, int target) { // dp[i] := max length that cost i can achieve int[] dp = new int[target + 1]; Arrays.fill(dp, Integer.MIN_VALUE); dp[0] = 0; // When cost = 0, the best is empty string "" for (int i = 1; i <= target; ++i) for (int d = 0; d < 9; ++d) if (i >= cost[d]) dp[i] = Math.max(dp[i], dp[i - cost[d]] + 1); if (dp[target] < 0) return "0"; StringBuilder sb = new StringBuilder(); // Greedily build the ans string for (int d = 8; d >= 0; --d) while (target >= cost[d] && dp[target] == dp[target - cost[d]] + 1) { target -= cost[d]; sb.append(1 + d); } return sb.toString(); } }