剑指Offer - 面试题47：礼物的最大价值

题目

在一个m*n的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值(价值大于0)。你可以从棋盘的左上角开始拿格子里的礼物，并每次向左向下移动一格，直到到达棋盘的右下角。给定一个棋盘及其上面的礼物，请计算你最多能拿到多少价值的礼物？
例如，在下面的棋盘中，如果沿着带下画线的数字的路线(1、12、5、7、7、16、5)。那么我们能拿到最大价值为53的礼物。

分析

动态规划

我们创建一个等同棋盘的二维数组，每个位置用记录前一步到这一步的能拿到的最多价值。
如下图，每一步都是拿到的最多价值。空间复杂度为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*[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;
}

本章完！