【算法挨揍日记】day21——64. 最小路径和、174. 地下城游戏

约定不等于承诺〃 2024-02-20 11:16 10阅读 0赞

## 64. 最小路径和 ##

[64. 最小路径和][64.]

### 题目描述： ###

给定一个包含非负整数的 `m x n` 网格 `grid` ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。

**说明：**每次只能向下或者向右移动一步。

![e05e922f215e4f9f8b1aab4631d71ad9.png][]

### 解题思路： ###

> 状态表示：dp【i】【j】表示到达（i，j）位置后的最小路径和
> 
> 状态转移方程：
> 
> 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(vector<vector<int>>& grid) {
            int len1=grid.size();
            int len2=grid[0].size();
            vector<vector<int>>dp(len1+1,vector<int>(len2+1,INT_MAX));
            dp[0][1]=0;
            for(int i=1;i<=len1;i++)
            {
                for(int j=1;j<=len2;j++)
                {
                    dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
                }
            }
            return dp[len1][len2];
        }
    };

--------------------

## 174. 地下城游戏 ##

[174. 地下城游戏][174.]

### 题目描述： ###

恶魔们抓住了公主并将她关在了地下城 `dungeon` 的 **右下角** 。地下城是由 `m x n` 个房间组成的二维网格。我们英勇的骑士最初被安置在 **左上角** 的房间里，他必须穿过地下城并通过对抗恶魔来拯救公主。

骑士的初始健康点数为一个正整数。如果他的健康点数在某一时刻降至 0 或以下，他会立即死亡。

有些房间由恶魔守卫，因此骑士在进入这些房间时会失去健康点数（若房间里的值为*负整数*，则表示骑士将损失健康点数）；其他房间要么是空的（房间里的值为 *0*），要么包含增加骑士健康点数的魔法球（若房间里的值为*正整数*，则表示骑士将增加健康点数）。

为了尽快解救公主，骑士决定每次只 **向右** 或 **向下** 移动一步。

返回确保骑士能够拯救到公主所需的最低初始健康点数。

**注意：**任何房间都可能对骑士的健康点数造成威胁，也可能增加骑士的健康点数，包括骑士进入的左上角房间以及公主被监禁的右下角房间。

![e335a2a8557b43b6aab24ff56eecf363.png][]

### 解题思路： ###

> 状态表示：dp【i】【j】代表以（i，j）位置为起点到终点（len1-1,len2-1）的最小生命值
> 
> 状态转移方程：
> 
> 假设(i,j)到终点的最小生命值为x
> 
> 我们就两种走法，向右走或者向下走
> 
> 当向下走的时候：x+dungeon\[i\]\[j\]>=dp\[i+1\]\[j\]
> 
> x>+=dp\[i+1\]\[j\]-dungeon\[i\]\[j\]
> 
> 当向下走的时候：x+dungeon\[i\]\[j\]>=dp\[i\]\[j+1\]
> 
> x>+=dp\[i\]\[j+1\]-dungeon\[i\]\[j\]
> 
> 因此状态转移方程为：dp\[i\]\[j\]=min(dp\[i+1\]\[j\],dp\[i\]\[j+1\])-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(vector<vector<int>>& dungeon) {
            int len1=dungeon.size();
            int len2=dungeon[0].size();
            vector<vector<int>>dp(len1+1,vector<int>(len2+1,INT_MAX));
            dp[len1-1][len2]=dp[len1][len2-1]=1;
            for(int i=len1-1;i>=0;i--)
            {
                for(int j=len2-1;j>=0;j--)
                {
                    dp[i][j]=min(dp[i+1][j],dp[i][j+1])-dungeon[i][j];
                    dp[i][j]=max(1,dp[i][j]);
                }
            }
            return dp[0][0];
        }
    };

###  ###

[64.]: https://leetcode.cn/problems/minimum-path-sum/
[e05e922f215e4f9f8b1aab4631d71ad9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/90e27140a6704b68994ce22feb69ab7f.png
[174.]: https://leetcode.cn/problems/dungeon-game/
[e335a2a8557b43b6aab24ff56eecf363.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/cc24e5c745e843d996a4eab4673b76f7.png