力扣64. 最小路径和

动态规划

• 思路：
  • 假设 dp[i][j] 为 第 i 行、第 j 列的最小路径和；
  • 因为只能向右或者向下移动，所以状态转移方程：
    • dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + v[i][j]
    • 当 i = 0 时，即第一行，只能向右移动，即：dp[0][j] = dp[0][j - 1]?+ v[0][j]；（可以认为是 i - 1 不能越界）
    • 当 j = 0 时，即第一列，只能向下移动，即：dp[i][0] = dp[i - 1][0] + v[i][0]；（可以任务是 j - 1 不能越界）
  • 边界条件 dp[0][0] = v[0][0]；

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        if (row == 0) {
            return 0;
        }
        int column = grid[0].size();
        if (column == 0) {
            return 0;
        }

        std::vector<std::vector<int>> dp(row, std::vector<int>(column));
        dp[0][0] = grid[0][0];
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < column; ++j) {
                if (i == 0 && j == 0) {
                    dp[0][0] = grid[0][0];
                } else if (i == 0) {
                    dp[0][j] = dp[0][j - 1] + grid[0][j];
                } else if (j == 0) {
                    dp[i][0] = dp[i -1][0] + grid[i][0];
                } else {
                    dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
                }
            }
        }

        return dp[row - 1][column - 1];

    }
};

• 可调整一下逻辑，先计算第一行的 dp 值，然后计算第一列的 dp 值：

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int row = grid.size();
        if (row == 0) {
            return 0;
        }
        int column = grid[0].size();
        if (column == 0) {
            return 0;
        }

        std::vector<std::vector<int>> dp(row, std::vector<int>(column));
        dp[0][0] = grid[0][0];
        for (int i = 1; i < row; ++i) {
            dp[i][0] = dp[i - 1][0] + grid[i][0];
        }
        for (int j = 1; j < column; ++j) {
            dp[0][j] = dp[0][j - 1] + grid[0][j];
        }


        for (int i = 1; i < row; ++i) {
            for (int j = 1; j < column; ++j) {
                dp[i][j] = std::min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
            }
        }

        return dp[row - 1][column - 1];
    }
};