稀碎从零算法笔记Day51-LeetCode:最小路径和

题型：DP、数组、矩阵

链接：64. 最小路径和 - 力扣（LeetCode）

来源：LeetCode

题目描述

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

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

题目样例

示例 1：

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7
解释：因为路径 1→3→1→1→1 的总和最小。

示例 2：

输入：grid = [[1,2,3],[4,5,6]]
输出：12

提示：

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

题目思路

①全局最优，DP ②找到最短的路径，可以BFS

矩阵，可以用dp[x][y] 来表示到达(x,y)这个点的路径最短长度
dp[x][y]的状态变化，主要看dp[x-1][y] 和 dp[x][y-1]（如果没越界的话）
所以可以先初始化dp[][]的左边和上边——因为dp[x][0] 只能dp[x-1][0] + grid[x][0]这样走
剩下的位于矩阵右下角的元素 dp[x][y] = min(dp[x-1][y],dp[x][y-1]) + grid[x][y];

BFS数据量小的话枚举出来所有数据也可以做，数据量太大就没办法了(会超时) 这边不给代码了

C++代码

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        //倒退:dp[row-1][col-1] = min(dp[row-2][col-1],dp[row-1][col-2]);
        //分析状态：1. x = 0, y > 0 dp[x][y] = dp[x][y-1] + grid[x][y];
        //         2. x > 0, y = 0 dp[x][y] = dp[x-1][y] + grid[x][y];
        //         3. x > 0, y > 0 dp[x][y] = min(dp[x-1][y],dp[x][y-1]) + grid[x][y];

        int row = grid.size();
        int column = grid[0].size();

        vector<vector<int>>dp(row,vector<int>(column));
        dp[0][0] = grid[0][0];
        // 初始化两条边
        for(int x = 1 ; x < row ; ++x){
            dp[x][0] = dp[x-1][0] + grid[x][0];
        }
        for(int y = 1 ; y < column ; ++y){
            dp[0][y] = dp[0][y-1] + grid[0][y];
        }
        // 遍历右下角的矩阵
        for(int x = 1 ; x < row ; ++x)
            for(int y = 1 ; y < column ; ++y){
                dp[x][y] = min(dp[x-1][y] , dp[x][y-1]) + grid[x][y];
            }

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