力控应用路径不存在，最短路径算法解

题目描述

给定一个包含非负整数的 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.lengthn grid[i].length1 < m, n < 2000 < grid[i][j] < 200

通过次数

527.3K

提交次数

756K

通过率

69.7%

思路和题解

动态规划第一行和第一列的答案就是对应位置矩阵上的数字其他位置答案是min(左上)。

代码

class Solution {public:    int minPathSum(vector<vector<int>>& grid) {        int dp[201][201];        int mgrid.size();        int ngrid[0].size();        dp[1][0]dp[0][1]0;        for(int i1;i<m;i) dp[i][1]grid[i-1][0]dp[i-1][1];        for(int i1;i<n;i) dp[1][i]grid[0][i-1]dp[1][i-1];        for(int i2;i<m;i)        {            for(int j2;j<n;j)            {                dp[i][j]grid[i-1][j-1]min(dp[i-1][j],dp[i][j-1]);            }        }        return dp[m][n];    }};