题目

算法训练 拿金币

资源限制

内存限制：256.0MB C/C++时间限制：1.0s Java时间限制：3.0s Python时间限制：5.0s

问题描述

　　有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以从一个格子走到它右边或下边的格子里。请问如何走才能拿到最多的金币。

输入格式

　　第一行输入一个正整数n。

　　以下n行描述该方格。金币数保证是不超过1000的正整数。

输出格式

　　最多能拿金币数量。

样例输入

3

1 3 3

2 2 2

3 1 2

样例输出

11

数据规模和约定

　　n<=1000

解题思路

刚开始是考虑，每一步考虑当前情况，两个方向的最大值，，永远向最大值走，通过计数累加金币数

但儒道如下类似状况，会出现错误，因为她路径前面的数字小，所有会错过，

后来根据是扫雷的启发，在每一个位置上累加出来他可能的最大值，

并且扩展边界来保证下标不越界，实际上也符合规律

求每个位置上，是加左边的大还是加上面的大，

然后再当前位置上累加，就代表做到这个位置上最大可以有多少金币

这种方法就是没有明确的坐标，没有明确的位置，对于最初的想法来说

因为我们会遍历每一个坐标，所有不会遗漏，

因为规定只能向右向下，所有我们的遍历方法，再每一个位置他的左边和上边都是已经固定的，

所有可以正确执行输出

代码实现

方法一别看了，是最开始的错误写法，下面的是正解

package 蓝桥解题集;import java.text.Format;
import java.util.Date;
import java.util.Scanner;public class ALOG1006拿金币 {public static void main(String[] args) {// TODO Auto-generated method stubScanner sc = new Scanner(System.in);
//        int n = 3;
//        int[][] arr = {
//                {1,3,3},
//                {2,2,2},
//                {9,1,2},
//        } ;int n = sc.nextInt();int[][] arr = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {arr[i][j] = sc.nextInt();}}///int count = 1;int x =0,y =0;for (int i = 0; i < (2*n)-1; i++) {if (x+1>n-1) {x--;y++;if (y+1>n-1) {if (x+1==n-1&&y+1==n) {//到达最有或者最下//只能往一个方向走x++;System.out.println("向右");count+=arr[x][y];if (x==n-1) {break;}}y--;}}if (y+1>n-1) {y--;x++;if (x+1>n-1) {if (x+1==n&&y+1==n-1) {//到达最有或者最下//只能往一个方向走y++;System.out.println("向下");count+=arr[x][y];if (y==n-1) {break;}}x--;}}if (arr[x+1][y]>arr[x][y+1]) {x++;System.out.println(arr[x][y]+":"+x+":"+y);count += arr[x][y];}else {y++;System.out.println(arr[x][y]+":"+x+":"+y);count += arr[x][y];                }}//System.out.println(count);}}

方法二

3

1 3 3

2 2 2

9 1 3

///使用的 自己的测试，因为题目测试样例，即使方法一也嫩正确，这个样例可以屏蔽掉部分蒙对的情况，

package 蓝桥解题集;import java.io.*;
import java.util.LinkedList;
import java.util.Scanner;public class ALOG1006拿金币_3 {public static void main (String[]args)throws IOException {Scanner in = new Scanner(System.in);int n = in.nextInt();    int[][] dp = new int[n+1][n+1];for (int i = 1; i <=n ; i++) {for (int j = 1; j <=n ; j++) {int m = in.nextInt();    dp[i][j]=m;}}for (int i = 1; i <=n ; i++) {for (int j = 1; j <=n ; j++) {int up = dp[i-1][j];int left = dp[i][j-1];if (up>left) {dp[i][j] += up;}else {dp[i][j] += left;}}}System.out.println(dp[n][n]);        }}