力扣题目：#70. 爬楼梯
刷题时长：5min
解题方法：动态规划
复杂度分析
- 时间复杂度: O(nm)
- 空间复杂度: O(n)
问题总结
- 条件判断背包容量时的逻辑是大于等于，漏掉了等于
- 忘记dp数组初始化，递归五部曲，一步不能少
本题收获
- 动规思路
- 确定dp数组及下标的含义：爬到有i个台阶的楼顶，有dp[i]种方法
- 确定递推公式：dp[i] += dp[i - j]
- dp数组的初始化：dp[0] =1
- 确定遍历顺序：将target放在外循环，将nums放在内循环，此题求排列
力扣题目：#322. 零钱兑换
刷题时长：30min
解题方法：动态规划
复杂度分析
- 时间复杂度: O(n * amount)，其中 n 为 coins 的长度
- 空间复杂度: O(amount)
问题总结
- 卡在无解的case，打印dp数组后才debug：若dp[amount]最后仍为初始化的值，则无解
本题收获
- 动规思路
- 确定dp数组及下标的含义：凑足总额为j所需钱币的最少个数为dp[j]
- 确定递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j])
- dp数组的初始化：dp[0] = 0, 下标非0的元素都是应该是最大值
- 确定遍历顺序：coins（物品）放在外循环，target（背包）在内循环。且内循环正序
力扣题目：#279.完全平方数
刷题时长：10min
解题方法：动态规划
复杂度分析
- 时间复杂度: O(n * √n)
- 空间复杂度: O(n)
问题总结
- 平方数数组不能剪枝，得计算到n^2，才能包含当n=1的边界情况
本题收获
- 题意转换：完全平方数就是物品（可以无限件使用），凑个正整数n就是背包，问凑满这个背包最少有多少物品
- 动规思路：题解方法
- 确定dp数组及下标的含义：和为j的完全平方数的最少数量为dp[j]
- 确定递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j])
- dp数组的初始化：dp[0]=0，非0下标的dp[j]一定要初始为最大值，这样dp[j]在递推的时候才不会被初始值覆盖
- 确定遍历顺序：外层for循环遍历物品，内层for遍历背包
本文链接：https://my.lmcjl.com/post/13208.html
展开阅读全文
4 评论