算法：下降路径最小和

题目：

一个 n x n 整数矩阵 arr ，请返回 非零偏移下降路径 数字和的最小值。

非零偏移下降路径 定义为：从 arr 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

思路：

从整数矩阵arr的顶部到底部，定义dp[i][j]为从顶部到第i行，第j个数的 非零偏移下降路径 数字和的最小值，则答案为min(dp[n-1][i]),0<=i<=n-1 。记第i-1行的最小值为first,次小值为second。则状态转移方程为 dp[i][j]=first+arr[i][j],first和arr[i][j]不同一列 d[i][j] = second+arr[i][j]，first和arr[i][j]同一列。边界dp[0][i] = arr[0][i] ,0<=i<=n-1,时间复杂度为O(n²),空间复杂度为O(1)

代码：

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int first_sum = 0,first_pos = -1,second_sum = 0;
        for(int i = 0;i < n;i++) {
            int fs = INT_MAX,fp = -1,ss = INT_MAX;
            for(int j = 0;j < n;j++) {
                int cur_sum = (first_pos != j ? first_sum : second_sum) + grid[i][j];
                if (cur_sum < fs) {
                    ss = fs;
                    fs = cur_sum;
                    fp = j;
                }
                else if(cur_sum < ss) {
                    ss = cur_sum;
                }
            }
            first_sum = fs;
            second_sum = ss;
            first_pos = fp;
        }
        return first_sum;
    }
};