5399. 数位成本和为目标值的最大数字


图片说明


利用完全背包找出最大的长度，然后贪心从最大的取。

class Solution {
public:
    int dp[5005]={0};
    string largestNumber(vector<int>& cost, int v) {
        for(int i=1;i<=v;i++)dp[i]=-500005;
        for(int i=1;i<=9;i++){
            for(int j=cost[i-1];j<=v;j++){
                dp[j]=max(dp[j],dp[j-cost[i-1]]+1);
            }
        }
        if(dp[v]<=0)return "0";
        string ans="";
        for(int i=9;i>=1;i--){
            while(v>=cost[i-1]&&dp[v]==dp[v-cost[i-1]]+1){
                v-=cost[i-1];
                ans+='0'+i;
            }
        }
        return ans;
    }
};