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还是不够。 好奇怪~~~~~以后再说吧
No comments:
Post a Comment