《代码随想录》刷题打卡day28：动态规划part01

1. 动态规划（Dynamic Programming）理论

（1）什么是动态规划

如果某一问题有很多重叠子问题，使用动态规划是最有效的。

所以动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的。

**例如：**有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划中dp[j]是由dp[j-weight[i]]推导出来的，然后取max(dp[j], dp[j - weight[i]] + value[i])。

但如果是贪心呢，每次拿物品选一个最大的或者最小的就完事了，和上一个状态没有关系。

所以贪心解决不了动态规划的问题。

（2）动态规划解题步骤

1. 确定dp数组（dp table）以及下标的含义

2. 确定递推公式

3. dp数组如何初始化

4. 确定遍历顺序

5. 举例推导dp数组

   做动规的题目，写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍，心中有数，确定最后推出的是想要的结果。

   然后再写代码，如果代码没通过就打印dp数组，看看是不是和自己预先推导的哪里不一样。

   如果打印出来和自己预先模拟推导是一样的，那么就是自己的递归公式、初始化或者遍历顺序有问题了。

   如果和自己预先模拟推导的不一样，那么就是代码实现细节有问题。

2.题目打卡

【509.斐波那契数】

动规五部曲：

这里我们要用一个一维dp数组来保存递归的结果

1. 确定dp数组以及下标的含义

dp[i]的定义为：第i个数的斐波那契数值是dp[i]

2. 确定递推公式

为什么这是一道非常简单的入门题目呢？

因为题目已经把递推公式直接给我们了：状态转移方程 dp[i] = dp[i - 1] + dp[i - 2];

3. dp数组如何初始化

题目中把如何初始化也直接给我们了，如下：

dp[0] = 0; dp[1] = 1;

4. 确定遍历顺序

从递归公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，dp[i]是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

5. 举例推导dp数组

按照这个递推公式dp[i] = dp[i - 1] + dp[i - 2]，我们来推导一下，当N为10的时候，dp数组应该是如下的数列：

0 1 1 2 3 5 8 13 21 34 55

如果代码写出来，发现结果不对，就把dp数组打印出来看看和我们推导的数列是不是一致的。

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]; } };

【70.爬楼梯】

class Solution { // dp[i]表示到当前楼层所有的方法数，dp[i] = dp[i-1] + do[i-2] public: int climbStairs(int n) { if(n <= 2) 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]; } };

【746.使用最小花费爬楼梯】

class Solution { //dp[i]表示上到i台阶所需要的最低花费 public: int minCostClimbingStairs(vector<int>& cost) { int height = cost.size(); vector<int> dp(height+1); dp[0] = 0; dp[1] = 0; for(int i = 2; i <= height; i++){ dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2]); } return dp[height]; } };