type
status
date
slug
summary
tags
category
icon
password
状态
专注质量
预计（分钟）
开始时间
结束时间
本文是经过在代码随想录网站上学习和刷题，总结下来的一些思考。如有侵权，立刻删除。
🤔 综述
动态规划部分的题目类型多、难度较高，需要刷题时格外注意体会思路。
现总结动态规划五部曲如下：
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
其中，最困难的实际上是第三步和第四步。当我们遇到一个问题时，如果我们能确定要使用动态规划方法来解决，那么说明我们已经对状态如何转移和推导有了一个模糊的认识，而dp数组无非就是一维、二维两种情况，分别去思考如何定义合理即可。
最难的部分是初始化和遍历。我们需要知道dp数组中下一个元素的来源，以推导出它。如果dp[i][j]由左上角的元素推出，那么遍历顺序一定是从上往下，从左往右；如果dp[i][j]由下方和左边的元素推出，那么遍历顺序一定是由下往上，从左往右，依次类推。
建议在没有思路的时候，打开本地的控制台程序，将自己推导的公式打印出来看看，理清思路。可以借此机会练习一下ACM模式。
📝动态规划
题型
动态规划基础
很容易掌握的一些题目，复习时简单看下即可。
背包问题
打家劫舍系列
这个系列很有意思，也不难，
股票系列
股票系列问题也不是很难，可以简单复习下。
子序列系列
这个部分的一些题目是相当难的，一刷基本上已经放弃了，回头再说吧。
贪心与动态规划
当遇到回溯算法、动态规划和贪心算法相关的题目时，你会明显感觉到它们与之前的题目有所不同。
这是因为这些题目开始更密切地与现实情境结合，而且往往是各大公司主要考察的题目。
因此，当遇到这类题目时，你可以花费1-2分钟按照以下的思路尝试解题：
- 暴力算法（如果在使用暴力算法过程中，发现连嵌套循环的次数都无法确定，那么大概率是回溯算法，因为回溯算法的时间复杂度通常是指数级）
- 贪心算法（如果能够聪明地解决问题）
- 动态规划（如果能将问题划分为一系列小问题，这是一种数学思想）
基本上这样就能找到解题的思路，接下来就是如何实施这五部曲的问题了。
🤗总结归纳
需要感谢代码随想录，刷完这一部分的题目后，基本上就可以宣布告一段落了。这个刷题顺序还是比较不错的，非常感谢前人做的一系列总结和归纳，让后来者在刷题时减少了许多试错成本。
致谢：
Written by Aryue,editted by Notion AI.
- 作者:Aryue
- 链接:www.aryue.com/article/664ce565-0875-4414-98f2-ea3ac954c1e9
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
相关文章
