动态规划入门详解

动态规划（Dynamic Programming，简称DP）是一种算法思想，它将问题分解为更小的子问题，然后将子问题的解存起来，避免重复计算。

所以动态规划中每一个状态都是由上一个状态推导出来的，这一点就区别于贪心，贪心没有状态推导。

并且动态规划问题可以分为很多种类，如线性DP、区间DP、背包DP、树形DP、状态压缩DP、数位DP、计数型DP、递推型DP、博弈型DP和记忆化搜索等。每种类型都有其特定的问题模型和解决方法。如线性DP通常通过处理一维数组或字符串，区间DP处理二维区间，背包问题处理物品的选择问题。

这说的的都是啥玩意啊？怎么字都认识？连在一起，就都不懂了？

我们来看下，网上比较流行的一个例子：

• A ： "1+1+1+1+1+1+1+1 =？"
• A ： "上面等式的值是多少"
• B ： 计算 "8"
• A : 在上面等式的左边写上 "1+" 呢？
• A : "此时等式的值为多少"
• B : 很快得出答案 "9"
• A : "你怎么这么快就知道答案了"
• A : "只要在8的基础上加1就行了"
• A : "所以你不用重新计算，因为你记住了第一个等式的值为8!动态规划算法也可以说是 '记住求过的解来节省时间'"

有一道题，挺适合启蒙思想的-青蛙跳阶问题
这里我们只是带入思想，不给出题解，相信大家，在看完本文后，肯定能解决。

leetcode原题：一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 10 级的台阶总共有多少种跳法。

• 要想跳到第10级台阶，要么是先跳到第9级，然后再跳1级台阶上去;要么是先跳到第8级，然后一次迈2级台阶上去。
• 同理，要想跳到第9级台阶，要么是先跳到第8级，然后再跳1级台阶上去;要么是先跳到第7级，然后一次迈2级台阶上去。
• 要想跳到第8级台阶，要么是先跳到第7级，然后再跳1级台阶上去;要么是先跳到第6级，然后一次迈2级台阶上去。

所以可以推导，得出这么一个结论：

f（10） = f（9）+f(8)
f (9)  = f(8) + f(7)
f (8)  = f(7) + f(6)
...
f(3) = f(2) + f(1)f(n) = f(n-1) + f(n-2)

而 f(n) = f(n-1) + f(n-2); 又叫做递推公式，这也是动态规划的核心。

Carl对动态规划，总结成了5步，如果这5步都能合理的掌握并运用，相当于神功大成\(￣︶￣*\))

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

好啦，接下来举例子：

斐波那契数

斐波那契数 （通常用 F(n) 表示）形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n) 。

示例 1：

输入：n = 2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1

示例 2：

输入：n = 3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2

示例 3：

输入：n = 4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3

提示：

• 0 <= n <= 30

这道题目，作例子，再合适不过了。

在示例1~3中：递归公式，给的在明显不过了。

f(n) = f(n-1) + f(n-2)；

咱们在开篇时已经讲过：动态规划是 将问题分解为更小的子问题，然后将子问题的解存起来，避免重复计算。

重点是存起来，所以就需要用到数组喽，如下：

arr[0]=0;
arr[1]=1;
for(int i=2; i<=n; ++i){arr[i]=arr[i-1]+arr[i-2];
}

这就是递推，本题的总代码如下：

class Solution {
public:int fib(int n) {// 排除意外if(n==0) return 0;else if(n==1) return 1;vector<int> arr(n+1);arr[0]=0;arr[1]=1;for(int i=2; i<=n; ++i){arr[i]=arr[i-1]+arr[i-2];}return arr[n];}
};

相信到这里，大家已经基本对动态规划有了大致了解，接下来可以安心开刷了( •̀ ω •́ )✧

题目：

 2、爬楼梯-（解析）-线性dp入门

 3、使用最小花费爬楼梯-（解析）-线性dp入门

 4、不同路径-（解析）-区间dp入门

 5、不同路径 II-（解析）-区间dp入门

 6、整数拆分-（解析）-需要考虑，数字拆成几个？需要有一定推理能力

