文章目录
动态规划理论基础
什么是动态规划
动态规划(Dynamic Programming, DP)，如果某一个问题有很多重叠子问题，这样往往是用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。
对于刷题来说就抓住一句话：
动规是由前一个状态推导出来的，而贪心是从局部直接选出最优的。
动态规划的解题步骤
在全面总结动态规划解题步骤前，同时也是做动态规划类题目之前，我们要先搞明白以下几个问题：
DP数组以及下标的含义
有很多类问题有一个二维dp数组，其中的行、列的含义一定要搞清楚；同理一维dp数组中的值又是什么呢？在写代码前，一定要搞明白这是什么意思。
递推公式
动态规划递推公式仅仅是一部分，而不是只要掌握了递推公式，动规就变得简单了。
DP数组初始化
dp数组如何初始化其实紧贴着dp数组以及下标含义，如果dp数组里是什么，各个维度含义是什么，那dp数组的初始化更加无从谈起了。
DP数组遍历顺序
对于背包类问题，遍历顺序是非常有讲究的，所以每道题一定要弄清他们的遍历顺序。
打印DP数组
如果题目通过不了，首先应该考虑是不是dp数组出了问题，我们应该吧dp数组打印出来看是否符合预期
动态规划五部曲
一定要仔细分析上述的五大问题
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
动态规划应该如何debug
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。
这样才是一个完整的思考过程，而不是一旦代码出问题，就毫无头绪的东改改西改改，最后过不了，或者说是稀里糊涂的过了。
这里给出卡哥写的自我debug的灵魂三问：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
509.斐波那契数
文章链接：509.斐波那契数列
视频链接：手把手带你入门动态规划 | leetcode：509.斐波那契数
状态：迭代法还是会写一写
什么是斐波那契数列
动态规划五部曲
确定dp数组下标以及含义
dp[i]表示第i个斐波那契数值为dp[i]
确定递推公式
斐波那契数的递推公式很明显： d p [ i ] = d p [ i − 1 ] + d p [ i − 2 ] dp[i] = dp[i - 1] + dp[i - 2] dp[i]=dp[i−1]+dp[i−2]
dp数组如何初始化
斐波那契的初始化也很简单 [ 0 , 1 , 1 , 2 , 3 , 5 , 8 ] [0, 1, 1, 2, 3, 5, 8] [0,1,1,2,3,5,8]
由数学归纳可知： d p [ 0 ] = 0 ; d p [ 1 ] = 1 ; dp[0] = 0; dp[1] = 1; dp[0]=0;dp[1]=1;
在很多题目中，dp数组的初始化往往也依赖于递推公式
确定遍历顺序
本题中，遍历顺序从前向后即可。（有一些题目从后向前遍历；有一些题目两层for循环，其先先后顺序也有说法）
打印DP数组
这个主要是用来debug的
代码实现
vector<int> dp(n+1);
//初始化
dp[0] = 0; dp[1] = 1;
for (i = 2; i <= n; i++)
dp[i] = dp[i-1] + dp[i-2];
return dp[n];
对状态进行压缩，只需要维护两个数值就可以了，不需要记录整个序列.代码可以缩减为
int fib(int N){
if (N <= 1) return N;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++){
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
时间复杂度为O(2^n)的递归解法：
int fib(int N){
if (N < 2) return N;
return fib(N - 1) + fib(N - 2);
}
CPP代码
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
vector<int> dp(N + 1);
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[N];
}
};
//只维护两个数值
class Solution {
public:
int fib(int N) {
if (N <= 1) return N;
int dp[2];
dp[0] = 0;
dp[1] = 1;
for (int i = 2; i <= N; i++) {
int sum = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = sum;
}
return dp[1];
}
};
//递归
class Solution {
public:
int fib(int N) {
if (N < 2) return N;
return fib(N - 1) + fib(N - 2);
}
};
70.爬楼梯
文章讲解：70.爬楼梯
视频讲解：带你学透动态规划-爬楼梯|LeetCode:70.爬楼梯）
状态：基础题
题意分析
如果对于一个n阶台阶，每次你可以爬 1 或 2 个台阶。有多少种不同的方法可以爬到楼顶。
如果台阶一共只有1阶，一共只有1种
如果台阶有2阶，一共有2种
如果台阶有3阶，一共有3种
如果台阶有4阶，一共有5种
本质上，当前台阶有几种方法，主要依赖于前两个状态。
其实这就是递推关系。这种递推关系可以用动态规划来解决。
动规五部曲
确定dp数组下标以及含义
dp[i]，达到i阶有dp[i]种方法。
确定递推公式
dp[i - 2]表示达到i-2阶有dp[i - 2]种方法
dp[i - 1]表示达到i-1阶有dp[i - 1]种方法
dp[i]表示达到i阶有dp[i]种方法
d p [ i ] = d p [ i − 2 ] + d p [ i − 1 ] dp[i] = dp[i-2]+dp[i-1] dp[i]=dp[i−2]+dp[i−1]
dp数组如何初始化
从递推公式可以看出，最重要的就是初始化数组的前几位
dp[0] = 1还是dp[0] = 0
因为我们dp[2] = 2，从递推公式出发，dp[0]应该初始化成1。同时题目中也说过，n为正整数
在代码随想录的代码中，是不初始化0的，而是直接初始化dp[2]和dp[1]
确定遍历顺序
从前向后遍历即可
打印DP数组
用于debug
其实本质上，从上文论述的规律可以看出，其实本题就是一个斐波那契数列
扩展题
一步可以走m个台阶，爬n阶的楼梯有多少种方法。
词题可以用完全背包的思路来解决。
CPP代码
//还是只维护两个数组
class Solution {
public:
int climbStairs(int n) {
if (n <= 3) return n;
int dp[2];
dp[0] = 1; dp[1] = 2;
for (int i = 3; i <= n; ++i) {
int cur = dp[0] + dp[1];
dp[0] = dp[1];
dp[1] = cur;
}
return dp[1];
}
};
746.使用最小花费爬楼梯
文章讲解：746.使用最小花费爬楼梯
视频讲解：动态规划开更了！| LeetCode：746. 使用最小花费爬楼梯
状态：首先靠感觉得出dp[i]的含义，然后数学归纳了一下，大概得出了递推公式，然后代码修修改改通过。
在题目描述中，我们可以选择从下标为0或下标为1的台阶开始爬楼梯。
思路
dp数组含义
想给出结论，本题仍然只需要一个一维的dp数组，其下标记录我们到达了哪个台阶，其中的值就是体力的最小消耗。
以上的推导都是怎么来的呢？
要求的是爬到楼顶，那么我们dp数组应该得用下标来表示我们爬的位置，看是不是到楼顶了；
然后我们要求一个最小消耗，那么我们的dp数组刚好可以存到达该层的一个消耗，刚好逻辑就闭环。
综上：
dp[i]表示到达i位置所需要的花费为dp[i]
递推公式
本题中我们要求的就是dp[i]，那么如何跳到dp[i]呢？我们可以从dp[i-1]跳一步到dp[i]，也可以从dp[i-2]跳两步到dp[i]。
如果从dp[i-1]跳到dp[i]的话，所需要的花费是dp[i-1] + cost[i-1]
如果从dp[i-2]跳到dp[i]的话，所需要的花费是dp[i-2] + cost[i-2]
dp[i]表示到达i位置所需要的花费为dp[i]
显然递推公式为： d p [ i ] = m i n ( d p [ i − 1 ] + c o n s t [ i − 1 ] , d p [ i − 2 ] + c o n s t [ i − 2 ] ) dp[i] = min(dp[i-1] + const[i-1], dp[i-2] + const[i-2]) dp[i]=min(dp[i−1]+const[i−1],dp[i−2]+const[i−2])
初始化
很明显，本题只要初始化了dp[1]和dp[0]就可以把递推公式打通了。
//题意表明了，可以选择从0层或者从第1层开始跳
dp[0] = 0; //到达0位置最小花费为0
dp[1] = 0; //到底1位置最小花费也是0. 因为我们可以选择嘛
遍历顺序
从零往后去遍历
因为是模拟台阶，而且dp[i]由dp[i-1]dp[i-2]推出，所以是从前到后遍历cost数组就可以了。
打印dp数组
打印出来看是不是和我们预想的一样
CPP代码
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp(cost.size() + 1);
dp[0] = 0; // 表示的是直接上到台阶0
dp[1] = 0; // 直接上到台阶1
for (int i = 2; i <= cost.size(); i++) {
dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
}
return dp[cost.size()];
}
};
//只维护两个数字
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
int dp0 = 0;
int dp1 = 0;
for (int i = 2; i <= cost.size(); i++) {
int dpi = min(dp1 + cost[i - 1], dp0 + cost[i - 2]);
dp0 = dp1; // 记录一下前两位
dp1 = dpi;
}
return dp1;
}
};