蓝桥杯 算法提高 拿金币（C++）

1. 题目

1.1 资源限制1.2 问题描述1.3 输入格式1.4 输出格式1.5 样例输入1.6 样例输出1.7 数据规模及约定 2. 题目分析

2.1 关键字2.2 题目分析 3. 代码书写4. 代码：

  时间限制：1.0s 内存限制：256.0MB

  有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

  第一行输入一个正整数n。
  以下n行描述该方格。金币数保证是不超过1000的正整数。

  最多能拿金币数量。

  3
  1 3 3
  2 2 2
  3 1 2

  11

  n<=1000

  你站在最左上角的格子里，每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

由于需要获取到最多的金币，那么我们需要走过尽可能多的格子，来获取金币，结合本题对于行走方式的限制，那么，本题的行走起点就是左上角，行走终点就是右下角。在行走的过程中，关于下一步的行走，有两种选择：向右或者向下；那么，反过来想，想要行走到当前的格子，也有两种可能：从上方的格子向当前格子行走或者从左侧格子向当前格子行走。将问题（获取到最多的金币数），简化为子问题（行走到某一个格子能够获取到的最大金币数），即，将某一个格子的左侧的格子和上方的格子中的金币数进行比较，选取较大的，再与本格子的金币数相加，从而获取到单个格子的最优解。

创建两个二维数组，注意：在主函数外部进行声明

int gold[1001][1001]; 	//金币数组
int dp[1001][1001];		//dp数组

初始化金币数组

for(int i = 1; i <= n; i++) {
	for(int j = 1; j <= n; j++) {
		cin >> gold[i][j];
	}
}

  以“样例输入”为例，我们可以得到如下所示的一个金币数组：

初始化dp数组，考虑到最左上方的格子并不存在“上方格子和左侧格子”，故需要进行初始化。

//初始化dp数组
dp[0][1] = dp[1][0] = 0;

  初始化后的dp数组如下所示：

对dp数组中的值进行计算：选取“金币数组”中对应位置的值进行计算，这里的dp数组中的每一个元素可以理解为选取最优解能够获取到的金币数

for(int x = 1; x <= n; x++) {
	for(int y = 1; y <= n; y++) {
		dp[x][y] = max(dp[x - 1][y], dp[x][y - 1]) + gold[x][y];
	}
} 

经过上述的过程后，可以获取到的dp数组如下：

#include
using namespace std;

//大型数组在外部进行说明 
int gold[1001][1001];
int dp[1001][1001];

int max(int a, int b) {
	return a > b ? a : b;
}

int main() {
	int n;
	cin >> n;
	
	//初始化金币数组 
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			cin >> gold[i][j];
		}
	}
	
	//初始化dp数组
	dp[0][1] = dp[1][0] = 0;
	
	for(int x = 1; x <= n; x++) {
		for(int y = 1; y <= n; y++) {
			dp[x][y] = max(dp[x - 1][y], dp[x][y - 1]) + gold[x][y];
		}
	} 
	
	cout << dp[n][n] << endl;
	return 0;
}