背包问题是一类经典的动态规划题目，01背包问题是其中最为基础的一个。本文结合多个题解，给出01背包问题的直观解释，以及多种求解方法的代码实现。...对于背包问题，你先解决小背包（子背包）问题，再逐步解决原来的问题。 比较有趣的一句话是：每个动态规划都从一个网格开始。...（所以学会网格的推导至关重要，而有些题解之所以写的不好，就是因为没有给出网格的推导过程，或者说，没有说清楚为什么要”这样“设计网格。本文恰是解决了我这方面长久以来的困惑！）...[i]+dp[k-weight[i]](旧值), dp[k](旧值)) 为什么说这里必须反向遍历来更新dp[]数组的值呢？...dp[k] = Math.max(dp[k - weight[i]] + value[i], dp[k]); } } return dp[W]; } 为什么可以这样简化呢
62 不同路径 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。...机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ img 例如，上图是一个7 x 3 的网格。有多少可能的路径？...机器人试图达到网格的右下角（在下图中标记为“Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ img 网格中的障碍物和空位置分别用 1 和 0 来表示。...考虑网格中有障碍物，那这个条件对于我们解决该题而言有什么含义呢？...c 初始为 1， 大家可以考虑下为什么？
不同路径II 问题描述： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。...机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？...解决方案 该问题是之前问题的简化版，解法相同，直接给出转移方程和baseline。...[i][j + 1]; } } return dp[0][0]; } } 不同路径III 问题描述： 在二维网格 grid 上，有 4 种类型的方格...请注意，起始和结束方格可以位于网格中的任意位置。
机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？...机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 1 和 0 来表示。...，只不过有些地方有「障碍物」，只要在「状态转移」上稍加修改就可解决。...最小路径和 题目链接 -> Leetcode -64.最小路径和 Leetcode -64.最小路径和 题目：给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小...那么我们分析状态转移的时候会有一个问题：那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
就像做递归的题，看的懂答案，但下不了手，关于递归的，我之前也写过一篇套路的文章，如果对递归不大懂的，强烈建议看一看：为什么你学不会递归，告别递归，谈谈我的经验 对于动态规划，春招秋招时好多题都会用到动态规划...(1)、定义数组元素的含义 按我上面的步骤说的，首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有...下面这道题也不难，比上面的难一丢丢，不过也是非常类似 问题描述 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。...和上面的差不多，不过是算最优路径和，这是 leetcode 的第64题：https://leetcode-cn.com/problems/minimum-path-sum/ 还是老样子，可能有些人都看烦了...(将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解答 还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决
一、题目描述======不同路径一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。...机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。问总共有多少条不同的路径？...又是需要你从小到大一步一步解决问题。我都说道这里了如果你还不知道用动态规划来做，我也不知道该咋说了。当然了，解决问题是有很多种的。...笔者这里只是建议通过动态规划来解决问题或者说来加强我们对动态规划的熟悉度。并不是说此题非动归不可转移方程首先，我们考虑下本题是寻找路径的问题，我们直接接触了没有维度的概念，只有执行与方式的不同。...不清楚的可以在主页中找到爬楼梯章节查看具体逻辑升级--上面的动态规划解决的太完美了，因为我们不需要考虑复杂的情况，只需要三板斧就可以解决了。而且执行效率真的没得说。美中不足的是在内存消耗上有点不完美。
问题描述： 一些恶魔抓住了公主（P）并将她关在了地下城的右下角。地下城是由 M x N 个房间组成的二维网格。...有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数...例如，考虑到如下布局的地下城，如果骑士遵循最佳路径 右 -> 右 -> 下 -> 下，则骑士的初始健康点数至少为 7。...解决方案 该问题与不同路径问题相类似，不过不同路径问题从前往后dp或从后往前dp均可，该问题只能使用从后往前的动态规划。...定义一和二维网格同尺寸二维数组记做dp,其中dp[i] [j]表示从i, j位置出发到达终点最少需要的初始体力点数。
加载本地包下的文件和打包成jar文件的路径是不一样的，需要对路径进行调整。...如果要判断为本地文件还是jar包文件可以参考以下代码 String protocol = Aviator.class.getResource("").getProtocol(); if ("jar"...import java.util.List; import java.util.jar.JarEntry; import java.util.jar.JarFile; /** * 扫描包下路径...> superStrategy = String.class;//接口类class 用于过滤 可以不要 private List clazz = null; try { //此时jarEntryName为jar包中类的相对路径
(1)、定义数组元素的含义 按我上面的步骤说的，首先我们来定义 dp[i] 的含义，我们的问题是要求青蛙跳上 n 级的台阶总共由多少种跳法，那我们就定义 dp[i] 的含义为：跳上一个 i 级的台阶总共有...下面这道题也不难，比上面的难一丢丢，不过也是非常类似 问题描述 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。...和上面的差不多，不过是算最优路径和，这是 leetcode 的第64题：https://leetcode-cn.com/problems/minimum-path-sum/ 还是老样子，可能有些人都看烦了...由于机器人可以向下走或者向右走，所以有两种方式到达 一种是从 (i-1, j) 这个位置走一步到达 一种是从(i, j - 1) 这个位置走一步到达 不过这次不是计算所有可能路径，而是计算哪一个路径和是最小的...(将 'h' 替换为 'r') rorse -> rose (删除 'r') rose -> ros (删除 'e') 解答 还是老样子，按照上面三个步骤来，并且我这里可以告诉你，90% 的字符串问题都可以用动态规划解决
不同路径 II 题目地址： 不同路径 II 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。机器人每次只能向下或者向右移动一步。...机器人试图达到网格的右下角（在下图中标记为 “Finish”）。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径？ 网格中的障碍物和空位置分别用 1 和 0 来表示。...下降路径最小和 给你一个n x n的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和。 下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。...有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为负整数，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 0），要么包含增加骑士健康点数的魔法球（若房间里的值为正整数...那么我们分析状态转移的时候会有⼀个问题：那就是我们当前的健康点数还会受到后面的路径的影响。也就是从上往下的状态转移不能很好地解决问题。
动态规划可以说算法中最优秀的算法，因为在此介绍动态规划系列中的路径问题。 下面是对应的动态规划解决的路径问题总结： 62. 不同路径 63. 不同路径 II 64. 最小路径和 120....机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？...当然，你也可以对二维dp数组压缩成一维数组，来代表每一行或者每一列的路径数之和，可以对空间进一步的优化。...最小路径和 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。...初始化dp所有的元素均为0，在网格的第一行和第一列的所有路径和应该都是固定的，因为都是向右或者向下移动。
/ 本文，Jungle将采用动态规划，一举解决上述问题。...那么对于数组元素dp[i][j]代表什么呢？——机器人走到网格(i,j)时的最小路径值。...总体上思路是一样的，区别在于边界条件。 （1）明确数组元素代表的含义 dp[i][j]——走到网格(i,j)时的最小路径值。...下降路径最小和 给定一个方形整数数组 A，我们想要得到通过 A 的下降路径的最小和。下降路径可以从第一行中的任何元素开始，并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列。...（1）明确数组元素代表的含义 dp[i][j]——走到网格(i,j)时的最小路径和。
2、如何判断一个问题是动态规划问题，即如何看出是否存在重叠子问题。 3、为什么经常看到将dp数组的大小设置为n + 1而不是n。...那现在改变思路，借助最优子结构解决最值问题，再回过头解决最大分数差问题，是不是就高效多了？...但毕竟斐波那契数列问题太简单了，实际的动态规划问题比较复杂，比如二维甚至三维的动态规划，当然也可以画递归树，但不免有些复杂。...再看dp数组，你当然也可以定义dp[i][j]存储s1[0..i]和s2[0..j]的编辑距离，但问题是 base case 怎么搞？索引怎么能是 -1 呢？...四、dp数组的遍历方向 我相信读者做动态规问题时，肯定会对dp数组的遍历顺序有些头疼。
（2）寻找递推关系，务必考虑特殊情况下的递推关系 以一维数组为例，明确了dp[i]的含义了，那么dp[i]和dp[i+1]是什么关系？可以通过怎样的关系式将二者关联起来？...根据前述的三大步骤： （1）明确数组含义 dp[i][j]代表什么？——机器人走到网格(i,j)总共有多少种路径。...类似于第62题，根据前述的三大步骤： （1）明确数组含义 dp[i][j]——机器人走到网格(i,j)总共有多少种路径。...m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。...这道题其实也是个最短路径问题，那么同样，我们使用二维数组。 （1）明确数组含义 dp[i][j]——走到网格(i,j)时的最短路径值（包括该网格的路径值）。
.不同路径 : https://leetcode.cn/problems/unique-paths 一个机器人位于一个 m x n 网格 的 左上角 （起始点在下图中标记为 “Start” ）。...机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？...一、问题分析 ---- 动态规划 可以解决 三类问题 : 求最值 : 最大值 , 最小值 等 ; 大规模问题的结果 由 小规模问题 的计算结果 相加 大规模问题的结果 由 小规模问题 的计算结果...: public class Solution { /** * 不同路径 * @param m 网格行数 * @param n 网格列数 * @return...m - 1 , n - 1 ) 位置的方案数 从 (i , j + 1) 走到 ( m - 1 , n - 1 ) 位置的方案数 之和 ; 这里可以得到依赖关系 : dp[i][j] = dp[i+1
不同路径 一、题目描述： 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。 机器人每次只能向下或者向右移动一步。...机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。 问总共有多少条不同的路径？...然后我又想了动态规划的方法，这道题应该是一道典型的动态规划题目，我们将起点到每一个点的路径设置为到其左边那个点的路径条数加上到其上面那个点的路径条数之和。...所以有动态规划转移方程： f(x,y) = f(x-1)(y) + f(x)(y-1) 不过需要注意的是，我们要将f(x,0)和f(0,y)的值设置为1。很好就可以理解，确实到他们的路径只有一条！...做题的时候是不是一次通过的，遇到了什么问题，需要注意什么细节？ 不是一次通过的，注意什么时候用m，什么时候用n。我刚开始在此处有些失误！
题目描述 一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。...问总共有多少条不同的路径？ ? 例如，上图是一个7 x 3 的网格。有多少可能的路径？ 说明：m 和 n 的值均不超过 100。...示例 1: 输入: m = 3, n = 2 输出: 3 解释: 从左上角开始，总共有 3 条路径可以到达右下角。...思路 这是一道典型的适合使用动态规划解决的题目，它和爬楼梯等都属于动态规划中最简单的题目， 因此也经常会被用于面试之中。 读完题目你就能想到动态规划的话，建立模型并解决恐怕不是难事。...1 : dp[i - 1][j] + dp[i][j - 1]; // 转移方程 } } return dp[m][n]; 由于dp[i][j] 只依赖于左边的元素和上面的元素，因此空间复杂度可以进一步优化
，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的，因此每个元素对应的最小路径和即为对应的路径上的数字总和。...对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值...由于每个元素对应的最小路径和与其相邻元素对应的最小路径和有关，因此可以使用动态规划求解。...最后得到 dp[m−1][n−1] 的值即为从网格左上角到网格右下角的最小路径和。...空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。
动态规划 此题是典型的动态规划问题，由于路径的方向只能是向下或向右，因此网格的第一行的每个元素只能从左上角元素开始向右移动到达，网格的第一列的每个元素只能从左上角元素开始向下移动到达，此时的路径是唯一的...对于不在第一行和第一列的元素，可以从其上方相邻元素向下移动一步到达，或者从其左方相邻元素向右移动一步到达，元素对应的最小路径和等于其上方相邻元素与其左方相邻元素两者对应的最小路径和中的最小值加上当前元素的值...创建二维数组 dp，与原始网格的大小相同，dp[i][j] 表示从左上角出发到 (i, j) 位置的最小路径和。显然，dp[0][0]=grid[0][0]。...最后得到 dp[m − 1][n − 1] 的值即为从网格左上角到网格右下角的最小路径和。...空间复杂度可以优化，例如每次只存储上一行的 dp 值，则可以将空间复杂度优化到 O(n)。
思考 挺像游戏的一道题，首先只能向下或向右移动，所以每个格子可以由上面或左边的格子移动而来，很自然想到可以用动态规划解决。...逆向思维 为什么从结果倒推，DP 判断条件就没有后效性了呢？ 先回忆一下从左上角出发的情况，为什么除了最低初始 HP 外还要记录当前 HP？...那为什么从右下角，以终为始的考虑就可以少判断一个条件了呢？首先最低初始 HP 我们肯定要判断的，因为答案要的就是这个，那当前 HP 呢？当前 HP 重要吗？...(...pathResults), 1) } } return dp[0][0] }; 逆向思维为什么就能减少当前 HP（或者说路径和，或者说所有之前节点的影响）判断呢？...总结 该题很容易想到使用动态规划解决，但因为目标是求最低的初始健康点需求，所以按照勇者路径走的话，后续未探索的路径会影响到目标，所以我们需要从公主角度反向寻找勇者，才可以保证动态规划的每个判断点都只考虑一个影响因素
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
