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

写在前面

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

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

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

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

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

2021.6.11 每日一题

279. 完全平方数

这个题一看就知道是物品无限的背包问题。然后容量是当前的和 i，价值是最少需要的平方数个数 dp[i]，这些平方数加起来就是当前的和 i。因为 i 是一个平方和，所以构成 i 的若干平方数开根号以后都没有 i 开根号之后大。这就定出来一个搜索范围，只要在 $[0, \sqrt{\texttt{i}}]$ 里面挑选，平方之后加和就能找到一个凑出 i 的组合。假设现在选到了 j 这个数，那么之后就只需要去凑出 dp[i - j * j] 就可以。接下来就可以写状态转移方程了。