一、动态规划三板斧
- 状态转移公式
- 循环 或 递归
- 性能优化
二、WHY
1、状态转移公式
动态规划与分治不一样，分治的问题是相互独立的，而动态规划的各个状态是有关联关系的。比如背包问题，你选择了 i 物品之后，背包的剩余容量要发生变化吧，对装别的物品就有影响了。
状态转移公式就是刻画这种关联的，一旦知道了这种关系，就可以道生一，一生二，二生三，三生万物了。
怎么生万物呢？
靠循环。
2、循环&递归
为了穷尽所有可能。
值得注意的是：循环一般是从前往后思考，而递归往往是从后往前考虑。
3、性能优化
正是要穷尽所有可能，动态规划的时间复杂度通常是指数级的，性能很差。动态规划还有维度爆炸的问题，就是当考虑的维度过多时，穷尽不过来了。因此一定要做性能优化，最经典的方式就是以空间换时间。
总结来说：
动态规划，就是用状态转移公式建立关系，用循环穷尽所有可能，最后捡出符合的答案。
三、HOW
如何运用这三板斧？
1、找到状态转移公式
① 借助几何图形看关系
比如背包问题中，列出表格；找零问题中，建立树形图；杨辉三角问题，画出杨辉三角。
不要小看列表格的过程。
不要小看列表格的过程。
不要小看列表格的过程。
我一开始觉得看看别人列的表格就行了，后来才发现列表格的过程就是理解动态规划的开始。
不要动眼不动手。
② 确定问题维度
一维问题，一个参数就能表示，比如爬楼问题状态用 f ( n )就能表示。二维问题，比如杨辉三角问题，用 f ( x, y )表示一个节点状态。
③ 确定边界条件
边界条件是你递归的出口，或者循环的起点。下面几种是常见的边界调节-
x === 1 return ...
y <= 0 return ...④ 列出状态转移公式和边界条件
2、循环/递归
要递归的内容，和递归的出口，上一步已经定好了。这里直接拿来用就行了。
3、性能优化
递归时，很容易导致重复计算。这时用空间换时间，将计算过的状态储存起来，然后也作为递归的出口，碰到计算过的数据，直接取值即可。
四、如何入门动态规划
思想是无形的，动态规划尤其细腻、微妙，要用有形来攻无形。可以联系下面几道经典题目，能帮助你学习无形的思想。
由浅到深：
- 斐波那契数列
- 爬楼梯问题
- 机器人走方格问题
- 杨辉三角（变形）问题
- 01背包问题
- 找硬币问题
等你深入理解这些问题之后，会发现它们有着很多相似处，有的更是相互的变形。然后你对动态规划就会有更立体的认识，而且会体会到其中的乐趣。
编辑于 2021-10-25 10:16 标签：状态,递归,问题,理解,杨辉三角,动态,规划 From： https://www.cnblogs.com/shoshana-kong/p/17001255.html