您好,欢迎访问代理记账网站
移动应用 微信公众号 联系我们

咨询热线 -

电话 15988168888

联系客服
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

力扣 1449. 数位成本和为目标值的最大数字 dp 贪心

https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
在这里插入图片描述
思路一:依旧是完全背包的变种……只不过这道题要求恰好装满背包,那么在初始化的时候只初始化 d p 0 dp_0 dp0为空,其余的初始化为 − ∞ -\infin 即可。但是此题需要比较的元素是字符串而不是整数,而且字符串的比较方式也有所区别:首先判断长度关系,然后逐字符判断。如果简单的认为 d p dp dp数组每个元素都是字符串,然后按照如下方程转移:
d p j = m y _ s t r i n g _ c m p ( d p j , d p j − c o s t i + s t r i n g i ) dp_{j}=my\_string\_cmp(dp_j,dp_{j-cost_i}+string_i) dpj=my_string_cmp(dpj,dpjcosti+stringi)
会发现得到的结果是错误的。为什么呢?因为字符串加法和整数加法是有区别的,对于整数, 1 + 2 = 2 + 1 = 3 1+2=2+1=3 1+2=2+1=3;对于字符串, ′ 1 ′ + ′ 2 ′ ̸ = ′ 2 ′ + ′ 1 ′ '1'+'2'\not= '2'+'1' 1+2=2+1。不过这里取的是最大值,因此我们可以自己定义一个最优的加法,利用贪心的思想很容易做到这一点:

class Solution {
public:
    string largestNumber(vector<int>& cost, int target) {
        const string init=string(1,'0'-1);
        vector<string> dp(target+1,init);
        dp[0]="";
        int n=cost.size();
        for(int i=0;i<n;i++)
        {
            char ch=i+1+'0';
            for(int j=cost[i];j<=target;j++)
                if(dp[j-cost[i]]!=init)
                {

                    dp[j]=max(dp[j],cal(dp[j-cost[i]],ch));
                }
        }
        return dp[target]==init?"0":dp[target];
    }

    string max(const string& s1,const string& s2)
    {
        int n=s1.size(),m=s2.size();
        if(n>m)
            return s1;
        else if(n<m)
            return s2;
        else
        {
            if(s1>=s2)
                return s1;
            return s2;
        }
    }

    string cal(const string& s,char ch)
    {
        int n=s.size();
        int i=0;
        while(i<n&&ch<s[i])
            ++i;
        return s.substr(0,i)+string(1,ch)+s.substr(i,n-i);
    }
};

思路二:在思路一上更进一步,其实这道题是有贪心的余地的:我们希望字符串更长,在长度相等的情况下,我们希望越靠前的字符越大。我们可以先解决第一个问题,求出满足题意的数字的最大位数,这个可以用传统完全背包的做法来做(初始化不一样)。然后找到背包问题的最优解(路径),再贪心的把路径上的字符累加起来。背包问题的最优路径其实是很好找的,由转移方程逆推回去即可。

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

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进