這是我參與更文挑戰的第12天
，活動詳情查看更文挑戰

題目

給你一個整數數組 cost 和一個整數 target 。請你返回滿足如下規則可以得到的 最大 整數：

給當前結果添加一個數位（i + 1）的成本為 cost[i] （cost 數組下標從 0 開始）。
總成本必須恰好等于 target 。
添加的數位中沒有數字 0 。
由于答案可能會很大，請你以字符串形式返回。

如果按照上述要求無法得到任何整數，請你返回 “0” 。

• 示例 1：

輸入：cost = [4,3,2,5,6,7,2,5,5], target = 9
輸出：“7772”
解釋：添加數位 ‘7’ 的成本為 2 ，添加數位 ‘2’ 的成本為 3 。所以 “7772” 的代價為 23+ 31 = 9 。 “977” 也是滿足要求的數字，但 “7772” 是較大的數字。

 數字     成本1  ->   42  ->   33  ->   24  ->   55  ->   66  ->   77  ->   28  ->   59  ->   5

• 示例 2：

輸入：cost = [7,6,5,5,5,6,8,7,8], target = 12
輸出：“85”
解釋：添加數位 ‘8’ 的成本是 7 ，添加數位 ‘5’ 的成本是 5 。“85” 的成本為 7 + 5 = 12 。

• 示例 3：

輸入：cost = [2,4,6,2,4,6,4,4,4], target = 5
輸出：“0”
解釋：總成本是 target 的條件下，無法生成任何整數。

• 示例 4：

輸入：cost = [6,10,15,40,40,40,40,40,40], target = 47
輸出：“32211”

解題思路

數組定義

• dp[i][j]代表選擇前i個數位，成本為j時，組成最大整數的長度
• log[i][j]記錄當前dp[i][j]的情況是由dp[i][log[i][j]]轉移而來的

狀態轉移

• j-cost[i]<0
  當前總成本太小了，不足以取第i位，因此

dp[i+1][j]=dp[i][j];

• j-cost[i]>=0
  成本足夠了，可以選擇是否取當前數位。判斷取當前數位或者不取的情況下，哪種情況下產生的數位更多，選擇產生數位最多的一種情況。

                  if (dp[i][j]>dp[i+1][j-cost[i]]+1){dp[i+1][j]=dp[i][j];log[i+1][j]=j;}else {dp[i+1][j]=dp[i+1][j-cost[i]]+1;log[i+1][j]=j-cost[i];}

代碼

class Solution {public String largestNumber(int[] cost, int target) {int[][] dp = new int[10][target + 1];int[][] log = new int[10][target + 1];for (int i=0;i<10;i++){Arrays.fill(dp[i],Integer.MIN_VALUE);}dp[0][0]=0;for (int i=0;i<9;i++){for (int j = 0; j <= target; j++) {if(j-cost[i]<0){dp[i+1][j]=dp[i][j];log[i+1][j]=j;}else{if (dp[i][j]>dp[i+1][j-cost[i]]+1){dp[i+1][j]=dp[i][j];log[i+1][j]=j;}else {dp[i+1][j]=dp[i+1][j-cost[i]]+1;log[i+1][j]=j-cost[i];}}}}StringBuilder res = new StringBuilder();int i=9,j=target;if(dp[i][j]<0)  return "0";while (i>0){if(log[i][j]==j){i--;}else{j=log[i][j];res.append(i);}}return res.toString();}
}