LeetCode 1289. 下降路径最小和 II（DP）

示例 1：
输入：arr = [[1,2,3],[4,5,6],[7,8,9]]
输出：13
解释：
所有非零偏移下降路径包括：
[1,5,9], [1,5,7], [1,6,7], [1,6,8],
[2,4,8], [2,4,9], [2,6,7], [2,6,8],
[3,4,8], [3,4,9], [3,5,7], [3,5,9]
下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
 
提示：
1 <= arr.length == arr[i].length <= 200
-99 <= arr[i][j] <= 99

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int m = arr.size(), n = arr[0].size();
        if(n == 1)//一列，不满足题目要求
        	return 0;
        vector<int> dp(arr[0]);//存储到达每一行的最小路径和，第一行初始为arr数值
        vector<int> temp(n,INT_MAX);
        int i, j, k, MIN = INT_MAX;
        for(i = 1; i < m; i++)//从第2行开始
        {
        	for(j = 0; j < n; j++)
        		temp[j] = INT_MAX;//临时存储最小路径和，初始化为INT_MAX
        	for(j = 0; j < n; j++)//对上一行的每个dp[j] 计算下一行的 dp值
        	{       		
        		for(k = 0; k < n; k++)
        		{
        			if(k == j)//不同列的要求
        				continue;
        			temp[k] = min(temp[k], dp[j]+arr[i][k]);
        			//第j列可以选择下一行的 k列作为路径
        		}     		
        	}

        	for(j = 0; j < n; j++)
        		dp[j] = temp[j];//临时值存入dp中，状态压缩
        }
        for(i = 0; i < n; i++)
        	if(dp[i] < MIN)
        		MIN = dp[i];//取最后一行的最小值
    	return MIN;
    }
};