DP-Hard

**Abstract：**DP Hard 合集

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

解法一：bottom-up

由于字符串拼接 $O(target^2)$ ，子问题$O(9 * target)$

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<string> dp(target + 1, "0");
        dp[0] = "";
        for(int i = 1; i <= target; i++) {
            for(int d = 0; d < 9; d++) {
                const int t = i - cost[d];
                if(t >= 0 && dp[t] != "0" && dp[t].length() + 1 >= dp[i].length())
                    dp[i] = to_string(d + 1) + dp[t];
            }
        }
        return dp[target];
    }
};

解法二：优化字符串拼接

只记录此时的最优数字和当前长度, $O(9 * target )$

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        vector<pair<int, int>> dp(target + 1, { -1, -1 });
        dp[0] = { 0, 0 };
        for(int i = 1; i <= target; i++) {
            for(int d = 0; d < 9; d++) {
                const int t = i - cost[d];
                if(t >= 0 && dp[t].second != -1 && dp[t].second + 1 >= dp[i].second)
                    dp[i] = { d + 1, dp[t].second + 1};
            }
        }
        if(dp[target].second == -1) return "0";
        string res;
        while(target) {
            res += to_string(dp[target].first);
            target -= cost[dp[target].first - 1];
        }

        return res;
    }
};