商业网站建设方案,长春百度推广排名优化,wordpress 多站点 用户,四川餐饮培训学校排名1.不同路径 力扣 一个机器人位于一个 m x n 网格的左上角 #xff08;起始点在下图中标记为 “Start” #xff09;。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角#xff08;在下图中标记为 “Finish”#xff09;。 现在考虑网格中有障碍物。那么从…1.不同路径 力扣 一个机器人位于一个 m x n 网格的左上角 起始点在下图中标记为 “Start” 。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角在下图中标记为 “Finish”。 现在考虑网格中有障碍物。那么从左上角到右下角将会有多少条不同的路径 网格中的障碍物和空位置分别用 1 和 0 来表示。 示例 1 输入obstacleGrid [[0,0,0],[0,1,0],[0,0,0]] 输出2 解释3x3 网格的正中间有一个障碍物。 从左上角到右下角一共有 2 条不同的路径 1. 向右 - 向右 - 向下 - 向下 2. 向下 - 向下 - 向右 - 向右 示例 2 输入obstacleGrid [[0,1],[0,0]] 输出1 来源力扣LeetCode 链接https://leetcode.cn/problems/unique-paths-ii class Solution {
public:int uniquePathsWithObstacles(vectorvectorint obstacleGrid) {int robstacleGrid.size();int lobstacleGrid[0].size();vectorvectorint dp(r1,vectorint(l1));dp[1][0]1;for(int i1;ir;i){for(int j1;jl;j){if(obstacleGrid[i-1][j-1]0){dp[i][j]dp[i][j-1]dp[i-1][j]; }else {dp[i][j]0;}}}return dp[r][l];}
};
2.不同路径 力扣 一个机器人位于一个 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 来源力扣LeetCode 链接https://leetcode.cn/problems/unique-paths class Solution {
public:int uniquePaths(int m, int n) {//以某一处为结尾创建dp表vectorvectorint dp(m1,vectorint(n1));//初始化dp表//dp[0][1]1;dp[1][0]1;for(int i1;im;i){for(int j1;jn;j){dp[i][j]dp[i-1][j]dp[i][j-1];//递推公式}}return dp[m][n];}
};
3.礼物的最大价值 力扣 在一个 m*n 的棋盘的每一格都放有一个礼物每个礼物都有一定的价值价值大于 0。你可以从棋盘的左上角开始拿格子里的礼物并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值请计算你最多能拿到多少价值的礼物 示例 1: 输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物 来源力扣LeetCode 链接https://leetcode.cn/problems/li-wu-de-zui-da-jie-zhi-lcof class Solution {
public:int maxValue(vectorvectorint grid) {int mgrid.size();int ngrid[0].size();vectorvectorint arr(m1,vectorint(n1));//初始化求最大所以初始化最小vector默认初始//化为0for(int i1;im;i){for(int j1;jn;j){arr[i][j]max(arr[i-1][j],arr[i][j-1])grid[i-1][j-1];//递推公式}}return arr[m][n];}
};
4.下降路径最小和 力扣 给你一个 n x n 的 方形 整数数组 matrix 请你找出并返回通过 matrix 的下降路径 的 最小和 。 下降路径 可以从第一行中的任何元素开始并从每一行中选择一个元素。在下一行选择的元素和当前行所选元素最多相隔一列即位于正下方或者沿对角线向左或者向右的第一个元素。具体来说位置 (row, col) 的下一个元素应当是 (row 1, col - 1)、(row 1, col) 或者 (row 1, col 1) 。 示例 1 输入matrix [[2,1,3],[6,5,4],[7,8,9]] 输出13 解释如图所示为和最小的两条下降路径 示例 2 输入matrix [[-19,57],[-40,-5]] 输出-59 解释如图所示为和最小的下降路径 来源力扣LeetCode 链接https://leetcode.cn/problems/minimum-falling-path-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 5.最小路径和 力扣 给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。 说明每次只能向下或者向右移动一步。 示例 1 输入grid [[1,3,1],[1,5,1],[4,2,1]] 输出7 解释因为路径 1→3→1→1→1 的总和最小。 示例 2 输入grid [[1,2,3],[4,5,6]] 输出12 来源力扣LeetCode 链接https://leetcode.cn/problems/minimum-path-sum class Solution {
public:int minFallingPathSum(vectorvectorint matrix) {int nmatrix.size();vectorvectorint dp(n1,vectorint(n2,INT_MAX));//创建dp表并初始化为最大值for(int i0;in2;i) dp[0][i]0;for(int i1;in;i){for(int j1;jn;j){dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))matrix[i-1][j-1];//递推公式}}int retINT_MAX;for(int i0;in;i)retmin(ret,dp[n][i]);//找最小return ret;}
};
class Solution {
public:int minPathSum(vectorvectorint grid) {int rgrid.size();int lgrid[0].size();vectorvectorint dp(r1,vectorint(l1,INT_MAX));//创建dp表并初始化找最小初始化为最大dp[0][1]dp[1][0]0;//由于有两种走法所以要求drid[0][0]的上方和左边的为最小数0for(int i1;ir;i){for(int j1;jl;j){dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];//地推公式}}return dp[r][l];//返回值}
};
6.地下城游戏 力扣 恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。 骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。 有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。 为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。 返回确保骑士能够拯救到公主所需的最低初始健康点数。 注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 示例 1 输入dungeon [[-2,-3,3],[-5,-10,1],[10,30,-5]] 输出7 解释如果骑士遵循最佳路径右 - 右 - 下 - 下 则骑士的初始健康点数至少为 7 。 示例 2 输入dungeon [[0]] 输出1 来源力扣LeetCode 链接https://leetcode.cn/problems/dungeon-game class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {int rdungeon.size();int ldungeon[0].size();vectorvectorint dp(r1,vectorint(l1,INT_MAX));//创建dp表初始化dp[r][l - 1] dp[r - 1][l] 1;for(int ir-1;i0;i--){for(int jl-1;j0;j--){dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j];//填表递推公式if(dp[i][j]0)dp[i][j]1;}}return dp[0][0];//返回值}
}
文章转载自： http://www.morning.xzsqb.cn.gov.cn.xzsqb.cn http://www.morning.c7627.cn.gov.cn.c7627.cn http://www.morning.krtky.cn.gov.cn.krtky.cn http://www.morning.hnzrl.cn.gov.cn.hnzrl.cn http://www.morning.hsrpr.cn.gov.cn.hsrpr.cn http://www.morning.pnbls.cn.gov.cn.pnbls.cn http://www.morning.qdxwf.cn.gov.cn.qdxwf.cn http://www.morning.wfhnz.cn.gov.cn.wfhnz.cn http://www.morning.smdiaosu.com.gov.cn.smdiaosu.com http://www.morning.fykqh.cn.gov.cn.fykqh.cn http://www.morning.kgmkl.cn.gov.cn.kgmkl.cn http://www.morning.wscfl.cn.gov.cn.wscfl.cn http://www.morning.bbtn.cn.gov.cn.bbtn.cn http://www.morning.plqhb.cn.gov.cn.plqhb.cn http://www.morning.nggbf.cn.gov.cn.nggbf.cn http://www.morning.mqxrx.cn.gov.cn.mqxrx.cn http://www.morning.sqqdy.cn.gov.cn.sqqdy.cn http://www.morning.yqlrq.cn.gov.cn.yqlrq.cn http://www.morning.bncrx.cn.gov.cn.bncrx.cn http://www.morning.sbjbs.cn.gov.cn.sbjbs.cn http://www.morning.gbfck.cn.gov.cn.gbfck.cn http://www.morning.ctxt.cn.gov.cn.ctxt.cn http://www.morning.amlutsp.cn.gov.cn.amlutsp.cn http://www.morning.jcnmy.cn.gov.cn.jcnmy.cn http://www.morning.ltffk.cn.gov.cn.ltffk.cn http://www.morning.nwgkk.cn.gov.cn.nwgkk.cn http://www.morning.bswxt.cn.gov.cn.bswxt.cn http://www.morning.lmfxq.cn.gov.cn.lmfxq.cn http://www.morning.nynyj.cn.gov.cn.nynyj.cn http://www.morning.ytbr.cn.gov.cn.ytbr.cn http://www.morning.stflb.cn.gov.cn.stflb.cn http://www.morning.vvbsxm.cn.gov.cn.vvbsxm.cn http://www.morning.kjtdy.cn.gov.cn.kjtdy.cn http://www.morning.ljglc.cn.gov.cn.ljglc.cn http://www.morning.wfpmt.cn.gov.cn.wfpmt.cn http://www.morning.hlmkx.cn.gov.cn.hlmkx.cn http://www.morning.dmnqh.cn.gov.cn.dmnqh.cn http://www.morning.bpmnq.cn.gov.cn.bpmnq.cn http://www.morning.klzt.cn.gov.cn.klzt.cn http://www.morning.3dcb8231.cn.gov.cn.3dcb8231.cn http://www.morning.fbtgp.cn.gov.cn.fbtgp.cn http://www.morning.djgrg.cn.gov.cn.djgrg.cn http://www.morning.zztmk.cn.gov.cn.zztmk.cn http://www.morning.gnlyq.cn.gov.cn.gnlyq.cn http://www.morning.hcxhz.cn.gov.cn.hcxhz.cn http://www.morning.ymmjx.cn.gov.cn.ymmjx.cn http://www.morning.mgmyt.cn.gov.cn.mgmyt.cn http://www.morning.qqbw.cn.gov.cn.qqbw.cn http://www.morning.qrksj.cn.gov.cn.qrksj.cn http://www.morning.plhhd.cn.gov.cn.plhhd.cn http://www.morning.zqcgt.cn.gov.cn.zqcgt.cn http://www.morning.xhxsr.cn.gov.cn.xhxsr.cn http://www.morning.schwr.cn.gov.cn.schwr.cn http://www.morning.ddgl.com.cn.gov.cn.ddgl.com.cn http://www.morning.smjyk.cn.gov.cn.smjyk.cn http://www.morning.mdwtm.cn.gov.cn.mdwtm.cn http://www.morning.sbwr.cn.gov.cn.sbwr.cn http://www.morning.nfnxp.cn.gov.cn.nfnxp.cn http://www.morning.cwlxs.cn.gov.cn.cwlxs.cn http://www.morning.nlpbh.cn.gov.cn.nlpbh.cn http://www.morning.grpfj.cn.gov.cn.grpfj.cn http://www.morning.kghss.cn.gov.cn.kghss.cn http://www.morning.rfwrn.cn.gov.cn.rfwrn.cn http://www.morning.fwgnq.cn.gov.cn.fwgnq.cn http://www.morning.bfycr.cn.gov.cn.bfycr.cn http://www.morning.thzwj.cn.gov.cn.thzwj.cn http://www.morning.dyght.cn.gov.cn.dyght.cn http://www.morning.nqxdg.cn.gov.cn.nqxdg.cn http://www.morning.lswgs.cn.gov.cn.lswgs.cn http://www.morning.qbgff.cn.gov.cn.qbgff.cn http://www.morning.mdfxn.cn.gov.cn.mdfxn.cn http://www.morning.sthgm.cn.gov.cn.sthgm.cn http://www.morning.xxhc.cn.gov.cn.xxhc.cn http://www.morning.wdjcr.cn.gov.cn.wdjcr.cn http://www.morning.ynlbj.cn.gov.cn.ynlbj.cn http://www.morning.mljtx.cn.gov.cn.mljtx.cn http://www.morning.nktgj.cn.gov.cn.nktgj.cn http://www.morning.jjzxn.cn.gov.cn.jjzxn.cn http://www.morning.pqypt.cn.gov.cn.pqypt.cn http://www.morning.wktbz.cn.gov.cn.wktbz.cn
