力扣64. 最小路径和

Problem: 64. 最小路径和

题目描述

思路

对于二维动态规划我们往往要建立一个矩阵，同时将矩阵的第一行、列根据题意填写出相应的值以完成状态的初始化（接下来规定矩阵grid的函数为row，列数为col）

1.创建一个与grid等大的int类形矩阵dp，用于记录从gird左上角度到右下角的最短距离；
2.初始化dp的第一行、列：将grid第一行、列元素的累加和分别填入dp的第一行列（若不明其意，直接看代码即可）；
3.从dp的第一行、列开始动态转移，由于是从右上角到左下角，所以每次移动只能是向下或者向右移动则当前位置的最短距离为当前位置右侧或者上侧中的最小值加上当前位置的元素值即dp[i][j] = min(dp[i][j - 1], dp[i - 1][j]) + grid[i][j]
4.最终返回dp[row - 1][col - 1]

复杂度

时间复杂度:

$O(M\times N)$;其中$M$是矩阵的行数，$N$是矩阵的列数

空间复杂度:

$O(M\times N)$

Code

class Solution {
public:
    /**
     * The minimum path sum is obtained by dynamic programming
     * @param grid Given matrix(Store the number of steps)
     * @return int
     */
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        int col = grid[0].size();
        vector<vector<int>> dp(row, vector<int>(col));
        int temp = 0;
        for (int i = 0; i < col; ++i) {
            temp += grid[0][i];
            dp[0][i] = temp;
        }
        temp = 0;
        for (int j = 0; j < row; ++j) {
            temp += grid[j][0];
            dp[j][0] = temp;
        }
        //Dynamic transfer equation
        for (int i = 1; i < row; ++i) {
            for (int j = 1; j < col; ++j) {
                dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }
        return dp[row - 1][col - 1];
    }
};