题目
在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
例如，在下面的棋盘中，如果沿着带下画线的数字的路线(1、12、5、7、7、16、5)。那么我们能拿到最大价值为53的礼物。
分析
动态规划
我们创建一个等同棋盘的二维数组，每个位置用记录前一步到这一步的能拿到的最多价值。
如下图，每一步都是拿到的最多价值。空间复杂度为O(n2);
C++
#include <iostream> using namespace std; int getMaxValue_sonlution(const int* values, int rows, int cols) { if (values == nullptr || rows <= 0 || cols <= 0) return 0; int** temp = new int*[rows];//用来存储每步的做大价值 for (int i = 0; i < rows; ++i) { temp[i] = new int[cols]; } for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { //保存前一步的最大价值 max(values[i-1][j]与values[i][j-1]) int maxnum = 0; if (0 == i && 0 == j) // 最开始 ; else if (0 == i) // 到最上边 maxnum = temp[i][j - 1]; else if (0 == j) // 到最左边 maxnum = temp[i - 1][j]; else maxnum = max(temp[i][j - 1], temp[i - 1][j]); temp[i][j] = values[i * cols + j] + maxnum; } } int set = temp[rows - 1][cols - 1]; for (int i = 0; i < rows; ++i) { delete[] temp[i]; } delete[] temp; return set; } int main() { int n[4][4] = { {1,10,3,8}, {12,2,9,6}, {5,7,4,11}, {3,7,16,5} }; int ret = getMaxValue_sonlution(n[0], 4, 4); cout << "能拿到最大价值的礼物:" << ret << endl; }
优化动态规划
因为我们每次向下和向右移动，所以我们可以用一维数组代替上面的二维数组,
空间复杂度为O(n);
C++
#include <iostream> using namespace std; int getMaxValue_sonlution(const int* values, int rows, int cols) { if (values == nullptr || rows <= 0 || cols <= 0) return 0; int* temp = new int[cols];//用来存储每步的做大价值 for (int i = 0; i < rows; ++i) { for (int j = 0; j < cols; ++j) { //保存前一步的最大价值 max(values[i-1][j]与values[i][j-1]) int maxnum = 0; if (0 == i && 0 == j) // 最开始 ; else if (0 == i) // 到最上边 maxnum = temp[j - 1]; else if (0 == j) // 到最左边 maxnum = temp[j]; else maxnum = max(temp[j - 1], temp[j]); temp[j] = values[i * cols + j] + maxnum; } } int ret = temp[cols - 1]; delete[] temp; return ret; } int main() { int n[4][4] = { {1,10,3,8}, {12,2,9,6}, {5,7,4,11}, {3,7,16,5} }; int ret = getMaxValue_sonlution(n[0], 4, 4); cout << "能拿到最大价值的礼物:" << ret << endl; }
本章完！
