本文主要是介绍从左上角到右下角的最小距离和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述：给定一个二维数组matrix，一个人必须从左上角出发，最后到达右下角，沿途只可以向下或者向右走，沿途的数字都累加就是距离累加和，返回最小距离累加和。
way：无他，dp[i] [j]表示(i,j)坐标位置的最小距离和。
#include<iostream>
#include<vector>
using namespace std;int minPathSum(vector<vector<int>> matrix)
{int row=matrix.size();int col=matrix[0].size();vector<vector<int>>dp(row,vector<int>(col));dp[0][0]=matrix[0][0];//第一行的dp值只能从左边过来for(int j=1; j<col; j++){dp[0][j]=dp[0][j-1]+matrix[0][j];}//第一列的dp值只能从上边过来for(int i=1; i<row; i++){dp[i][0]=dp[i-1][0]+matrix[i][0];}//从第二行第二列及其后的dp值可以从左边或上边过来for(int i=1; i<row; i++){for(int j=1; j<col; j++){dp[i][j]=max(dp[i-1][j],dp[i][j-1])+matrix[i][j];}}return dp[row-1][col-1];
}way2：一层dp。
//改成一层dp
int minPathSum2(vector<vector<int>> matrix)
{int row=matrix.size();int col=matrix[0].size();vector<int>dp(col);//初始值dp[0]=matrix[0][0];//第一行的值for(int j=1; j<col; j++){dp[j]=dp[j-1]+matrix[0][j];}//从第二行及其往后的行的值for(int i=1; i<row; i++){//表示第一列的值只能从上面过来dp[0]+=matrix[i][0];for(int j=1; j<col; j++){//dp[j]是上一行的dp[j],dp[j-1]是这一行更新的最新的dp[j-1]dp[j]=min(dp[j],dp[j-1])+matrix[i][j];}}return dp[col-1];
}这篇关于从左上角到右下角的最小距离和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
