Leetcode 1449: Form Largest Integer With Digits That Add up to Target

In this Leetcode problem, we are given the cost of each digit and a target cost target, and we try to find the maximum number satisfying the cost

Problem statement

Solution

We are going to use dynamic programming to find all the solutions for target values 1 to target, given the cost.

Algorithm ideas:

• When we know the solution for all largestNumber(cost, i), with 1 <= i < target, we can find largestNumber(cost, target) by trying all the digits 1-9 and concatenate them with:
• newString = d + largestNumber(cost, target — cost[d-1])
• Optimization: if 2 digits have the same cost, just keep the largest one in values in map cost -> digit, This map is used so that we can look up all the relevant costs fast
• We memorize all the solutions largestNumber(cost, i)in mem[i]

Here is the full solution:

class Solution {
    public String largestNumber(int[] cost, int target) {
        String[] mem = new String[target+1];
        Map<Integer, String> s = new HashMap<>();
        int n = cost.length;
        for (int i = 0; i < n; i++) {
            if (cost[i] <= target) {
                mem[cost[i]] = "" + (i+1);
                s.put(cost[i], "" +…