目录
一、动态规划是什么？
二、通用思路
2-1、状态的定义
2-2、状态转移方程
2-3、遍历顺序
2-4、初始化
2-5、结果输出
2-6、优化
2-6-1 空间的优化
2-6-2 递归实现VS迭代实现（数组存储）
一、动态规划是什么？
动态规划（DP），即将问题不断转化为子问题，再通过子问题的求解，解决问题。
如下：
假设你正在爬楼梯。需要
n阶你才能到达楼顶。每次你可以爬
1或2个台阶。你有多少种不同的方法可以爬到楼顶呢？
经过分析，可以得到 F(n)=F(n-1)+F(n-2) 这个我们称之为状态转移方程
即，楼顶有n个台阶，每次可以爬1个或2个，问题可以转化为 n-1个台阶的不同方法（对应下一步爬1个台阶），加上n-2个台阶的不同方法（对应下一步爬2个台阶)。
当只有0个台阶，那么只有0中方法，即F(0)=0
当只有1个台阶，那么只有1种方法，即F(1)=1
当只有2个台阶，那么只有2种方法，即F(2）=2
当只有3个台阶，那么只有F(3)=F(2)+F(1)=2+1=3
当有n个台阶，那么有F(n)=F(n-1+F(n-2) 种走法。
可以发现，除了0个台阶，其它的都符合我们的推理。
动态规划的难点在于，如何找出状态转移方程，当找到状态转移方程，问题迎刃而解。
因为F(n)依赖于F(n-1)和F(n-2) 所以我们必须将F(n-1）和F(n-2)的值存储下来，常用的方式是定义一个数组，如
int[] dp =new int[n+1];二、通用思路
下面以上面的题目，尝试将动态规划的步骤拆解
2-1、状态的定义
dp[i] 为 i 个台阶，一共有多少种走法
2-2、状态转移方程
根据上面，状态转移方程为 dp[i]=dp[i-1]+dp[i-2]
2-3、遍历顺序
可以看到，对于 i 依赖于 i-1 和 i-2 ，即前面2个值
所以是后面依赖前面，顺序应该是正序
2-4、初始化
正序遍历，且需要前2个值，初始化dp数组，至少需要两个值，dp[0]为特殊情况，单独处理，所以我们至少需要提前设置
dp[1]=1;
dp[2]=2;2-5、结果输出
对于n个台阶的最大走法，结果显然为 dp[n]
2-6、优化
2-6-1 空间的优化
可以看到，上述问题使用了一个dp数组，但是实际使用中，我们只需要2个变量就可以替代掉数组的作用，即空间上可以把 优化为
实际操作中，01背包问题，经常会通过二维的dp数组，压缩为一维的dp数组
注意事项：优化空间的过程，不能导致状态值的丢失。
2-6-2 递归实现VS迭代实现（数组存储）
既然是问题转化为子问题求解，显然递归是一个好方式，但是受限于栈的大小以及可开辟的缓存空间，可灵活考虑是使用递归实现，还是迭代实现。文章来源：https://www.toymoban.com/news/detail-793202.html
如LeetCode上的一些题目，使用递归，会栈溢出，就只能使用迭代实现，另一些题目，要求空间复杂度在，可考虑递归实现。文章来源地址https://www.toymoban.com/news/detail-793202.html
到了这里，关于【算法-动态规划】通用模板的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
