1. 题意

一个N x N的方形数组，从第一行任意列出发，每次向下一行，可以向左向右保护列不动，求到最后一行的最小路径和。

2. 题解

简单动态规划问题
$$\begin{array}{c}dp[i][j]=m[i][j]+\min \{\begin{array}{l}dp[i-1][j-1]\\ dp[i-1][j]\\ dp[i-1][j+1]\end{array}\end{array}$$

• 二维动态规划

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<vector<int>> dp( n,vector<int>(n, 0));for (int i = 0;i < n;i++) {dp[0][i] = matrix[0][i];}int ans = 1000000;for (int i = 1;i < n;i++) {for (int j = 0;j < n;j++) {dp[i][j] = dp[i - 1][j];if (j + 1 < n)dp[i][j] = min(dp[i][j], dp[i-1][j+1]);if (j - 1 >= 0)dp[i][j] = min(dp[i][j], dp[i-1][j-1]);dp[i][j] += matrix[i][j];}}for (int i = 0;i < n;i++) {ans = min(dp[n-1][i], ans);}return ans;}
};

可以像01背包那样，将空间复杂度压缩到O(n)

• 空间压缩

class Solution {
public:int minFallingPathSum(vector<vector<int>>& matrix) {int n = matrix.size();vector<int> dp(n, 0);for (int i = 0;i < n;i++) {dp[i] = matrix[0][i];}int ans = 1000000;for (int i = 1;i < n;i++) {int pre = dp[0];for (int j = 0;j < n;j++) {int tmp = dp[j];if (j > 0)dp[j] = min(pre,dp[j]);if (j + 1 < n)dp[j] = min(dp[j+1],dp[j]);dp[j] += matrix[i][j];pre = tmp;}}for (int i = 0;i < n;i++) {ans = min(dp[i], ans);}return ans;}
};