[数据结构与算法]蓝桥杯练习题---有一个N x N的方格每一个格子都有一些金币只要站在格子里就能拿到里面的金币。你站在最左上角的格子里每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币.

#include<iostream>
#include <cstring>
#include<algorithm>
using namespace std;
const int N = 1005;
int b[N][N]={0};
int main()
{
? ? int n;
? ? cin>>n;
? ? ?for(int i=1;i<=n;i++)
? ? ? ? for(int j=1;j<=n;j++)
? ? ? ? ? ? cin>>b[i][j];

? ? ? for(int i=1;i<=n;i++)
? ? ? ? for(int j=1;j<=n;j++)
? ? ? ? ? ? b[i][j]=max(b[i][j-1]+b[i][j],b[i-1][j]+b[i][j]);

? ? ?cout<<b[n][n]<<endl;
? ? ?return 0;
}

这是一道简单的动态规划题目?

解决该题的主要思路是如何求出b[i][j] 我们采取从利用前面一种位置的状态求这个位置的状态

b[i][j]的意思是从数组最左上方到这个位置取得的最大值(累加起来的)

显然得出b[i][j]只有两种情况

1.b[i-1][j] 其左边的元素加上这个原来位置b[i][j]的值

2.b[i][j-1] 其上面边的元素加上这个原来位置b[i][j]的值

然后就是两者求最大值调用max函数就行啦