一.题目解析大致意思是一个矩阵,沿着矩阵向下走并且只能空一格,求所走路径的最小和算法解析1.状态表示dp[i][j]表示到(i,j)位置时候的最小和2.状态转移方程3.初始化在写代码时就可以先初始化为无穷大,再把第一行改为零注意下标的映射,我们加了一行两列,想要找到原矩阵的数据就横纵坐标减去14.填表顺序从上到下5.返回值返回的是最后一行的最小和二.代码实现class Solution { public: int minFallingPathSum(vectorvectorint matrix) { int nmatrix.size(); vectorvectorintdp(n1,vectorint(n2,INT_MAX)); for(int j0;jn2;j)dp[0][j]0;//初始化第一行为零 for(int i1;in;i) for(int j1;jn;j) dp[i][j]min(dp[i-1][j],min(dp[i-1][j-1],dp[i-1][j1]))matrix[i-1][j-1];//注意下标的映射 int retINT_MAX; for(int i0;in;i) { retmin(ret,dp[n][i]); } return ret; } };