LeetCode 1449. 数位成本和为目标值的最大数字（DP）
LeetCode 1449. 数位成本和为目标值的最大数字（DP）
Michael阿明
发布于 2021-09-06 11:10:52
发布于 2021-09-06 11:10:52
文章被收录于专栏：Michael阿明学习之路
文章目录
1. 题目
给你一个整数数组 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
示例 2：
输入：cost = [7,6,5,5,5,6,8,7,8], target = 12
输出："85"
解释：添加数位 '8' 的成本是 7 ，添加数位 '5' 的成本是 5 。"85" 的成本为 7 + 5 = 12 。
示例 3：
输入：cost = [2,4,6,2,4,6,4,4,4], target = 5
输出："0"
解释：总成本是 target 的条件下，无法生成任何整数。
示例 4：
输入：cost = [6,10,15,40,40,40,40,40,40], target = 47
输出："32211"
提示：
cost.length == 9
1 <= cost[i] <= 5000
1 <= target <= 5000来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/form-largest-integer-with-digits-that-add-up-to-target 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
2. 解题
dp[x]表示 花费正好为 x 能构成的 最大的数字
class Solution {
public:
string largestNumber(vector<int>& cost, int target) {
vector<string> dp(target+1, "");
for(int i = 0; i < 9; ++i)
if(cost[i] <= target)
dp[cost[i]] = string(1, '1'+i); // 初始化
for(int j = 1; j <= target; ++j)
{ // 遍历状态
for(int i = 0; i < 9; ++i)
{ // 遍历达到该目标的方法
if(dp[j] == "" || j+cost[i] >target)
continue;
if(dp[j].size()+1 > dp[j+cost[i]].size()) // 如果长度更大得到的数字更大
dp[j+cost[i]] = dp[j]+char('1'+i);
else if(dp[j].size()+1 == dp[j+cost[i]].size())// 如果长度相等，取较大的数字
dp[j+cost[i]] = max(dp[j+cost[i]], dp[j]+char('1'+i));
}
}
return dp[target]=="" ? "0" : dp[target];
}
};284 ms 482.2 MB C++
附一个例子的求解过程
[4,3,2,5,6,7,2,2,2]
10dp[4] = 1
dp[3] = 2
dp[2] = 3
dp[5] = 4
dp[6] = 5
dp[7] = 6
dp[2] = 7
dp[2] = 8
dp[2] = 9
num=1 cost[i]：4 dp[2] = 9 dp[6] = 91
num=2 cost[i]：3 dp[2] = 9 dp[5] = 92
num=3 cost[i]：2 dp[2] = 9 dp[4] = 93
num=4 cost[i]：5 dp[2] = 9 dp[7] = 94
num=5 cost[i]：6 dp[2] = 9 dp[8] = 95
num=6 cost[i]：7 dp[2] = 9 dp[9] = 96
num=7 cost[i]：2 dp[2] = 9 dp[4] = 97
num=8 cost[i]：2 dp[2] = 9 dp[4] = 98
num=9 cost[i]：2 dp[2] = 9 dp[4] = 99
num=1 cost[i]：4 dp[3] = 2 dp[7] = 94
num=2 cost[i]：3 dp[3] = 2 dp[6] = 91
num=3 cost[i]：2 dp[3] = 2 dp[5] = 92
num=4 cost[i]：5 dp[3] = 2 dp[8] = 95
num=5 cost[i]：6 dp[3] = 2 dp[9] = 96
num=6 cost[i]：7 dp[3] = 2 dp[10] = 26
num=7 cost[i]：2 dp[3] = 2 dp[5] = 92
num=8 cost[i]：2 dp[3] = 2 dp[5] = 92
num=9 cost[i]：2 dp[3] = 2 dp[5] = 92
num=1 cost[i]：4 dp[4] = 99 dp[8] = 991
num=2 cost[i]：3 dp[4] = 99 dp[7] = 992
num=3 cost[i]：2 dp[4] = 99 dp[6] = 993
num=4 cost[i]：5 dp[4] = 99 dp[9] = 994
num=5 cost[i]：6 dp[4] = 99 dp[10] = 995
num=7 cost[i]：2 dp[4] = 99 dp[6] = 997
num=8 cost[i]：2 dp[4] = 99 dp[6] = 998
num=9 cost[i]：2 dp[4] = 99 dp[6] = 999
num=1 cost[i]：4 dp[5] = 92 dp[9] = 994
num=2 cost[i]：3 dp[5] = 92 dp[8] = 991
num=3 cost[i]：2 dp[5] = 92 dp[7] = 992
num=4 cost[i]：5 dp[5] = 92 dp[10] = 995
num=7 cost[i]：2 dp[5] = 92 dp[7] = 992
num=8 cost[i]：2 dp[5] = 92 dp[7] = 992
num=9 cost[i]：2 dp[5] = 92 dp[7] = 992
num=1 cost[i]：4 dp[6] = 999 dp[10] = 9991
num=2 cost[i]：3 dp[6] = 999 dp[9] = 9992
num=3 cost[i]：2 dp[6] = 999 dp[8] = 9993
num=7 cost[i]：2 dp[6] = 999 dp[8] = 9997
num=8 cost[i]：2 dp[6] = 999 dp[8] = 9998
num=9 cost[i]：2 dp[6] = 999 dp[8] = 9999
num=2 cost[i]：3 dp[7] = 992 dp[10] = 9991
num=3 cost[i]：2 dp[7] = 992 dp[9] = 9992
num=7 cost[i]：2 dp[7] = 992 dp[9] = 9992
num=8 cost[i]：2 dp[7] = 992 dp[9] = 9992
num=9 cost[i]：2 dp[7] = 992 dp[9] = 9992
num=3 cost[i]：2 dp[8] = 9999 dp[10] = 99993
num=7 cost[i]：2 dp[8] = 9999 dp[10] = 99997
num=8 cost[i]：2 dp[8] = 9999 dp[10] = 99998
num=9 cost[i]：2 dp[8] = 9999 dp[10] = 99999我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/06/12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。
腾讯云开发者
