Leetcode 每日一题和每日一题的下一题刷题笔记 12/30

写在前面

这是我参与更文挑战的第12天，活动详情查看：更文挑战

快要毕业了，才发现自己被面试里的算法题吊起来锤。没办法只能以零基础的身份和同窗们共同加入了力扣刷题大军。我的同学们都非常厉害，他们平时只是谦虚，口头上说着自己不会，而我是真的不会。。。乘掘金鼓励新人每天写博客，我也凑个热闹，记录一下每天刷的前两道题，这两道题我精做。我打算每天刷五道题，其他的题目嘛，也只能强行背套路了，就不发在博客里了。

本人真的只是一个菜鸡，解题思路什么的就不要从我这里参考了，编码习惯也需要改进，各位如果想找刷题高手请教问题我觉得去找 宫水三叶的刷题日记 这位大佬比较好。我在把题目做出来之前尽量不去看题解，以免和大佬的内容撞车。

另外我也希望有得闲的大佬提供一些更高明的解题思路给我，欢迎讨论哈！

好了废话不多说开始第十二天的前两道题吧！

2021.6.12 每日一题

1449. 数位成本和为目标值的最大数字

这道题看不懂题面，但是看到第一个例子就大致明白了。。。这应该也是背包问题，而且没那么单纯。各位可以列一下状态转移方程，会发现一下子连定义都定义不出来。列出来了？很好，这道题用完全背包和多重背包的方法来做。没列出来，嗯，这道题确实不是一次背包问题就完了，要用两次背包问题，或者一次背包问题一次单调栈，或者一次背包问题，再来一个记忆化。这么提示不知道能不能反应过来，这个问题有两个子问题，首先要把能获取到的最大位数找出来，然后把成本数位排列组合找数位排列组成的最大的数。第一个问题肯定是背包问题，后面这个随意，看个人爱好，不要超时就好。

完全背包做法

完全背包就是物品无限，这道题的状态转移方程比较难搞，我不打算按照前几天那种优化空间复杂度的形式来讲了，少一个维度这种题太难讲太难理解了。

dp[i][j] 表示现在看到前 i 个元素种类，现在的总成本是 j，这种情况下构成的最大整数（整数是字符串的形式，需要定一个无效状态，比如这里用 '#'）。有没有发现我没有定义一个“i 位元素选了多少个”类似这种的数组，定义这种维度的话状态转移就太麻烦了，自己可以试一试。所以一般的完全背包问题状态转移只会从两种状态转移过来，第一种是“看到了但不取，就是玩儿”，第二种是“看到了取一下，咱看后续”。我在第十天也提到了这个思路，各位可以去看看第十天的笔记，放到结尾参考链接里了。这样就能写状态转移方程了，这里 i 是从 1 开始。