 7、不同的二叉搜索树-（解析）-需要有能力，跳出数字约束，进入宏观层面

2、爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

• 1 <= n <= 45

class Solution {
// 线性dp基础练习
public:int climbStairs(int n) {if(n==1) return 1;if(n==2) return 2;vector<int> res(n+1);res[1]=1;res[2]=2;for(int i=3; i<=n; ++i){res[i] = res[i-1] + res[i-2];} return res[n]; }
};

3、使用最小花费爬楼梯

给你一个整数数组 cost ，其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

示例 1：

输入：cost = [10,15,20]
输出：15
解释：你将从下标为 1 的台阶开始。
- 支付 15 ，向上爬两个台阶，到达楼梯顶部。
总花费为 15 。

示例 2：

输入：cost = [1,100,1,1,1,100,1,1,100,1]
输出：6
解释：你将从下标为 0 的台阶开始。
- 支付 1 ，向上爬两个台阶，到达下标为 2 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 4 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 6 的台阶。
- 支付 1 ，向上爬一个台阶，到达下标为 7 的台阶。
- 支付 1 ，向上爬两个台阶，到达下标为 9 的台阶。
- 支付 1 ，向上爬一个台阶，到达楼梯顶部。
总花费为 6 。

提示：

• 2 <= cost.length <= 1000
• 0 <= cost[i] <= 999

class Solution {
// 稍稍具有一点，推导能力的线性dp
public:int minCostClimbingStairs(vector<int>& cost) {vector<int> res(cost.size()+1);res[0] = 0;res[1] = 0;for(int i=2; i<=cost.size(); ++i){res[i] = min(res[i-1]+cost[i-1], res[i-2]+cost[i-2]);}return res[cost.size()];}
};

4、不同路径

一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。

问总共有多少条不同的路径？

示例 1：

输入：m = 3, n = 7
输出：28

示例 2：

输入：m = 3, n = 2
输出：3
解释：
从左上角开始，总共有 3 条路径可以到达右下角。
1. 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右
3. 向下 -> 向右 -> 向下

示例 3：

输入：m = 7, n = 3
输出：28

示例 4：

输入：m = 3, n = 3
输出：6

提示：

• 1 <= m, n <= 100
• 题目数据保证答案小于等于 2 * 109

class Solution {
// 入门的区间dp
public:int uniquePaths(int m, int n) {vector<vector<int>> res(m,vector<int>(n));for(int i=0; i<n; ++i) res[0][i]=1;for(int j=0; j<m; ++j) res[j][0]=1;for(int i=1; i<m; ++i){for(int j=1; j<n; ++j){res[i][j]=res[i-1][j]+res[i][j-1];}}return res[m-1][n-1];}
};

5、不同路径 II

给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角（即 grid[0][0]）。机器人尝试移动到 右下角（即 grid[m - 1][n - 1]）。机器人每次只能向下或者向右移动一步。

网格中的障碍物和空位置分别用 1 和 0 来表示。机器人的移动路径中不能包含 任何 有障碍物的方格。

返回机器人能够到达右下角的不同路径数量。

测试用例保证答案小于等于 2 * 109。

示例 1：

输入：obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
输出：2
解释：3x3 网格的正中间有一个障碍物。
从左上角到右下角一共有 2 条不同的路径：
1. 向右 -> 向右 -> 向下 -> 向下
2. 向下 -> 向下 -> 向右 -> 向右

示例 2：

输入：obstacleGrid = [[0,1],[0,0]]
输出：1

提示：

• m == obstacleGrid.length
• n == obstacleGrid[i].length
• 1 <= m, n <= 100
• obstacleGrid[i][j] 为 0 或 1

class Solution {
// 入门的区间dp
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int row = obstacleGrid.size();int col = obstacleGrid[0].size();vector<vector<int>> res(row,vector<int>(col, 0));for(int i=0; i<row; ++i){if(obstacleGrid[i][0]==1) break;res[i][0] = 1;} for(int i=0; i<col; ++i){if(obstacleGrid[0][i]==1) break;res[0][i] = 1;}for(int i=1; i<row; ++i){for(int j=1; j<col; ++j){if(obstacleGrid[i][j]==1) continue;res[i][j] = res[i-1][j] + res[i][j-1];}}return res[row-1][col-1];}
};

6、整数拆分

给定一个正整数 n ，将其拆分为 k 个 正整数 的和（ k >= 2 ），并使这些整数的乘积最大化。

返回 你可以获得的最大乘积 。

示例 1:

输入: n = 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1。

示例 2:

输入: n = 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36。

提示:

• 2 <= n <= 58

class Solution {// 本题的思考角度在于，一个数字，能被拆几次。（2~n此，因为拆的次数多了，所以才有无限可能...
public:int integerBreak(int n) {vector<int> dp(n+1, 0);dp[0] = dp[1]=0;for(int i=2; i<=n; ++i){for(int j=1; j<i; ++j){dp[i] = max(dp[i], max(j*(i-j),j*dp[i-j]));      }}return dp[n];}
};

7、不同的二叉搜索树

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

• 1 <= n <= 19

class Solution {// 实现宏观抽象，不要看具体的数据，跳过数据看规律。
public:int numTrees(int n) {vector<int> dp(n+1,0);dp[0]=1;for(int i=1; i<=n; ++i){for(int j=0; j<i; ++j){dp[i] += dp[i-1-j]*dp[j];}    }//   for(int i : dp) cout<<i<<endl;return dp[n];}
};

需要有，跳出数据，从宏观逻辑分析的能力。

---

借鉴博客：

1、动态规划理论基础

2、看一遍就理解：动态规划详解

---