每个单元格中都有一个点矩阵,该矩阵如何使用两次遍历从该网格中获取最大点。
有一些条件要满足-
第一次遍历从网格的左上角单元格开始,并且应该到达左下角。在第二次遍历中,从右上角到右下角
我们只能从一个单元格移到当前单元格的底部,左下角和当前单元格的右下角。
如果一个遍历已经从一个单元格中获得了一些点,则在下一次遍历中将不会从该单元格中获得任何点。
Input: A grid with points. 3 6 8 2 5 2 4 3 1 1 20 10 1 1 20 10 1 1 20 10 Output: Maximum points collected by two traversals is 73. From the first traversal, it gains: 3 + 2 + 20 + 1 + 1 = 27 From the second traversal, it gains: 2 + 4 + 10 + 20 + 10 = 46
findMaxVal(mTable, x, y1, y2)
输入-一个3D数组作为存储表,x值和y1,y2。
输出-最大值。
Begin if x, y1 and y2 is not valid, then return - ∞ if both traversal is complete, then if y1 = y2, then return grid[x, y1] else return grid[x, y1] + grid[x, y2] if both traversal are at last row, then return - ∞ if subProblem is solved, then return mTable[x, y1, y2] set res := - ∞ if y1 = y2, then temp := grid[x, y1] else temp := grid[x, y1] + grid[x, y2] res := max of res and (temp + findMaxVal(mTable, x+1, y1, y2-1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1, y2+1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1, y2)) res := max of res and (temp + findMaxVal(mTable, x+1, y1-1, y2)) res := max of res and (temp + findMaxVal(mTable, x+1, y1-1, y2-1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1-1, y2+1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1+1, y2)) res := max of res and (temp + findMaxVal(mTable, x+1, y1+1, y2-1)) res := max of res and (temp + findMaxVal(mTable, x+1, y1+1, y2+1)) return true if mTable[x, y1, y2] = res End
#include<iostream> #define ROW 5 #define COL 4 using namespace std; int grid[ROW][COL] = { {3, 6, 8, 2}, {5, 2, 4, 3}, {1, 1, 20, 10}, {1, 1, 20, 10}, {1, 1, 20, 10}, }; bool isValidInput(int x, int y1, int y2) { return (x >= 0 && x < ROW && y1 >=0 && y1 < COL && y2 >=0 && y2 < COL); } int max(int a, int b) { return (a>b)?a:b; } int findMaxVal(int mTable[ROW][COL][COL], int x, int y1, int y2) { if (!isValidInput(x, y1, y2)) //when in invalid cell, return -ve infinity return INT_MIN; if (x == ROW-1 && y1 == 0 && y2 == COL-1) //when both traversal is complete return (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2]; if (x == ROW-1) //both traversal are at last row but not completed return INT_MIN; if (mTable[x][y1][y2] != -1) //when subproblem is solved return mTable[x][y1][y2]; int answer = INT_MIN; //initially the answer is -ve infinity int temp = (y1 == y2)? grid[x][y1]: grid[x][y1] + grid[x][y2]; //store gain of the current room //找到所有可能值的答案并使用最大值 answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2-1)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2+1)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1, y2)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2-1)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1-1, y2+1)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2-1)); answer = max(answer, temp + findMaxVal(mTable, x+1, y1+1, y2+1)); return (mTable[x][y1][y2] = answer); //store the answer in the mTable and return. } int findMaxCollection() { //创建一个备忘录表并将所有值设置为-1- int mTable[ROW][COL][COL]; for(int i = 0; i<ROW; i++) for(int j = 0; j<COL; j++) for(int k = 0; k<COL; k++) mTable[i][j][k] = -1; return findMaxVal(mTable, 0, 0, COL-1); } int main() { cout << "Maximum collection is " << findMaxCollection(); return 0; }
输出结果
Maximum collection is 73