动态规划理论基础
动态规划题单：
什么是动态规划
动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的，
例如：有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。
但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。所以贪心解决不了动态规划的问题。
动态规划的解题步骤
对于动态规划问题，Carl将拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了！
- 确定dp数组（dp table）以及下标的含义
- 确定递推公式
- dp数组如何初始化
- 确定遍历顺序
- 举例推导dp数组
如何Debug
做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。
拷问自己：
- 这道题目我举例推导状态转移公式了么？
- 我打印
dp数组的日志了么？ - 打印出来了
dp数组和我想的一样么？
509.斐波那契数
思路
从斐波那契数列，正式入手动态规划！
我提出几个疑问：斐波那契数列我可以递归做，为什么要动态规划？动态规划是递归吗？具体是什么含义？
听我细细道来：
与动态规划相关的知识我不多说。首先，递归不是动态规划，动态规划是递推，计算的数据（状态）会保留在dp中，而递推更类似于暴力遍历，这也导致了动态规划效率大大高于递归；动态规划->当前状态的选择来源于之前状态，视因有果。
题解
class Solution {
public:
int fib(int n) {
//dp[i]代表第F(n) 初始化
//因为仅仅和前两个状态有关，可优化
// vector<int> dp = {0,1};
// if(n<2)return dp[n];
// for(int i = 2;i<=n;i++)
// {
// dp.push_back(dp[i-1]+dp[i-2]);
// }
// return dp[n];
int dp[3] = {0,1,0};
if(n<2)return dp[n];
//for与下标无关，仅代表循环次数
for(int i = 0;i<n-1;i++)
{
dp[2] = dp[0]+dp[1];
dp[0] = dp[1];//蕴含着更新迭代
dp[1] = dp[2];
}
return dp[2];
}
};
70.爬楼梯
思路
华为面试手撕题目，没了猴子，却多了感悟
本题开始着重加强理解（赋予）dp数组所代表的含义：dp是状态，是题目所求的所有状态的集合。
在本题中，dp[n]代表着爬n阶的方法（数量），动态规划呀，当前状态与之前状态有关，之前的状态是？n-2与n-1。
牢牢记住是数量所以dp[n] = dp[n-2]+dp[n-1]，不需要再加其他。
题解
class Solution {
public:
int climbStairs(int n) {
int dp[3] = {1,2,0};
if(n<=2)return dp[n-1];
for(int i = 0;i<n-2;i++)
{
dp[2] = dp[0]+dp[1];
dp[0] = dp[1];
dp[1] = dp[2];
}
return dp[2];
// if(n == 2)return 2;
// else if(n == 1)return 1;
// return climbStairs(n-2)+climbStairs(n-1);
}
};
746.使用最小花费爬楼梯
题目链接：746.使用最小花费爬楼梯
文档讲解：代码随想录
状态：轻松AC
思路
遇到因果问题考虑动态规划，本题主要考察两点：递推公式、dp数组初始化
初始化时注意读题即可，没什么难度
题解
class Solution {
public:
int minCostClimbingStairs(vector<int>& cost) {
vector<int> dp = {0,0};
for(int i = 2;i<=cost.size();i++)
{
dp.push_back(min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]));
}
return dp.back();
}
};