首页 🍒LeetCode,🐶算法

题目

R4KQDPXUP1.png

m == grid.length
n == grid[i].length
1 <= m, n <= 200
0 <= gridi <= 100

思路

此题数据达到200 * 200搜索会超时。

因为每次移动只能向下或向右,所以要到达某个方块只能由其上边的方块或左边的方块到达(左上角方块除外)。

定义dp[i][j]:到达i,j位置所需要的最少步数。
状态转移方程:由于方块只能向下或向右移动,那么dp[i][j]的值就只和dp[i - 1][j]和dp[i][j - 1]有关,由于找最短路径所以在dp[i - 1][j]和dp[i][j - 1]取最小然后加上grid[i][j]表示到达dp[i][j]所需要的最短路径。
dp[0][0] = grid[0][0]

确定好转移方程后两层遍历可以把dp数组填充,然后取右下角就是所求答案。

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        int dp[n][m];
        dp[0][0] = grid[0][0];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (j - 1 >= 0 && i - 1 >= 0)
                    dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j];
                else if (j - 1 >= 0)
                    dp[i][j] = dp[i][j - 1] + grid[i][j];
                else if (i - 1 >= 0)
                    dp[i][j] = dp[i - 1][j] + grid[i][j];
            }
        }
        return dp[n - 1][m - 1];
    }
};



文章评论