网站pv uv,漳州城乡建设局网站,派代网,百度 营销怎么收费目录
一、理论基础
1. 大纲
2. 动态规划的解题步骤
二、LeetCode 题目
1. 斐波那契数
2. 爬楼梯
3. 使用最小花费爬楼梯
4. 不同路径
5. 不同路径 II
6. 整数拆分
7. 不同的二叉搜索树 一、理论基础
1. 大纲 动态规划#xff0c;英文#xff1a;Dynamic Programm…目录
一、理论基础
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) 0F(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] 0dp[1] 0; class Solution {
public:int minCostClimbingStairs(vectorint 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) {vectorvectorint dp(m, vectorint(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) {vectorint 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;vectorvectorint buff(m, vectorint(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] 一定为 1dp[0][j] 也同理。但如果 (i, 0) 这条边有了障碍之后障碍之后包括障碍都是走不到的位置了所以障碍之后的 dp[i][0] 应该还是 初始值 0。 // 方法一二维数组保存
class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {// 二维数组保存int m obstacleGrid.size();int n obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] 1 || obstacleGrid[0][0] 1) return 0;vectorvectorint buff(m, vectorint(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(vectorvectorint obstacleGrid) {int m obstacleGrid.size();int n obstacleGrid[0].size();if (obstacleGrid[m - 1][n - 1] 1 || obstacleGrid[0][0] 1) //如果在起点或终点出现了障碍直接返回0return 0;vectorvectorint dp(m, vectorint(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(vectorvectorint obstacleGrid) {// 二维数组保存if (obstacleGrid[0][0] 1) return 0;int m obstacleGrid.size();int n obstacleGrid[0].size();vectorvectorint buff(m, vectorint(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 表示 对应为下标数字时 拆分的最大值可以由之前下标数组最大值得出vectorint 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;vectorint 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];}
};
