试题 算法训练 拿金币-蓝桥杯
这里的关键字仍然是动态规划。 动态规划核心：拆分子，记住过往，减少重复计算，计算结果。
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;
}
上一篇：
92天倒计时，蓝桥杯省赛备赛攻略来啦~
下一篇：
做程序员是一种什么感受？