与leetcode 120 三角形最短路径和类似
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int m=grid.size(); int n=grid[0].size(); vector <vector <int>> dp(m,vector <int> (n,0)); dp[m-1][n-1]=grid[m-1][n-1]; for(int i=m-2;i>=0;i--) {//初始化n-1列，，防止数组越界 dp[i][n-1]=grid[i][n-1]+dp[i+1][n-1]; } for(int i=n-2;i>=0;i--) {//初始化m-1行，，防止数组越界 dp[m-1][i]=grid[m-1][i]+dp[m-1][i+1]; } for(int i=m-2;i>=0;i--) { for(int j=n-2;j>=0;j--) { dp[i][j]=min(dp[i+1][j],dp[i][j+1])+grid[i][j]; } } return dp[0][0]; } };