动态规划part01
文章参考来源代码随想录
理论基础
适用范围：
如果某一问题有很多重叠子问题，使用动态规划是最有效的。
与贪心算法的区别：
动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的
状态转移公式（递推公式）是很重要，但动规不仅仅只有递推公式。
动规五部曲：
1.确定dp数组（dp table）以及下标的含义
2.确定递推公式
3.dp数组如何初始化
4.确定遍历顺序
5.举例推导dp数组
debug：
找问题的最好方式就是把dp数组打印出来，看看究竟是不是按照自己思路推导的
以及反思：
- 这道题目我举例推导状态转移公式了么？
- 我打印dp数组的日志了么？
- 打印出来了dp数组和我想的一样么？
509. 斐波那契数
动规五部曲：
1.确定dp数组以及下标的含义：第i个位置的斐波那契值为dp[i]；
2.确定递推公式：dp[i]=dp[i-1]+dp[i-2];
3.dp数组如何初始化:斐波那契数列初始前两个位置为0,1；
4.确定遍历顺序：因为递推是从前往后因此这里从前往后遍历；
5.举例推导dp数组：
按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：
0 1 1 2 3 5 8 13 21 34 55
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];
}
};特别情况 ：
当n小于等于1时这里不用递归公式，因为这两个本来就有初始化的，所以直接输出即可
优化：
我们只需要维护两个数值就可以了，不需要记录整个序列，因此这里可以用sum来记录dp[i-1]+dp[i-2]的值，然后更新dp[i-2]为dp[i-1]，dp[i-1]为sum。
70. 爬楼梯
动规五部曲：
1.确定dp数组以及下标的含义：能爬到第i个位置的方法为dp[i]；
2.确定递推公式：dp[i]=dp[i-1]+dp[i-2];
3.dp数组如何初始化:前两个台阶能爬的方法初始化为1,2；
4.确定遍历顺序：因为递推是从前往后因此这里从前往后遍历；
5.举例推导dp数组：
当n=3时，应该是第一个台阶方法数+第二个的，结果是1+2=3成立
dp数组0 1 2 3
class Solution {
public:
int climbStairs(int n) {
if(n==1)return n;
vector<int>dp(n+1);
dp[1]=1;
dp[2]=2;
for(int i=3;i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
};特别情况 ：
当n等于1时这里不用递归公式，因为第一个台阶只有一种方法，所以直接输出即可
优化：
我们只需要维护两个数值就可以了，不需要记录整个序列，因此这里可以用sum来记录dp[i-1]+dp[i-2]的值，然后更新dp[i-2]为dp[i-1]，dp[i-1]为sum。
746. 使用最小花费爬楼梯
动规五部曲：
1.确定dp数组以及下标的含义：能爬到第i个位置并由此向上爬的最小花费为dp[i]（包括该位置的花费，因为这里我们要cost是不包括最后一个台阶的）；
2.确定递推公式： dp[i]=min(dp[i-1],dp[i-2])+cost[i];
3.dp数组如何初始化:能爬到前两个台阶（0,1）并由此向上爬的最小花费初始化为cost[0]，cost[1]；
4.确定遍历顺序：因为递推是从前往后因此这里从前往后遍历；
5.举例推导dp数组：
具体cost具体分析
拿示例2：cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1] ，来模拟一下dp数组的状态变化，如下
需要注意的点 ：
这里dp大小初始化为cost大小，爬到最后一个台阶的最小花费实际上就是爬到倒数第一个或者第二个台阶并由此向上爬的最小花费
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int>dp(cost.size());
dp[0]=cost[0];
dp[1]=cost[1];
for(int i=2;i<cost.size();i++){
dp[i]=min(dp[i-1],dp[i-2])+cost[i];
}
return min(dp[cost.size()-1],dp[cost.size()-2]);
}
};