网站模板 在哪购买,教育机构网站源码,wordpress 置顶 函数,扁平化设计风格的网站1.动态规划
动态规划#xff0c;英文#xff1a;Dynamic Programming#xff0c;简称DP#xff0c;如果某一问题有很多重叠子问题#xff0c;使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的#xff0c;这一点就区分于贪心#xff0c…1.动态规划
动态规划英文Dynamic Programming简称DP如果某一问题有很多重叠子问题使用动态规划是最有效的。
所以动态规划中每一个状态一定是由上一个状态推导出来的这一点就区分于贪心贪心没有状态推导而是从局部直接选最优的。
例如有N件物品和一个最多能背重量为W 的背包。第i件物品的重量是weight[i]得到的价值是value[i] 。每件物品只能用一次求解将哪些物品装入背包里物品价值总和最大。
动态规划中dp[j]是由dp[j-weight[i]]推导出来的然后取max(dp[j], dp[j - weight[i]] value[i])。
但如果是贪心呢每次拿物品选一个最大的或者最小的就完事了和上一个状态没有关系。
所以贪心解决不了动态规划的问题。
动态规划五步曲
确定dp数组dp table以及下标的含义确定递推公式dp数组如何初始化确定遍历顺序举例推导dp数组
为什么要先确定递推公式然后在考虑初始化呢
因为一些情况是递推公式决定了dp数组要如何初始化 做动规的题目写代码之前一定要把状态转移在dp数组的上具体情况模拟一遍心中有数确定最后推出的是想要的结果。
然后再写代码如果代码没通过就打印dp数组看看是不是和自己预先推导的哪里不一样。
如果打印出来和自己预先模拟推导是一样的那么就是自己的递归公式、初始化或者遍历顺序有问题了。
如果和自己预先模拟推导的不一样那么就是代码实现细节有问题。
代码都已经和题解一模一样了为什么通过不了呢
发出这样的问题之前其实可以自己先思考这三个问题
这道题目我举例推导状态转移公式了么我打印dp数组的日志了么打印出来了dp数组和我想的一样么
如果这灵魂三问自己都做到了基本上这道题目也就解决了或者更清晰的知道自己究竟是哪一点不明白是状态转移不明白还是实现代码不知道该怎么写还是不理解遍历dp数组的顺序。
2.斐波那契数
力扣题目链接(opens new window)
斐波那契数通常用 F(n) 表示形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始后面的每一项数字都是前面两项数字的和。也就是 F(0) 0F(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
public class Fibonacci_number {public int fib2(int n) {//公共方法接受一个整数参数 n返回斐波那契数列的第 n 项。if (n 1) return n;//如果 n 小于或等于 1直接返回 n因为斐波那契数列的前两个数分别是 0 和 1。int[] dp new int[n 1];//创建一个长度为 n 1 的数组 dp为了存储从 F(0) 到 F(n) 的所有斐波那契数。初始化 dp[0] 为 0dp[1] 为 1这是斐波那契数列的前两项。dp[0] 0;dp[1] 1;for (int index 2; index n; index){//for 循环从索引 2 迭代到 n每次迭代计算下一个斐波那契数并存储在 dp[index] 中。dp[index] dp[index - 1] dp[index - 2];//在每次迭代中根据斐波那契数列的递推公式 F(n) F(n - 1) F(n - 2)计算 dp[index] 的值即 dp[index] 等于 dp[index - 1] 与 dp[index - 2] 的和。}//通过逐步计算数组 dp 中会依次存储斐波那契数列的前 n 1 项的值。return dp[n];//循环结束后dp[n] 中存储的就是斐波那契数列的第 n 项的值将其返回。}
}
假设 n 5
因为 n 5 1不满足 if (n 1) 的条件继续执行。创建数组 dp长度为 6n 1并初始化 dp[0] 0dp[1] 1。进入 for 循环 当 index 2 时 dp[2] dp[1] dp[0] 1 0 1。当 index 3 时 dp[3] dp[2] dp[1] 1 1 2。当 index 4 时 dp[4] dp[3] dp[2] 2 1 3。当 index 5 时 dp[5] dp[4] dp[3] 3 2 5。循环结束返回 dp[5]即 5这就是斐波那契数列的第 5 项的值。
通过这种动态规划的方法代码可以高效地计算出斐波那契数列的任意一项。
3.爬楼梯
力扣题目链接(opens new window)
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢
注意给定 n 是一个正整数。
示例 1
输入 2输出 2解释 有两种方法可以爬到楼顶。 1 阶 1 阶2 阶
示例 2
输入 3输出 3解释 有三种方法可以爬到楼顶。 1 阶 1 阶 1 阶1 阶 2 阶2 阶 1 阶
public class Climbing_Stairs {public int climbStairs1(int n) {//接受一个整数参数 n表示台阶的数量返回爬上 n 级台阶的不同方法数。int[] dp new int[n 1];//创建一个长度为 n 1 的数组 dp用于存储从第0个台阶到第 n 个台阶的爬法数量。dp[0] 1;//表示在地面上第0个台阶只有1种方式啥都不做。dp[1] 1;//表示到达第1个台阶只有1种方式即向上爬1个台阶。for (int i 2; i n; i) {//for 循环从第 2 级台阶开始迭代到第 n 级台阶。每次迭代计算到达当前台阶的不同方法数并存储在 dp[i] 中。到达第 i 个台阶的方法数等于到达第 i-1 个台阶的方法数加上到达第 i-2 个台阶的方法数因为可以从第 i-1 个台阶走1步上来或者从第 i-2 个台阶走2步上来。dp[i] dp[i - 1] dp[i - 2];}return dp[n];//循环结束后dp[n] 中存储的就是爬上 n 级台阶的不同方法数将其返回。}
}
假设 n 3
创建数组 dp长度为 4n 1并初始化 dp[0] 1dp[1] 1。进入 for 循环 当 i 2 时 dp[2] dp[1] dp[0] 1 1 2。这表示到达第 2 级台阶有 2 种方法从第 0 级走 2 步上来或者从第 1 级走 1 步上来。当 i 3 时 dp[3] dp[2] dp[1] 2 1 3。这表示到达第 3 级台阶有 3 种方法从第 1 级走 2 步上来或者从第 2 级走 1 步上来。循环结束返回 dp[3]即 3这就是爬上 3 级台阶的不同方法数。
这种动态规划的方法通过逐步计算每一级台阶的方法数最终得出爬上 n 级台阶的总方法数逻辑清晰且计算效率较高。
4.使用最小花费爬楼梯
力扣题目链接(opens new window)
给你一个整数数组 cost 其中 cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用。一旦你支付此费用即可选择向上爬一个或者两个台阶。
你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。
请你计算并返回达到楼梯顶部的最低花费。 提示
cost 的长度范围是 [2, 1000]。cost[i] 将会是一个整型数据范围为 [0, 999] 。
public class Climbing_Stairs_with_Minimum_Cost {public int minCostClimbingStairs2(int[] cost) {//接受一个整数数组 cost 作为参数cost 数组中的每个元素表示爬上对应台阶所需的花费。方法返回爬上楼梯顶部的最小花费。int[] dp new int[cost.length];//创建一个长度为 cost.length 的数组 dp用于存储从第0个台阶到第 cost.length - 1 个台阶的最小花费,dp[i] 表示到达第 i 个台阶的最小花费。dp[0] cost[0];//因为题目设定可以从第 0 个台阶或第 1 个台阶开始。从起始位置到达第 0 个台阶只有一种方式就是直接踏上第 0 个台阶而踏上这个台阶所需的花费就是 cost[0]所以将 dp[0] 初始化为 cost[0]。表示到达第 0 个台阶的最小花费就是 cost[0]。dp[1] cost[1];//对于第 1 个台阶从起始位置到达它也只有一种方式就是直接踏上第 1 个台阶所需的花费就是 cost[1]。所以把 dp[1] 初始化为 cost[1]。表示到达第 1 个台阶的最小花费就是 cost[1]。for (int i 2; i cost.length; i) {//从第 2 个台阶开始迭代到第 cost.length - 1 个台阶。每次迭代计算到达当前台阶的最小花费并存储在 dp[i] 中。到达第 i 个台阶的最小花费等于到达第 i-1 个台阶的最小花费加上当前台阶的花费或者到达第 i-2 个台阶的最小花费加上当前台阶的花费取两者的最小值。dp[i] Math.min(dp[i - 1], dp[i - 2]) cost[i];}return Math.min(dp[cost.length - 1], dp[cost.length - 2]);//最终返回 dp[cost.length - 1] 和 dp[cost.length - 2] 的最小值因为到达顶部可以是从倒数第二步或倒数第三步爬上来的。}
}
假设输入的 cost 数组为 [10, 15, 20]
初始化 dp 数组 dp[0] 10dp[1] 15。进入 for 循环 当 i 2 时 dp[2] Math.min(dp[1], dp[0]) cost[2]dp[2] Math.min(15, 10) 20 10 20 30。循环结束后计算并返回结果 return Math.min(dp[2], dp[1]) Math.min(30, 15) 15。
所以爬上楼梯顶部的最小花费是 15。通过这种动态规划的方法代码能够有效地计算出爬上楼梯的最小花费。
5.不同路径
力扣题目链接(opens new window)
一个机器人位于一个 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
public class different_paths {public int uniquePaths2(int m, int n) {//接受两个整数参数m和n分别表示网格的行数和列数。方法返回从网格左上角到右下角的不同路径数量。int[] dp new int[n];//创建一个长度为 n 的一维整数数组 dpdp[j] 表示到达当前行的第 j 个格子的不同路径数量。Arrays.fill(dp, 1);//将dp数组的所有元素初始化为1这是因为在第一行中到达任何一个格子都只有一种方式即从左边的格子直接移动过来因为只能向右或向下移动。for (int i 1; i m; i ) {//外层 for 循环从第二行索引 i 1开始遍历到第 m - 1 行。对于每一行我们要计算该行中每个格子的不同路径数量。for (int j 1; j n; j ) {//内层 for 循环从第二列索引 j 1开始遍历到第 n - 1 列。对于每一个格子 (i, j)。到达该格子的路径数量 dp[j]dp[j] dp[j - 1];//由于只能向右或向下移动到达当前格子 (i, j) 的路径可以来自于上方的格子 (i - 1, j) 或者左方的格子 (i, j - 1)。因为我们是逐行计算的当计算到第 i 行的格子时dp[j - 1] 就表示了到达当前行前一列的格子 (i, j - 1) 的路径数量而 dp[j] 在这之前保存的是上一行同一列的格子 (i - 1, j) 的路径数量。所以dp[j] dp[j - 1] 表示将到达当前行前一列的格子的路径数量累加到当前格子的路径数量上从而得到到达当前格子 (i, j) 的总路径数量。在计算第 i 行的格子时dp 数组的状态是上一行计算完成后的结果。}}return dp[n - 1];//当所有行和列都计算完毕后dp[n - 1] 中存储的就是到达右下角格子即第 m - 1 行第 n - 1 列的不同路径数量将其返回。}
}
假设 m 3n 2
初始化 dp 数组 dp [1, 1]因为第一行的每个格子都只有一种到达方式。进入外层 for 循环 当 i 1第二行 进入内层 for 循环 当 j 1 dp[1] dp[0]此时 dp[0] 1dp[1] 1所以 dp[1] 1 1 2。此时 dp [1, 2]。外层 for 循环结束返回 dp[n - 1]即 dp[1] 2。
这表示在一个 3 x 2 的网格中从左上角到右下角有 2 条不同的路径。通过这种动态规划的方法代码能够高效地计算出不同路径的数量。
6.不同路径 II
力扣题目链接(opens new window)
一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为“Start” 。
机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为“Finish”。
现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 网格中的障碍物和空位置分别用 1 和 0 来表示。
示例 1 输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]]输出2 解释3x3 网格的正中间有一个障碍物。从左上角到右下角一共有 2 条不同的路径 向右 - 向右 - 向下 - 向下向下 - 向下 - 向右 - 向右
示例 2 输入obstacleGrid [[0,1],[0,0]]输出1
提示
m obstacleGrid.lengthn obstacleGrid[i].length1 m, n 100obstacleGrid[i][j] 为 0 或 1
public class different_pathsII {public int uniquePathsWithObstacles2(int[][] obstacleGrid) {//接受一个二维整数数组obstacleGrid作为参数表示网格其中1表示障碍物0表示空地。该方法返回从左上角到右下角的不同路径数量。int m obstacleGrid.length;//获取网格的行数m和列数n。int n obstacleGrid[0].length;int[] dp new int[n];//创建一个长度为 n 的一维整数数组 dpdp[j] 表示到达当前行的第 j 列格子的不同路径数量。for (int j 0; j n obstacleGrid[0][j] 0; j) {//初始化第一行的 dp 值。从左到右遍历第一行如果当前格子没有障碍物obstacleGrid[0][j] 0则到达该格子的路径数量为 1因为从左上角出发到第一行的非障碍物格子只有一种路径。一旦遇到障碍物后面的格子路径数就不再初始化保持默认的 0 值。dp[j] 1;}for (int i 1; i m; i) {//外层 for 循环从第二行i 1开始遍历到第 m - 1 行。对于每一行我们要计算该行中每个格子的不同路径数量。for (int j 0; j n; j) {//内层 for 循环遍历当前行的每一列从 j 0 到 j n - 1。if (obstacleGrid[i][j] 1) {//如果当前格子 (i, j) 有障碍物obstacleGrid[i][j] 1那么到达该格子的路径数量为 0因为无法通过有障碍物的格子。dp[j] 0;} else if (j ! 0) {//如果当前格子没有障碍物并且不是当前列的第一个格子即j ! 0由于只能从上方或左方移动到当前格子在处理到第 i 行时dp[j - 1] 表示到达当前行前一列格子 (i, j - 1) 的路径数量。由于可以从 (i, j - 1) 直接移动到 (i, j)所以从 (i, j - 1) 到达 (i, j) 的路径数量就是 dp[j - 1]。dp[j] dp[j - 1];//通过 dp[j] dp[j - 1];就把从左边格子到达当前格子的路径数量累加到了 dp[j] 上。上方格子对 dp[j] 的贡献已经在之前的计算中被包含在 dp[j] 的初始值里了。具体来说在处理第 i 行的格子时dp[j] 在执行 dp[j] dp[j - 1]; 之前的值就是从第 i - 1 行同一列的格子即上方格子 (i - 1, j)到达当前格子 (i, j) 的路径数量。}}}return dp[n - 1];//当所有行和列都计算完毕后dp[n - 1] 中存储的就是到达右下角格子即第 m - 1 行第 n - 1 列的不同路径数量将其返回。}
}
[[0, 0, 0],[0, 1, 0],[0, 0, 0]
]初始化 m 3n 3dp [0, 0, 0]。初始化第一行 因为 obstacleGrid[0][0] 0dp[0] 1。因为 obstacleGrid[0][1] 0dp[1] 1。因为 obstacleGrid[0][2] 0dp[2] 1。此时 dp [1, 1, 1]。计算第二行 当 i 1 当 j 0obstacleGrid[1][0] 0dp[0] 保持不变为 1。当 j 1obstacleGrid[1][1] 1dp[1] 0。当 j 2obstacleGrid[1][2] 0dp[2] 由于 j! 0dp[2] dp[1]此时 dp[2] 1 0 1。此时 dp [1, 0, 1]。计算第三行 当 i 2 当 j 0obstacleGrid[2][0] 0dp[0] 保持不变为 1。当 j 1obstacleGrid[2][1] 0dp[1] dp[0]dp[1] 0 1 1。当 j 2obstacleGrid[2][2] 0dp[2] dp[1]dp[2] 1 1 2。此时 dp [1, 1, 2]。返回结果 返回 dp[n - 1]即 dp[2] 2。
所以从左上角到右下角有 2 条不同的路径。
7.整数拆分
力扣题目链接(opens new window)
给定一个正整数 n将其拆分为至少两个正整数的和并使这些整数的乘积最大化。 返回你可以获得的最大乘积。
示例 1:
输入: 2输出: 1解释: 2 1 1, 1 × 1 1。
示例 2:
输入: 10输出: 36解释: 10 3 3 4, 3 × 3 × 4 36。说明: 你可以假设 n 不小于 2 且不大于 58。
public class Integer_Partition {public int integerBreak1(int n) {//接受一个整数n作为参数并返回将其拆分后能得到的最大乘积。int[] dp new int[n1];//一个长度为n1的整型数组dp用于存储从1到n每个整数拆分后能得到的最大乘积。dp[i] 用于存储整数 i 拆分后能得到的最大乘积。dp[2] 1;//初始化dp[2]为1因为2是最小的可以拆分的数且2只能拆分为11乘积为1。for(int i 3; i n; i) {//从 3 开始遍历到 n因为 2 已经在前面初始化过了。对于每个 i我们要计算将其拆分后能得到的最大乘积。for(int j 1; j i-j; j) {//对于每个 i内层循环遍历所有可能的拆分数 jj 的取值范围是从 1 到 i - j。这样可以确保 j 和 i - j 都是正整数且它们的和为 i。dp[i] Math.max(dp[i], Math.max(j*(i-j), j*dp[i-j]));//对于每个i尝试所有可能的拆分方式计算j*(i-j)和j*dp[i-j]取两者中较大的值更新dp[i]。j*(i-j)表示将i拆分为j和i-j的乘积j*dp[i-j]表示将i拆分为j和剩余部分i-j的最大乘积。}//例如假设 i 4// 当 j 1 时j * (i - j) 1 * 3 3j * dp[i - j] 1 * dp[3]假设 dp[3] 2则 j * dp[i - j] 1 * 2 2Math.max(j * (i - j), j * dp[i - j]) 3。如果 dp[4] 初始值为 0那么 dp[4] Math.max(0, 3) 3。//当 j 2 时j * (i - j) 2 * 2 4j * dp[i - j] 2 * dp[2]假设 dp[2] 1则 j * dp[i - j] 2 * 1 2Math.max(j * (i - j), j * dp[i - j]) 4。此时 dp[4] Math.max(3, 4) 4。// 所以经过这一系列计算dp[4] 最终被更新为 4即整数 4 拆分后能得到的最大乘积。}return dp[n];//循环结束后dp[n] 中存储的就是将整数 n 拆分后能得到的最大乘积将其返回。}
}
假设 n 5
初始化 dp 数组dp[2] 1。当 i 3 内层循环 当 j 1j * (i - j) 1 * 2 2j * dp[i - j] 1 * dp[2] 1 * 1 1dp[3] Math.max(dp[3], Math.max(2, 1)) 2。当 i 4 内层循环 当 j 1j * (i - j) 1 * 3 3j * dp[i - j] 1 * dp[3] 1 * 2 2dp[4] Math.max(dp[4], Math.max(3, 2)) 3。当 j 2j * (i - j) 2 * 2 4j * dp[i - j] 2 * dp[2] 2 * 1 2dp[4] Math.max(dp[4], Math.max(4, 2)) 4。当 i 5 内层循环 当 j 1j * (i - j) 1 * 4 4j * dp[i - j] 1 * dp[4] 1 * 4 4dp[5] Math.max(dp[5], Math.max(4, 4)) 4。当 j 2j * (i - j) 2 * 3 6j * dp[i - j] 2 * dp[3] 2 * 2 4dp[5] Math.max(dp[5], Math.max(6, 4)) 6。
最终dp[5] 6即把 5 拆分后能得到的最大乘积是 6例如拆分为 2 3。
8.不同的二叉搜索树
力扣题目链接(opens new window)
给定一个整数 n求以 1 ... n 为节点组成的二叉搜索树有多少种
二叉搜索树
二叉搜索树Binary Search TreeBST也称为二叉排序树或二叉查找树是一种特殊的二叉树数据结构。它满足以下性质
节点值特性 对于树中的每个节点其左子树中的所有节点的值都小于该节点的值而其右子树中的所有节点的值都大于该节点的值。有序性 二叉搜索树的中序遍历会得到一个升序的序列。这一特性使得二叉搜索树在查找、插入和删除操作上具有较高的效率。
public class Different_Binary_Search_Trees {public int numTrees(int n) {//接受一个整数n作为参数表示节点的数量并返回可以形成的不同二叉搜索树的数量。int[] dp new int[n 1];//一个长度为n 1的整型数组dp用于存储从0到n个节点时不同二叉搜索树的数量。dp[0] 1;//初始化dp[0]和dp[1]。对于0个节点有一种空树的情况对于1个节点有一种单节点树的情况。dp[1] 1;for (int i 2; i n; i) {//外层 for 循环从 2 开始遍历到 n对于每个 i我们要计算有 i 个节点时不同二叉搜索树的数量。for (int j 1; j i; j) {//对于每个 i内层循环遍历从 1 到 i 的所有可能的根节点。这是因为在构建二叉搜索树时每个节点都可以作为根节点。dp[i] dp[j - 1] * dp[i - j];//对于每个i计算以j为根节点时的不同二叉搜索树的数量并将结果累加到dp[i]。这里dp[j - 1]表示左子树的不同二叉搜索树的数量因为左子树有 j - 1 个节点dp[i - j]表示右子树的不同二叉搜索树的数量因为右子树有 i - j 个节点。}//根据乘法原理以 j 为根节点的不同二叉搜索树的数量就是左子树的不同二叉搜索树数量乘以右子树的不同二叉搜索树数量。我们将以每个 j 作为根节点时的不同二叉搜索树的数量累加到 dp[i] 中这样遍历完所有的 j 后dp[i] 就得到了有 i 个节点时不同二叉搜索树的总数量。}//乘法原理是一个基本的计数原理。如果完成一件事需要n个步骤其中做第一步有m1种不同的方法做第二步有m2种不同的方法……做第n步有mn种不同的方法那么完成这件事一共有Nm1*m2*....*mn种不同的方法。return dp[n];//循环结束后dp[n] 中存储的就是有 n 个节点时不同二叉搜索树的数量将其返回。当以值为 j 的节点作为根节点时因为左子树节点的值都要小于根节点的值所以左子树的节点只能从值为 1 到 j - 1 的这些节点中选取那么左子树就恰好有 j - 1 个节点。在具有 i 个节点的二叉搜索树中当确定以值为 j 的节点作为根节点时右子树的节点数量为 i - j 个}
}
假设 n 3
初始化 dp 数组dp[0] 1dp[1] 1。当 i 2 内层循环 当 j 1dp[1] 1dp[0] 1dp[2] dp[0] * dp[1] 1 * 1 1。当 j 2dp[1] 1dp[0] 1dp[2] dp[1] * dp[0] 1 * 1 1所以 dp[2] 2。当 i 3 内层循环 当 j 1dp[0] 1dp[2] 2dp[3] dp[0] * dp[2] 1 * 2 2。当 j 2dp[1] 1dp[1] 1dp[3] dp[1] * dp[1] 1 * 1 1。当 j 3dp[2] 2dp[0] 1dp[3] dp[2] * dp[0] 2 * 1 2所以 dp[3] 5。
最终dp[3] 5即有 3 个节点时可以形成 5 种不同的二叉搜索树。
