参考

代码随想录

理论基础

什么是动态规划

动态规划（Dynamic Programming，DP）是运筹学的一个分支，是求解决策过程最优化的过程。

基本思想

动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式 。

动态规划的解题步骤

1. 确定dp数组（dp table）以及下标的含义
2. 确定递推公式
3. dp数组如何初始化
4. 确定遍历顺序
5. 举例推导dp数组

题目一：LeetCode 509. 斐波那契数

递归

class Solution {
public:int fib(int n) {if(n <= 1)  return n;return fib(n - 1) + fib(n - 2);}
};

动态规划

1. 确定dp数组及其下标的含义
   第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]得到，因此只能从前往后遍历
5. 举例推导dp数组
   0 1 1 2 3 5 8 13 21…

代码实现如下：

class Solution {
public:int fib(int n) {if(n <= 1)  return n;vector 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];}
};

因为最后只需要dp[n]，因此dp数组不需要申请那么大，只要大小为3即可。

class Solution {
public:int fib(int n) {if(n <= 1)  return n;vector dp(3);//初始化dp[0] = 0,dp[1] = 1;for(int i = 2; i <= n; i++){dp[2] = dp[0] + dp[1];dp[0] = dp[1];dp[1] = dp[2];}return dp[2];}
};

题目二：LeetCode 70. 爬楼梯

根据题目意思，每次可以爬1阶或2阶台阶，因此对于第i阶台阶，可以从第i-1阶或第i-2阶爬上去，所以其实这还是斐波那契数列。

1. 确定dp数组及其下标的含义
   dp[i]为爬到第i个台阶有多少种方法
2. 确定递推公式
   爬到第i个台阶有两种方式，一个是从第i-1个台阶，另一个是从第i-2个台阶，因此不难确定递推公式为：dp[i] = dp[i-1] + dp[i-2]
3. dp数组初始化

dp[1] = 1;
dp[2] = 2;

这里dp[0]没有初始化，也不必初始化，因为用不到，况且dp[0]是模糊的，初始化0还是1？按照递归关系要初始化为1，但感觉有些勉强了，没必要，这里就不做初始化了。

4. 确定遍历顺序
   dp[i]由dp[i-1]和dp[i-2]推出，因此要从前往后遍历。
5. 举例推导dp数组
   1，2，3，5，8，13，…（注意下标从1开始）

代码实现如下：

class Solution {
public:int climbStairs(int n) {if(n <= 2)  return n;vector 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];}
};

可以发现，这个题本质上还是斐波那契数列。

题目三：LeetCode 746. 使用最小花费爬楼梯

1. 确定dp数组及其下标的含义
   dp[i]为爬到第i个台阶的最低花费
2. 确定递推公式

• 从第i-1个台阶爬到第i个台阶，dp[i] = dp[i-1] + cost[i-1]
• 从第i-2个台阶爬到第i个台阶，dp[i] = dp[i-2] + cost[i-2]
  因此dp数组定义为最低花费，所以dp[i]应该取这两者中的较小值，即

dp[i] = min(dp[i-1] + cost[i-1], dp[i-2] + cost[i-2])

3. dp数组初始化
   题目中给出“你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯”，因此在第0阶和第1阶的时候是没有花费的，所以dp[0] = 0, dp[1] = 0.
4. 确定遍历顺序
   第i个台阶的最低花费需要由第i-1个台阶和第i-2个台阶共同确定，因此要从前往后遍历
5. 推导dp数组
   以cost = [1,100,1,1,1,100,1,1,100,1]为例，dp数组的值为0，0，1，2，2，3，3，4，4，5，6

代码实现如下：

class Solution {
public:int minCostClimbingStairs(vector& cost) {vector dp(cost.size() + 1);dp[0] = 0;dp[1] = 0;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.back();}
};