浙江省电子商务网站建设宁波网站制作优化服务

从第一个例子可以知道，贪心是不对的，因此考虑动态规划。最简单是递归考虑，f(i）表示cost为i对应的最大数字，因此不难写出以下递归代码

class Solution:def largestNumber(self, cost: List[int], target: int) -> str:@lru_cache(None)def maxNum(i):if i == 0 :return 0if i < 0 :return -1res = -1for j, x in enumerate(cost):tmp = maxNum(i - x)res = max(res, maxNum(i - x) * 10 + j + 1)return resres = maxNum(target)return "0" if res == -1 else str(res)

以上代码充分利用了Python的特性，由于这里数字会暴INT，用字符串表示，先把返回值变为字符串

class Solution:def largestNumber(self, cost: List[int], target: int) -> str:@lru_cache(None)def maxNum(i):if i == 0 :return ""if i < 0 :return "0"res = "0"for j, x in enumerate(cost):cur = maxNum(i - x)if cur != "0" and len(cur) + 1 >= len(res):res =  str(j + 1) + curreturn resreturn maxNum(target)

这里由于我们从1到9顺序枚举字符串，因此我们实际上只用看字符符串的长度，不需要实际去比较整个字符串。

将递归改成循环

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

进一步优化的方法，我们不需要把答案完整的记录下来，只需要记录第一个数字和长度，然后再扫一遍求出方案

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