LeetCode 64. Minimum Path Sum (动归)

曾经终败给现在 2024-04-17 23:28 22阅读 0赞

题目描述：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70][]

一看这道题和上一道63题像从一个模板出来的，那它很危险了，我们可以套用上题类似的状态公式，稍作修改就能过了，而且也不用怕它卡，卡的地方都知道了。

思路在注释：

class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            //这题怕不是上两题的大哥，蜀国三兄弟
            //它还是把dp状态矩阵画好了，搞不好要白给
            //和上题那么像我们用一下上题的公式吧
            //上题公式：
            //dp[i][j] = dp[i-1][j] + dp[i][j-1]  if(obstacleGrid[i][j]!=1)
            //这题公式：
            //dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j];  
            int n = grid.size();
            int m = grid[0].size();
            long dp[n+5][m+5];
            memset(dp, 0, sizeof(dp));
            for(int i = 0; i < n; i++){
                for(int j = 0; j < m; j++){
                    if(i > 0 && j > 0) dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
                    else if(i > 0 && j == 0) dp[i][j] = dp[i-1][j] + grid[i][j];
                    else if(i == 0 && j > 0) dp[i][j] = dp[i][j-1] + grid[i][j];
                    else if(i == 0 && j == 0) dp[i][j] = grid[i][j];
                }
            }
            return dp[n-1][m-1];
        }
    };

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/b89656c96880445ebfdceccd0a08c24c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2NjUyNjE5_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/17/f8261e4c159a455d9507f78e836d212a.png