问题描述
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
输入格式
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。
输出格式
最多能拿金币数量。
样例输入
3
1 3 3
2 2 2
3 1 2
样例输出
11
数据规模和约定
n<=1000
首先展示我的代码：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int n;
scanf("%d",&n);
int b[1001][1001];
int i,j;
for (i=0;i<=1000;i++)
{
for(j=0;j<=1000;j++)
{
b[i][j]=0;
}
}
for (i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&b[i][j]);
}
}
for (i=1;i<=n;i++)
{
for (j=1;j<=n;j++)
{
if(b[i-1][j]>b[i][j-1])
{
b[i][j]+=b[i-1][j];
}
else
{
b[i][j]+=b[i][j-1];
}
}
}
printf("%d",b[n][n]);
return 0;
}
这是一道动态规划题，而题目已经给出了我们很明确的处理方案，利用二维数组，
而我这里设定二维数组的规模为1001是为了防止数据规模不够，按照道理来说设定规模为n+1也是可以的，但是不知道为什么测试就是报错，还有顺便提醒一下，蓝桥杯的程序需要以return 0结束不然测试会出现运行错误。
那么我们开始解析程序，
首先我们遍历来一次数组将其全部变成0，
这道题有点类似于求最佳带权路径，
所以有点像这个题，
只是每一步带上了权值，而每一次只能走下和右，所以自然我们就想到了取最大的那个，我最开始就是抱着这样的心态去算的，直接比较下和右的值哪个大就去哪个进入计数器，算到最后直接输出，但是这样有一个错误，那就是忽略了其他的格子，很明显就错了，只适用于一些特定的组合，
那么我们要怎么才能计算所有的路劲呢，很明显不可能单独计算每一条路径，那样的计算量很庞大，就有点类似于暴力算法了，所以我们需要想办法计算每一条路径，请看下图：
所有的图是从另一个博主哪里借用的具体查看
（https://blog.csdn.net/haduwi/article/details/120964125）
回到问题上来，如图（本图是机器人计算路径的所以借来用用，当然看成权值也是可以的）：
这是一个3*7的矩阵，那么很明显外围的格子都只有一条路劲可以到达，所以全部初始化为1，而我们需要求的是带权路径所以我们初始化为0，这样不会使我们计算出来的权值偏大，那么第二行的数字是怎么回事呢，最开始我比较傻，以为是有规律的比如等差数列，琢磨半天才看懂，是左边的值和上面的值相加得到的，比如2=1+1， 10=6+4，这不就是我们的路径选择规则么，而对应的数字就意味着到这个格子有多少条路径，比如第二行的7，因为抵达他左边的格子有6条路径，抵达上面的格子就一条路径（按照走格子的规则啊），所以一共是7条，那么联系到取金币上，我们只需要将对应数组上的数值改变相加就行了，依次相加，最后一个格子就是我们需要的最大值，当然我们的权值进行累加也不是乱加的，我们需要选择我们下一步需要走的格子的上面或者左边的大的那一个进行累加。