一、动态规划思考模板
1、构造dp[]数组，想清楚dp[]数组的具体含义。
2、确定本题目的递推公式
3、初始化dp[]数组
4、确定数组遍历顺序
5、利用初始化后的dp数组结合递推公式推导dp数组，看是否符合题意要求
二、题目示例
1、斐波那契数列-- 一维动态规划
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) = 1 F(n) = F(n - 1) + F(n - 2)，其中 n > 1 给你n ，请计算 F(n) 。
示例 1：
- 输入：2
- 输出：1
- 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：
- 输入：3
- 输出：2
- 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：
- 输入：4
- 输出：3
- 解释：F(4) = F(3) + F(2) = 2 + 1 = 3
提示：
- 0 <= n <= 30
第一步、构造dp数组
vector<int>dp(n + 1); //创建动态规划数组
明确dp数组的含义--dp[i]表示第i个数的大小
第二步、写出递推公式
dp[i] = dp[i - 1] + dp[i - 2]; //递推公式
通常根据题目中给出的信息进行模拟和找规律 ，最终找到递推公式
第三步、初始化dp数组
//初始化 dp[0] = 0; dp[1] = 1;
根据题目需要进行数组初始化
第四步、确定数组的遍历顺序
for(int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; //递推公式 }
斐波那契数列--我们选择从前向后遍历
第五步、我们自己按照初始化与递推公式进行手动模拟 或 打印dp数组，检查正确与否
最后，呈上完整代码
class Solution { public: int fib(int n) { if(n <= 1) return n; //特判，否则for循环部位报错 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]; } };
2、爬楼梯问题 -- 一维动态规划
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
- 输入： 2
- 输出： 2
- 解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
- 输入： 3
- 输出： 3
- 解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
爬楼梯问题属于经典的动态规划类问题，我们要从上文提到的动态规划五部曲来思考。
第一步、构造dp数组
vector<int>dp(n + 1);
我们首先构造一维dp数组
第二步、写出递推公式
dp[i] = dp[i - 1] + dp[i - 2];
我们首先发现本题的递推公式与上题斐波那契数列的递推公式一致，那么我们如何推导的呢？
假如n=3，即我们需要爬三层楼梯才能登上楼顶。
由于我们每次爬楼梯只能爬 一层 或 两层，所以肯定不可能从0层直接爬到三层。
如果想到达三层，只存在两种可能性--1、从一层处 爬两层楼梯到达三层，2、从二层处 爬一层楼梯到达三层。
但是我们不可能一开始就在 一层 或者 二层，我们的初始位置在零层，所以我们还要用同样的思路从零层 爬到 一层 或 二层。
故 dp[3] = dp[2] + dp[1]。 以此类推---dp[i] = dp[i - 1] + dp[i - 2]。
第三步、初始化dp数组
dp[1] = 1; dp[2] = 2;
根据递推公式我们可以将dp数组初始化。
第四步、确定数组的遍历顺序
for(int i = 3; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; }
因为我们必须 从最底层 一层层 向上爬楼梯，所以我们是从前向后遍历。
第五步、自己手动模拟或者打印dp数组进行检查正确与否。
最后、呈上本题完整代码
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]; } };
3、不同路径问题 -- 二维动态规划
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
问总共有多少条不同的路径？
示例 1：
- 输入：m = 3, n = 7
- 输出：28
示例 2：
- 输入：m = 2, n = 3
- 输出：3
解释： 从左上角开始，总共有 3 条路径可以到达右下角。
- 向右 -> 向右 -> 向下
- 向右 -> 向下 -> 向右
- 向下 -> 向右 -> 向右
示例 3：
- 输入：m = 7, n = 3
- 输出：28
示例 4：
- 输入：m = 3, n = 3
- 输出：6
提示：
- 1 <= m, n <= 100
- 题目数据保证答案小于等于 2 * 10^9
与爬楼梯问题不同的是，不同路径问题 是一个 图论中也经常出现的问题，在一个二维图表中，我们应使用二维动态规划。
第一步、构造dp数组，不过是二维数组。
vector<vector<int>>dp(m, vector<int>(n, 0)); //二维动归数组
m为行数， n为列数。dp[][]表示到达坐标(i,j)的位置共有多少种不同的走法。
第二部、写出递推公式。
dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //递推公式
题目中规定：我们只能向下走 或者 向右走。由此可得到递推公式。
第三步、初始化dp数组
for(int i = 0; i < n; i++) { dp[0][i] = 1; //初始化行 } for(int i = 0; i < m; i++) { dp[i][0] = 1; //初始化列 }
第一行 和 第一列 上的所有位置 若想到达则只有1条路径可走，要么一直向右，要么一直向下走。
第四步、确定数组的遍历顺序
for(int i = 1; i < m; i++) { for(int j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //递推公式 } }
遍历除 第一行 和 第一列 之外的每一个位置-->最终推出到达终点位置的路径数目总和。
第五步、同理打印dp或手动模拟检查正确与否。
