问题描述
有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。
输入格式
第一行输入一个正整数n。
以下n行描述该方格。金币数保证是不超过1000的正整数。
输出格式
最多能拿金币数量。
解题思路
因为要求最多能拿多少金币,所以就想到了贪心,每次都从右边或下边选最大的那个,但这样并不合理,可能会错过最佳选择;还有就是联想到了AOE网,能不能倒着从终点往回找。最后的思路来自知乎用户 一棵小树,对每一个方格都考虑其上方和左边哪个更大,把大的那个金额加到现在的这个方格,代码如下。
满分代码
注意!!!我在之前就发现用变量定义的二维数组在初始化时必须使用双层的for循环,这次也是一样,而且必须全都初始化了结果才不会错。
#include <stdio.h>
int main(void){
int n;
scanf("%d",&n);
int a[n+1][n+1];
int i=0,j=0;
for(i=0;i<=n;i++){
for(j=0;j<=n;j++)
a[i][j]=0;
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
scanf("%d",&a[i][j]);
}
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
a[i][j]+= a[i][j-1]>a[i-1][j] ? a[i][j-1]:a[i-1][j];
}
printf("%d",a[n][n]);
return 0;
}
最后,种一棵树最好的时机是在十年前,第二好的时机是现在。