蓝桥杯 试题 算法训练 拿金币 C++ 详解

蓝桥杯 试题 算法训练 拿金币 C++ 详解

题目：

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

---

前言：

请先阅读以下两篇文章：

https://blog.csdn.net/Auto918/article/details/121140800​​​​​​https://blog.csdn.net/weixin_53020123/article/details/122404298

一开始看到这道题，我想的是：穷举法。从左上角开始，尝试所有的路径，从中得到最大的数，便得到结果……但这样做又有问题：

1.不好标记已经走过的路径，倒可以再用数组保存路径，下次走的时候进行比较，但又更加麻烦。

2.不知道什么时候选择向右还是向下，结合路径重复的问题。

所以还是参考网上的答案，下面详细解释：

---

开始：

思路是：通过题意（只能向右和向下走的特性），从左上角开始，对每个数的上一个数和左一个数进行比较，累加大的。从左上角开始，向右下方向一直累加到右下角，得到结果。

以：

3
1 3 3
2 2 2
3 1 2

为例。

---

见图：（初始状态如下）

---

1.对橙色部分进行计算，通过比较其上一个数和左一个数，累加其中大的数。得到：

---

2.对蓝色部分进行计算，通过比较其上一个数和左一个数，累加其中大的数。得到：

---

3.对绿色部分进行计算，通过比较其上一个数和左一个数，累加其中大的数。得到：

---

 4.最终得到红色部分的结果。

---

其实解题运算过程不难，难的是怎么想到这样的方法去解题。

想得出的自然觉得毫无难度，想不出的绞尽脑汁都不行。

对此我也只能说，还没有养成好的编程思维，做题多了应该就有感觉了。

万丈高楼平地起，共勉。

---

最后附上代码：

#include
using namespace std;

int ii[1001][1001] = { 0 };
//温馨提示：对于这么大的数组，如果放到主函数体中是有语法警告，且运行之后有异常的。
//所以放在主函数体外。

int main()
{
	int n;
	cin >> n;

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

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			ii[i][j] += ((ii[i - 1][j] > ii[i][j - 1]) ? ii[i - 1][j] : ii[i][j - 1]);
		}
	}

	cout << ii[n][n];

	return 0;
}