杨伟丽 郑州做网站百度号码认证平台首页
目录
一、理论基础
1. 大纲
2. 动态规划的解题步骤
二、LeetCode 题目
1. 斐波那契数
2. 爬楼梯
3. 使用最小花费爬楼梯
4. 不同路径
5. 不同路径 II
6. 整数拆分
7. 不同的二叉搜索树
一、理论基础
1. 大纲
动态规划，英文：Dynamic Programming，简称 DP，如果 某一问题有很 多重叠子问题，使用动态规划 是最有效的。
动态规划中 dp[j] 是由 dp[j-weight[i]] 推导出来的，然后取 max(dp[j], dp[j - weight[i]] + value[i])。
2. 动态规划的解题步骤
- 确定 dp 数组（dp table）以及下标的含义。
- 确定 递推公式。
- dp 数组 如何初始化。
- 确定 遍历顺序。
- 举例 推导 dp 数组。
二、LeetCode 题目
1. 斐波那契数
https://leetcode.cn/problems/fibonacci-number/submissions/569810951/
https://leetcode.cn/problems/fibonacci-number/submissions/569810951/
斐波那契数，通常用 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理解：
① dp[i] 的定义为：第 i 个数的 斐波那契数值是 dp[i]。
② 状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]。
③ 初始化。
dp[0] = 0; dp[1] = 1;
// 写法一：
class Solution {
public:int fib(int n) {if (n < 2) return n;return fib(n - 1) + fib(n - 2);}
};// 写法二：
class Solution {
public:int fib(int n) {int f0 = 0, f1 = 1;int num;if (n == 1) return f1;if (n == 0) return f0;for (int i = 1; i < n; i++) {num = f0 + f1;f0 = f1;f1 = num;}return num;}
};2. 爬楼梯
https://leetcode.cn/problems/climbing-stairs/description/https://leetcode.cn/problems/climbing-stairs/description/
假设你正在爬楼梯。需要
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 阶理解：
① dp[i]： 爬到第i层楼梯，有dp[i]种方法。
② dp[i] = dp[i - 1] + dp[i - 2] ：首先是 dp[i - 1]，上 i-1 层楼梯，有 dp[i - 1] 种方法，那么再一步跳一个台阶不就是 dp[i] 了。还有就是 dp[i - 2]，上 i-2 层楼梯，有 dp[i - 2] 种方法，那么再一步跳两个台阶不就是 dp[i] 了。
③ dp[0] = 1，相当于直接站在楼顶。
class Solution {
public:int climbStairs(int n) {if (n <= 2) return n;int dp[2] = {1, 2};for (int i = 2; i < n; i++) {int num = dp[0] + dp[1];dp[0] = dp[1];dp[1] = num;}return dp[1];}
};3. 使用最小花费爬楼梯
https://leetcode.cn/problems/min-cost-climbing-stairs/description/https://leetcode.cn/problems/min-cost-climbing-stairs/description/
给你一个整数数组
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 。理解：
① 到达第 i 台阶所花费的最少体力为 dp[i]。
② dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
可以有 两个途径得到 dp[i]，一个是dp[i-1] 一个是 dp[i-2]。
dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]。
dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]。
③ dp[0] = 0，dp[1] = 0;
class Solution {
public:int minCostClimbingStairs(vector<int>& cost) {if (cost.size() == 1) return cost[0];if (cost.size() == 0) return 0;int dp[2] = {0};for (int i = 1; i < cost.size(); i++) {int costmin = min(dp[0] + cost[i - 1], dp[1] + cost[i]);dp[0] = dp[1];dp[1] = costmin;}return dp[1];}
};4. 不同路径
https://leetcode.cn/problems/unique-paths/description/https://leetcode.cn/problems/unique-paths/description/
一个机器人位于一个
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理解：
① dp[i][j] ：表示从（0 ，0）出发，到 (i, j) 有 dp[i][j] 条不同的路径。
② dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为 dp[i][j] 只有这两个方向过来。
③ dp[i][0] 一定都是 1，因为从 (0, 0) 的位置到 (i, 0) 的路径只有一条，那么 dp[0][j] 也同理。
// 方法一：（二维数组实现）
class Solution {
public:int uniquePaths(int m, int n) {vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m; i++) dp[i][0] = 1;for (int j = 0; j < n; j++) dp[0][j] = 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];}}return dp[m - 1][n - 1];}
};// 方法二：（一维数组实现）
class Solution {
public:int uniquePaths(int m, int n) {vector<int> dp(n);for (int i = 0; i < n; i++) dp[i] = 1;for (int j = 1; j < m; j++) {for (int i = 1; i < n; i++) {dp[i] += dp[i - 1];}}return dp[n - 1];}
};// 方法三：
class Solution {
public:int uniquePaths(int m, int n) {if (m == 0 || n == 0) return 1;vector<vector<int>> buff(m, vector<int>(n, 0));buff[0][0] = 1;for (int row = 0; row < m; row++) {for (int col = 0; col < n; col++) {if (row == 0 && col == 0) continue;else if (row == 0) buff[0][col] = buff[0][col - 1];else if (row > 0 && col == 0) buff[row][0] = buff[row - 1][0];else buff[row][col] = buff[row - 1][col] + buff[row][col - 1];// cout << buff[row][col] << " ";}// cout << endl;}return buff[m - 1][n - 1];}
};5. 不同路径 II
https://leetcode.cn/problems/unique-paths-ii/description/https://leetcode.cn/problems/unique-paths-ii/description/
给定一个
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理解：
① dp[i][j] ：表示从（0 ，0）出发，到 (i, j) 有 dp[i][j] 条不同的路径。
② 从 (0, 0) 的位置到 (i, 0) 的路径只有一条，所以 dp[i][0] 一定为 1，dp[0][j] 也同理。但如果 (i, 0) 这条边有了障碍之后，障碍之后（包括障碍）都是走不到的位置了，所以障碍之后的 dp[i][0] 应该还是 初始值 0。
// 方法一：（二维数组保存）
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {// 二维数组保存int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) return 0;vector<vector<int>> buff(m, vector<int>(n, 0));buff[0][0] = 1;for (int row = 0; row < m; row++) {for (int col = 0; col < n; col++) {if ((row == 0 && col == 0) || obstacleGrid[row][col] == 1) continue;else if (row == 0) buff[row][col] = buff[row][col - 1];else if (col == 0) buff[row][0] = buff[row - 1][0];else buff[row][col] = buff[row - 1][col] + buff[row][col - 1];}}return buff[m - 1][n - 1];}
};// 方法二：（一维数组保存）
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {int m = obstacleGrid.size();int n = obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] == 1 || obstacleGrid[0][0] == 1) //如果在起点或终点出现了障碍，直接返回0return 0;vector<vector<int>> dp(m, vector<int>(n, 0));for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;for (int i = 1; i < m; i++) {for (int j = 1; j < n; j++) {if (obstacleGrid[i][j] == 1) continue;dp[i][j] = dp[i - 1][j] + dp[i][j - 1];}}return dp[m - 1][n - 1];}
};// 方法三：
class Solution {
public:int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {// 二维数组保存if (obstacleGrid[0][0] == 1) return 0;int m = obstacleGrid.size();int n = obstacleGrid[0].size();vector<vector<int>> buff(m, vector<int>(n, 0));buff[0][0] = 1;for (int row = 0; row < m; row++) {for (int col = 0; col < n; col++) {if ((row == 0 && col == 0) || obstacleGrid[row][col] == 1) continue;else if (row == 0) buff[row][col] = buff[row][col - 1];else if (col == 0) buff[row][0] = buff[row - 1][0];else buff[row][col] = buff[row - 1][col] + buff[row][col - 1];}}return buff[m - 1][n - 1];}
};6. 整数拆分
https://leetcode.cn/problems/integer-break/description/https://leetcode.cn/problems/integer-break/description/
给定一个正整数
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。理解：
①dp[i]：分拆数字 i，可以得到的 最大乘积为 dp[i]。
②有两种渠道得到 dp[i]：一个是 j * (i - j) 直接相乘。一个是 j * dp[i - j]，相当于是拆分 (i - j)。j 是从 1 开始遍历，拆分 j 的情况，在遍历 j 的过程中其实都计算过了。那么从 1 遍历 j，比较 (i - j) * j 和 dp[i - j] * j 取最大的。递推公式：dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));
③这里只初始化 dp[2] = 1，从 dp[i] 的定义来说，拆分数字 2，得到的最大乘积是 1。
class Solution {
public:int integerBreak(int n) {// dp 表示 对应为下标数字时 拆分的最大值，可以由之前下标数组最大值得出vector<int> dp(n + 1, 0);dp[2] = 1; // 数字代表拆分的数字for (int i = 3; i <= n; i++) {for (int j = 1; j <= i / 2; j++) {// 从 1 开始拆，有拆和不拆两种选择dp[i] = max(dp[i], max((i - j) * j, dp[i - j] * j));}}return dp[n];}
};7. 不同的二叉搜索树
https://leetcode.cn/problems/unique-binary-search-trees/description/https://leetcode.cn/problems/unique-binary-search-trees/description/
给你一个整数
n，求恰由n个节点组成且节点值从1到n互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5示例 2：
输入：n = 1
输出：1理解：
① dp[i] ： 1 到 i 为节点组成的二叉搜索树的个数为 dp[i]。
② dp[i] += dp[j - 1] * dp[i - j]; ，j - 1 为 j 为头结点左子树节点数量，i - j 为以 j 为头结点右子树节点数量。
③ dp[以 j 为头结点左子树节点数量] * dp[以 j 为头结点右子树节点数量] 中以 j 为头结点左子树节点数量为 0，也需要 dp[以 j 为头结点左子树节点数量] = 1， 否则乘法的结果就都变成 0 了。所以初始化 dp[0] = 1。
class Solution {
public:int numTrees(int n) {if (n == 1) return 1;vector<int> dp(n + 1, 0);dp[0] = 1, dp[1] = 1;for (int i = 2; i <= n; i++) {for (int j = 0; j < i; j++) {dp[i] += dp[j] * dp[i - j - 1];}}return dp[n];}
};