【动态规划】下降路径最小和

题目链接https://leetcode.cn/problems/minimum-falling-path-sum/description/classSolution{public:intminFallingPathSum(vectorvectorintmatrix){/*时空复杂度O(n^2)*/// 1. 创建dp表intnmatrix.size();vectorvectorintdp(n1,vectorint(n2,INT_MAX));// 2. 初始化// 初始化第一行for(intj0;jn2;j)dp[0][j]0;// 3. 填表for(inti1;in;i)for(intj1;jn;j)dp[i][j]min(dp[i-1][j-1],min(dp[i-1][j],dp[i-1][j1]))matrix[i-1][j-1];// 4. 返回值intretINT_MAX;for(intj1;jn;j)retmin(ret,dp[n][j]);returnret;}};