每日leetcode第0079天 1449. Form Largest Integer With Digits That Add up to Target

非常有趣,我们要使用一定的金额购买数字,拿买的数字拼一个最大的数。

钱还必须得花完,不能有剩下的。(这点很重要)

这道题目如果想到了动态规划,那么距离成功就不远了。

这道题就像是完全背包问题,每个数字都是价值为1,重量为cost的货物。

数字是越多越好,要先考虑多,再考虑大。

先初始化dp数组,0到target,每个先写成”0″,0写成空串””。

接下来就开始尝试去拼接。

状态转移方程式:paint[i] = to_string(j) + paint[ori];

转移之前,我们就要先考虑

1.如果原串下标左得越界了,就不用考虑了。

2.如果原串就是“0”,那也不用考虑转移了。

3.原串的长度如果和现在一样长,那么就说明可以加一位,得加,需要状态转移。如果只短一位,说明之前有更小的数字拼接过,但现在j是从小到大遍历的,所以肯定也更大,就需要状态转移。如果加了一位还没现在这个长,那么就别转了,肯定没用。

最终输出的就是paint[target]的数字。

这道题目巧在数字可能比较大,所以我们不可以傻乎乎用int或longlong,而用string。用了string怎么来比较两个数字大小,其实就是比长度,长度一样,丝毫不慌,因为j的遍历顺序设计得好。哈哈。



关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。