1. 题意
一个N x N的方形数组，从第一行任意列出发，每次向下一行，可以向左向右保护列不动，求到最后一行的最小路径和。
2. 题解
简单动态规划问题
d p [ i ] [ j ] = m [ i ] [ j ] + min { d p [ i − 1 ] [ j − 1 ] d p [ i − 1 ] [ j ] d p [ i − 1 ] [ j + 1 ] \begin{equation*} dp[i][j] =m[i][j] +\min \begin{cases} dp[i-1][j-1] \\ dp[i-1][j] \\ dp[i-1][j+1] \end{cases} \end{equation*} dp[i][j]=m[i][j]+min⎩ ⎨ ⎧dp[i−1][j−1]dp[i−1][j]dp[i−1][j+1]
- 二维动态规划
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;}
};
