第一次独立写出dp类题目,来写题解,记录下思路。
可能有不对的地方,还请各位大佬指正出来,互相学习,谢谢!
思路:
1、状态定义:
dp[i][j]:表示从左上角出发到(i,j)位置经过的最短路径和。 此处i和j的下标都是从0开始算,没有对dp矩阵多构建一行和一列
2、状态转移:
根据题意,只能往右或者往下走,所以对于任意一个位置(i,j)只能从
(i-1,j)或者(i,j-1)过来。由此可以知道到(i,j)的最短距离和等于
dp[ i-1 ][ j ] 和 dp[ i ][ j-1 ]中较小的数 加上(i,j)位置的值。
dp[i][j] = min ( dp[i-1][j] , dp[i][j-1] ) + matrix [i] [j];
3、初始化:
dp[0][j] = dp[0][j-1] + matrix[0][j]; dp[i][0] = dp[i-1][0] + matrix[i][0];
4、结果返回
dp[n-1][m-1]; n和m分别是行数和列数
代码如下:
class Solution { public: /** * * @param matrix int整型vector<vector<>> the matrix * @return int整型 */ int minPathSum(vector<vector<int> >& matrix) { //计算行列数 int row=matrix.size(); int line=matrix[0].size(); //构建dp数组 vector<vector<int>>dp(row+1,vector<int>(line+1)); //初始化dp[0][0] dp[0][0]=matrix[0][0]; //初始化dp数组第一行 for(int j=1;j<line;++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]; } //求任意位置的最短路径距离和 for(int i=1;i<row;++i){ for(int j=1;j<line;++j){ dp[i][j]=min(dp[i-1][j],dp[i][j-1])+matrix[i][j]; } } //结果返回 return dp[row-1][line-1]; } };