下降路径最小和-526互联

给你一个 n x n 整数矩阵 grid ，请你返回非零偏移下降路径数字和的最小值。
非零偏移下降路径定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。

1. 动态规划

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        int dp[n][n];
        memset(dp,10000,sizeof(dp));
        for(int i=0;i<n;i++)
            dp[0][i] = grid[0][i];

        for(int i=1;i<n;i++){//遍历行
            for(int j=0;j<n;j++){//遍历列
                //由上一行的最小值进行转移
                for(int k=0;k<n;k++){//遍历上一行的每一列
                    if(k==j) continue;//不能是同一列
                    dp[i][j] = min(dp[i][j],dp[i-1][k]+grid[i][j]);
                }
            }
        }
        int res = 10e5;
        for(int i=0;i<n;i++)
            res = min(res,dp[n-1][i]);
        return res;
    }
};

路径