动态规划知识梳理
动态规划知识梳理
动态规划英文是"Dynamic Programming",简称“dp”。他不是算法，而是一种思维方式，主要以递推来解决问题
先来说说动态规划和递归的区别吧
| 动态规划 | 递归 | |
|---|---|---|
| 解题方向 | 自底向上 | 自顶向下 |
| 时间复杂度 | O(N) | O(n32n) |
p.s.他们的相同点是当前问题都依赖于之前问题的解
动态规三个步骤
1， 定义状态 ：
定义状态指的就是给dp[i]定义一个通解 ，也就是给dp[i]定义一个意思定义状态指的就是给dp[i]定义一个通解 ，也就是给dp[i]定义一个意思；
2，写出状态转移方程 ：
状态转移方程是动态规划中最重要的一环，作用是求出dp[i]的状态
3，确定边界条件 ：
所谓的边界条件就是动态规划的最小子问题，是动态规划一定取不出来，只能自己算的东西