LeetCode 1289 下降路径最小和 II

给出一个二维数组，从每行选择一个数字，且相邻的两行不能选择同一列的数字，求选出来的所有数字最小和。很常规的一道动态规划题目，用一个数组dp[i][j]记录选择第i行第j列时的最小和，我是从上到下选择，每次选择不能选择和前一行同列的数。

class Solution {
public:
    int dp[205][205];
    struct node
    {
        int val,pos;
        bool operator <(const node& rhs) const
        {
            return val<rhs.val;
        }
    };
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n=arr.size(),m;
        if(n!=0) m=arr[0].size();
        for(int i=0;i<m;i++)
        dp[0][i]=arr[0][i];
        node tmp[205];
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                tmp[j].pos=j;
                tmp[j].val=dp[i-1][j];
            }
            sort(tmp,tmp+m);
            for(int j=0;j<m;j++)
            {
                if(tmp[0].pos!=j)
                    dp[i][j]=arr[i][j]+tmp[0].val;
                else
                    dp[i][j]=arr[i][j]+tmp[1].val;
            }
        }
        int ans=0x3f3f3f3f;
        for(int i=0;i<m;i++)
            ans=min(ans,dp[n-1][i]);
        return ans;
    }
};

LeetCode 1289 下降路径最小和 II

原文：https://www.cnblogs.com/ambition-hhn/p/12856490.html