1289. Minimum Falling Path Sum II -------H ~~~~~

Given a square grid of integers arr, a falling path with non-zero shifts is a choice of exactly one element from each row of arr, such that no two elements chosen in adjacent rows are in the same column.

Return the minimum sum of a falling path with non-zero shifts.

 

Example 1:

Input: arr = [[1,2,3],[4,5,6],[7,8,9]]
Output: 13
Explanation: 
The possible falling paths are:
[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]
The falling path with the smallest sum is [1,5,7], so the answer is 13.

 

Constraints:

• 1 <= arr.length == arr[i].length <= 200
• -99 <= arr[i][j] <= 99

 A:

首先，对2种情况递归。从上到下，每一行， 找到最小的2个值，  再mark不用的那一行，然后往下一行搜

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        // for each row, find two least position
        int n = arr.size();
        return helper(0, arr, -1);
    }
private:
    int helper(int curRow, vector<vector<int>>& arr, int preIndex) {
        int n = arr.size();
        if (curRow >= n) {
            return 0;
        }
        int rowMin = INT_MAX, minCol = -1;
        int rowMin2 = INT_MAX, minCol2 = -1;
        for (int i = 0; i < n; i++) {
            if (i == preIndex) {
                continue;
            }
            if (arr[curRow][i] <= rowMin) {
                rowMin2 = rowMin;
                minCol2 = minCol;
                rowMin = arr[curRow][i];
                minCol = i;
            }
            else if (arr[curRow][i] < rowMin2) {
                rowMin2 = arr[curRow][i];
                minCol2 = i;
            }
        }
        int next1 = INT_MAX;
        int next2 = INT_MAX;
        if (minCol >= 0) {
            next1 = arr[curRow][minCol] + helper(curRow + 1, arr, minCol);
        }
        if (minCol2 >= 0) {
            next2 = arr[curRow][minCol2] + helper(curRow + 1, arr, minCol2);
        }
        return min(next1, next2);
    }
};

**********************LTE了************

原因是我们确定某一行以后，下面调用2次，有重复计算。

因为每次是排除法，所以不能简单地用HashMap去记录。

首先想到的方法就是我们每一层都找出2个最小的数值。然后递归即可。

然而这样还是会重复计算的。虽然应该能过test。  进一步的方法是，每次先计算下一层的最小的2个值。然后返回本层的2个最小值，加和。比较

-------------------------------------------------

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size();
        if (n == 0)
            return 0;
        if (n == 1)
            return arr[0][0];
        return helper(arr, 0)[0]->total;
    }
private:
    struct Node {
        int total;
        int index;
        Node(int v, int i) :total(v), index(i) {}
    };
    vector<Node*> helper(vector<vector<int>>& arr, int curRow) {
        int n = arr.size();
        if (curRow >= n) { // ending point
            Node* a = new Node(0, -1);
            Node* b = new Node(0, -1);
            return vector<Node*>{ a,b };
        }
        auto next = helper(arr, curRow + 1);
        // get the two minValue for current line        
        int rowMin = INT_MAX, minCol = -1;
        int rowMin2 = INT_MAX, minCol2 = -1;
        for (int i = 0; i < n; i++) {
            if (arr[curRow][i] <= rowMin) {
                rowMin2 = rowMin;
                minCol2 = minCol;
                rowMin = arr[curRow][i];
                minCol = i;
            }
            else if (arr[curRow][i] < rowMin2) {
                rowMin2 = arr[curRow][i];
                minCol2 = i;
            }
        }
        Node* tmpMin = new Node(rowMin + ((minCol == next[0]->index) ? next[1]->total : next[0]->total), minCol);

        Node* tmpMin2 = new Node(rowMin2 + ((minCol2 == next[0]->index) ? next[1]->total : next[0]->total), minCol2);
        if (tmpMin->total <= tmpMin2->total)
            return vector<Node*>{tmpMin, tmpMin2};
        else
            return vector<Node*>{tmpMin2, tmpMin};
    }
};

然而，上面的代码， 96% speedwise，可是memory 不够快。进一步的改善，  也就是把resursive call变成 循环。

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& arr) {
        int n = arr.size();
        vector<int> DP{0,-1, 0,-1};//{minSum, minIndex, minSum2, min2Index}
        for(int row =0; row < n; row++){
            // find MinValue and second minValue, and their indices
            int rowMin = INT_MAX, minCol = -1;
            int rowMin2 = INT_MAX, minCol2 = -1;
            for(int col = 0;col<n;col++){
                int val = arr[row][col];
                if(val <= rowMin){                    
                    rowMin2 = rowMin;
                    minCol2 = minCol;
                    rowMin = val;
                    minCol = col;                    
                }else if(val < rowMin2){
                    rowMin2 = val;
                    minCol2 = col;
                }
            }
            rowMin += minCol != DP[1]?DP[0]:DP[2];
            rowMin2 += minCol2 != DP[1]?DP[0]:DP[2];
            if(rowMin <= rowMin2)
                DP ={rowMin, minCol, rowMin2, minCol2};
            else
                DP = {rowMin2, minCol2, rowMin, minCol};
        }
        return DP[0];
    }
};

然而，速度超过了98.27%. 然而memory还是不够。  好奇怪~~~~~以后再说吧