免费做印章的网站,网站建设售后服务内容,网站开发工程是待遇,有的网站为什么打不开怎么回事64. 最小路径和难度中等1430收藏分享切换为英文接收动态反馈给定一个包含非负整数的 m x n 网格 grid #xff0c;请找出一条从左上角到右下角的路径#xff0c;使得路径上的数字总和为最小。说明#xff1a;每次只能向下或者向右移动一步。示例 1#xff1a;输入#xff…64. 最小路径和难度中等1430收藏分享切换为英文接收动态反馈给定一个包含非负整数的 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] 100解题思路动态规划DP。状态转移方程dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j]AC代码class Solution {
public:int minPathSum(vectorvectorint grid) {//每次只能向下或者向右移动一步int rowgrid.size();int colgrid[0].size();int dp[row][col]; //走到坐标(i,j)所需最少花费//状态转移方程dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j]dp[0][0]grid[0][0];for(int i1;icol;i)dp[0][i]dp[0][i-1]grid[0][i];for(int i1;irow;i)dp[i][0]dp[i-1][0]grid[i][0];for(int i1;irow;i){for(int j1;jcol;j){dp[i][j]min(dp[i-1][j],dp[i][j-1])grid[i][j];}}return dp[row-1][col-1];}
};
