建设网站需要支付什么插件费用吗,做内容的网站,营销网站建设整合网站营销专家,公司网站后台是什么64. 最小路径和 64. 最小路径和
题目描述#xff1a;
给定一个包含非负整数的 m x n 网格 grid #xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。
说明#xff1a;每次只能向下或者向右移动一步。 解题思路#xff1a; 状态表示
给定一个包含非负整数的 m x n 网格 grid 请找出一条从左上角到右下角的路径使得路径上的数字总和为最小。
说明每次只能向下或者向右移动一步。 解题思路 状态表示dp【i】【j】表示到达ij位置后的最小路径和 状态转移方程 dp[i][j]min(dp[i][j-1],dp[i-1][j])grid[i-1][j-1] 初始化dp[0][i]INT_MAX,dp[i][0]INT_MAX,dp[0][1]0 填表顺序左到右 返回值dp【len1】【len2】 解题代码
class Solution {
public:int minPathSum(vectorvectorint grid) {int len1grid.size();int len2grid[0].size();vectorvectorintdp(len11,vectorint(len21,INT_MAX));dp[0][1]0;for(int i1;ilen1;i){for(int j1;jlen2;j){dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i-1][j-1];}}return dp[len1][len2];}
}; 174. 地下城游戏
174. 地下城游戏
题目描述
恶魔们抓住了公主并将她关在了地下城 dungeon 的 右下角 。地下城是由 m x n 个房间组成的二维网格。我们英勇的骑士最初被安置在 左上角 的房间里他必须穿过地下城并通过对抗恶魔来拯救公主。
骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下他会立即死亡。
有些房间由恶魔守卫因此骑士在进入这些房间时会失去健康点数若房间里的值为负整数则表示骑士将损失健康点数其他房间要么是空的房间里的值为 0要么包含增加骑士健康点数的魔法球若房间里的值为正整数则表示骑士将增加健康点数。
为了尽快解救公主骑士决定每次只 向右 或 向下 移动一步。
返回确保骑士能够拯救到公主所需的最低初始健康点数。
注意任何房间都可能对骑士的健康点数造成威胁也可能增加骑士的健康点数包括骑士进入的左上角房间以及公主被监禁的右下角房间。 解题思路 状态表示dp【i】【j】代表以ij位置为起点到终点len1-1,len2-1的最小生命值 状态转移方程 假设(i,j)到终点的最小生命值为x 我们就两种走法向右走或者向下走 当向下走的时候xdungeon[i][j]dp[i1][j] xdp[i1][j]-dungeon[i][j] 当向下走的时候xdungeon[i][j]dp[i][j1] xdp[i][j1]-dungeon[i][j] 因此状态转移方程为dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j] 这里值得注意的是dp【i】【j】可能为负数因此要dp[i][j]max(1,dp[i][j]) 初始化dp[len1][i]和dp[i][len2]都为INT_MAX dp[len1-1][len2]和dp[len1][len2-1]为1 填表顺序从右到左从下到上 返回值dp[0][0] 解题代码
class Solution {
public:int calculateMinimumHP(vectorvectorint dungeon) {int len1dungeon.size();int len2dungeon[0].size();vectorvectorintdp(len11,vectorint(len21,INT_MAX));dp[len1-1][len2]dp[len1][len2-1]1;for(int ilen1-1;i0;i--){for(int jlen2-1;j0;j--){dp[i][j]min(dp[i1][j],dp[i][j1])-dungeon[i][j];dp[i][j]max(1,dp[i][j]);}}return dp[0][0];}
};
