Java解题--练习解题阶段(无序阶段)-ALGO-1006 拿金币

àì夳堔傛蜴生んèń 2024-03-25 16:45 21阅读 0赞

### 题目 ###

算法训练 拿金币

资源限制

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

问题描述

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

输入格式

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

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

输出格式

最多能拿金币数量。

样例输入

1 3 3

2 2 2

3 1 2

样例输出

数据规模和约定

n<=1000

### 解题思路 ###

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

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

![dd9aeed16728b15a0c38f94a654c0cb2.png][]

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

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

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

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

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

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

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

所有可以正确执行输出

![b8432142ab47ddd57d5248e10d5fbba6.png][]

### 代码实现 ###

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

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 stub
            Scanner 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);
    
        }
    
    
    
    }

#### 方法二 ####

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]);        
        }
    
    
    }

![7b1746d372bbee8710f22608f52f2ef9.png][]

[dd9aeed16728b15a0c38f94a654c0cb2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5fa7f71e26de4063ae92764bbae4e177.png
[b8432142ab47ddd57d5248e10d5fbba6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/83af157e0bee4b0388dab70a6fc93ba9.png
[7b1746d372bbee8710f22608f52f2ef9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/030729d7f2c74dd6b0e876acc4279781.png