Leetcode -1449- Digit cost and maximum number for target value

A path to learning at 🐔

[B].

I give you an integer array cost and an integer target. Return the largest integer that satisfies the following rule: add one digit (I +) to the current result1) cost cost[I] (cost array subscript from0Start). The total cost must be exactly equal to Target. There are no digits in the added digits0. Since the answer may be large, please return it as a string. If you cannot get any integers as described above, return"0". The sample1: Input: cost = [4.3.2.5.6.7.2.5.5], target = 9Output:"7772"Explanation: Add digits'7'For the cost of2, add digits'2'For the cost of3. so"7772"Price for2*3+ 3*1 = 9 。 "977"That's the number we want to find, but"7772"It's the larger number. Digital cost1  ->   4
  2  ->   3
  3  ->   2
  4  ->   5
  5  ->   6
  6  ->   7
  7  ->   2
  8  ->   5
  9  ->   5The sample2: Input: cost = [7.6.5.5.5.6.8.7.8], target = 12Output:"85"Explanation: Add digits'8'The cost is7, add digits'5'The cost is5 。"85"For the cost of7 + 5 = 12. The sample3: Input: cost = [2.4.6.2.4.6.4.4.4], target = 5Output:"0"Explanation: Total cost is target condition, cannot generate any integer. The sample4: Input: cost = [6.10.15.40.40.40.40.40.40], target = 47Output:"32211"Tip: cost.length ==9 
 1 <= cost[i] <= 5000 
 1 <= target <= 5000Related Topics String dynamic planning 👍65 👎 0
Copy the code

[答 案]

Leetcode topic link

[making address]

Code link

[introduction]

Idea 1: dynamic planning + exhaustive

  • The larger the number of digits, the more the number of digits required, the better. In the case of the same number of digits, the greater the number of digits required
  • Can be converted to a knapsack problem that is, the value of each item is 1, the capacity is the array element value, find the maximum element solution that can satisfy the knapsack capacity (each item has only one)
  • The solution can refer to the knapsack problem and write dynamic programming
  • The equation DP [I] is defined to represent the most elemental solutions satisfying j capacity
  • dp[i] = max(dp[i-cost[0->cost.length] + 1])
  • After that, the final solution can be obtained by inverse derivation of the optimal solution
  • That’s a really good idea. PassdpValue backsliding must be the current optimal solution traversing all valuesval dp[j] == dp[j – u] + 1This condition satisfies the condition that the optimal solution must be obtained
  • I thought of two steps, but in addition to mistakes in the first step of converting one dimension, I was still young when I didn’t think of a proper saving scheme in the second part
public String largestNumber(int[] cost, int target) {
            int[] dp = new int[target + 1];
            Arrays.fill(dp, Integer.MIN_VALUE);
            dp[0] = 0;
            for (int i = 1; i < 10; i++) {
                int val = cost[i - 1];
                for (int j = val; j <= target; j++) {
                    dp[j] = Math.max(dp[j], dp[j - val] + 1); }}if (dp[target] < 0) {
                return "0";
            }
            StringBuilder ans = new StringBuilder();
            Val dp[j] == dp[j] + 1 val dp[j] == dp[j] + 1 val dp[j] == dp[j] + 1 val dp[j] = dp[j] + 1
            for (int i = 9, j = target; i >= 1; i--) {
                int val = cost[i - 1];
                while (j >= val && dp[j] == dp[j - val] + 1) { ans.append(String.valueOf(i)); j -= val; }}return ans.toString();

        }
Copy the code

Time complexity O(n*10)