快捷搜索:

试题 算法训练 拿金币-蓝桥杯

这里的关键字仍然是动态规划。 动态规划核心:拆分子,记住过往,减少重复计算,计算结果。

1.不难发现,对于某个确定的路径上的特定位置上的金币总数,总是由该位置的上方的值或左边的值确定的。所以遍历数组位置的上方和左边的 再 比较 递加,就能计算出N*N方格中的最大金币数。

这就是拆分子的逻辑。

2.在循环中不断用数组存储计算出的值并不断 递进 ,便是记住过往,减少重复计算,并用于计算结果。

/*
		拿金币 :动态规划 
		2022/1/28  fevergo  明鹊。。。
		希望对你有帮助  
*/
#include<iostream>
using namespace std;
int a[1001][1001] = {0}; // 数组初始化为零 
int main()
{
	int n;
	cin>>n;
	
	for(int i = 1;i<=n;i++) // 输入 
	for(int j = 1;j<=n;j++)
	cin>>a[i][j];
	
	 // 从下标 1 开始,便于 上方和左边数组值 的 比较  
	for(int i = 1;i<=n;i++)
	for(int j = 1;j<=n;j++)
	{
		if(a[i-1][j]>=a[i][j-1]) 
		{
			a[i][j] += a[i-1][j];
		}
		else 
		{
			a[i][j] += a[i][j-1];
		}	
	}
	
	cout<<a[n][n]; // 输出 
	
	return 0;
}
经验分享 程序员 职场和发展