题目描述:
给你一个整数数组 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" 的代价为 2*3+ 3*1 = 9 。 "977" 也是满足要求的数字,但 "7772" 是较大的数字。
数字 成本
1 -> 4
2 -> 3
3 -> 2
4 -> 5
5 -> 6
6 -> 7
7 -> 2
8 -> 5
9 -> 5
题解:
动态规划,容易看懂,难点在于string怎么用,以及里面用到了贪心,大数字要放在前面
注意:
string用法
题源:
https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target/
class Solution { public: string maxstring(string a,string b) //string类型是这么比较的,长度用size(),大小直接比 { if (a=="#") return b; if (b=="#") return a; if(a.size()!=b.size()) return a.size()>b.size()?a:b; else return a>b?a:b; } string largestNumber(vector<int>& cost, int target) { string dp[5005]; for(int i=1;i<=target;i++) dp[i]='#'; dp[0]=""; for(int i=0;i<9;i++) for(int j=cost[i];j<=target;j++) if(dp[j-cost[i]]!="#") { string a; char ch=char(i+1)+'0'; a=ch; //在cb中to_string不能直接用,string类型的,char变量可以直接赋值。 a=a+dp[j-cost[i]]; dp[j]=maxstring(dp[j],a); } if(dp[target]=="#") return "0"; return dp[target]; } };