LeetCode热题100 最小路径和

题目描述给定一个包含非负整数的 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思路动态规划板子dp[i][j]表示到达当前i, j的最小值dp[i][j] min(dp[i - 1][j], dp[i][j - 1]) grid[i][j]。代码classSolution{public:intminPathSum(vectorvectorintgrid){intngrid.size();intmgrid[0].size();vectorvectorintdp(n,vectorint(m,0));for(inti0;in;i){for(intj0;jm;j){if(!i!j)dp[i][j]grid[i][j];elsedp[i][j]min(i0?dp[i-1][j]:INT_MAX,j0?dp[i][j-1]:INT_MAX)grid[i][j];}}returndp[n-1][m-1];}};