數位成本和為目标值的最大數字

原題連結：https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/

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

給目前結果添加一個數位（i + 1）的成本為 cost[i] （cost 數組下标從 0 開始）。

總成本必須恰好等于 target 。

添加的數位中沒有數字 0 。

由于答案可能會很大，請你以字元串形式傳回。

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

解題思路

看資料範圍，應該是和target有關的一個dp。細細想來就是完全背包。

設dp[i] 為成本剛好為i的能組成的最大的數。

由于這個數可能太大，是以用string 來存儲。用mybigger 函數來判斷兩個string 的大小。由于空指針的存在，是以初始化下。其中dp[0]是第一個合法狀态。

要找的答案是最大，是以先加大的數。

代碼

class Solution {
    public String largestNumber(int[] cost, int target) {
        String dp[] = new String[target + 1];
        dp[0] = "0";
        for(int i = 1; i <= target; i++)
        {
            dp[i] = "";
        }
        String num[] = {"1", "2", "3", "4", "5", "6", "7", "8", "9"};
        //先加大的數
        for(int i = 8; i >= 0; i--)
        {
            for(int j = cost[i]; j <= target; j++)
            {
                if(dp[j - cost[i]] != "" && mybigger(dp[j - cost[i]] + num[i], dp[j]))
                {
                    dp[j] = dp[j - cost[i]] + num[i];
                }
            }
        }
        return dp[target] == "" ? "0" : dp[target].substring(1);
    }
    public boolean mybigger(String a, String b)
    {
        if(a.length() != b.length())
        {
            return a.length() > b.length();
        }
        int i = 0;
        while(i < a.length())
        {
            if(a.charAt(i) != b.charAt(i))
            {
                return a.charAt(i) > b.charAt(i);
            }
            i++;
        }
        return true;
    }
}