蓝桥杯备赛day02 -- 算法训练题 拿金币Java

目录

题目：

问题描述

输入格式

输出格式

解题过程

第一步 定义dp数组

第二步 确定 dp 数组递推公式

?第三步 dp数组的初始化

第四步 dp数组的遍历顺序

第五步 举例说明

?报错：内存超限

用dp数组去存储位置上的金币

dp数组从二维降为一维

?收获：

---

?

题目：

问题描述

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

输入格式

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

输出格式

　　最多能拿金币数量。

样例输入

3
1 3 3
2 2 2
3 1 2

样例输出

11

数据规模和约定

n<=1000

---

解题过程

这是一道很明显的动态规划问题，那就老规矩动态规划五部曲。

第一步 定义dp数组

采用二维数组dp[ i ][ j ]，定义为到第i行第j列时，拿到的最大金币数。

因此在定义数组长度时，需要是（n+1）*（n+1）

（因为数组索引从0开始）

又采用gold[ i ][ j ]数组，存储位置上的金币。

第二步 确定 dp 数组递推公式

我们只能往右走或者往下走，那么到达第i行第j列的位置，只能是从[ i ][ j-1 ]的位置（往右走）或者[ i-1 ][ j ] 的位置（往下走），

那么到[ i ][ j ]拿的金币应该为[ i ][ j-1 ]和[ i-1 ][ j ] 两者拿金币的最大值 加上[ i ][ j ]位置上的金币。

即

dp[i][j] = (Math.max(dp[i-1][j], dp[i][j-1]) + gold[i][j]);

?第三步 dp数组的初始化

• 显然，在起点时，dp[1][1] = gold[1][1]。
• 在第一行时，我们只能往右走，这时dp[ i ][ j ] = dp[ i ][ j-1 ] + gold[ i ][ j ]。? ? ? ? ? ? ? ? ? ? ? ? ?（注意往右是对 j 的变换，因此是 j-1 ）
• 在第一列时，我们只能往下走，这时dp[ i ][ j ] = dp[ i-1 ][ j ] + gold[ i ][ j ]。? ? ? ? ? ? ? ? ? ? ? ? ?（注意往下是对i的变换，因此是 i-1 ）

第四步 dp数组的遍历顺序

从左上角走到右下角，显然是i++，j++。?

第五步 举例说明

没啥可举例的哈。

最终代码如下，

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] dp = new int [n+1][n+1];
        int[][] gold = new int [n+1][n+1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++ )
                gold[i][j] = scanner.nextInt();
        dp[1][1] = gold[1][1];
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 1 && j == 1) dp[i][j] = gold[1][1];
                else if(i == 1) dp[i][j] = dp[i][j-1] + gold[i][j];
                else if(j == 1) dp[i][j] = dp[i-1][j] + gold[i][j];
                else dp[i][j] = (Math.max(dp[i-1][j], dp[i][j-1]) + gold[i][j]);
            }
        }
        System.out.println(dp[n][n]);
    }
}

?报错：内存超限

乐，最终报错了，内存超限。十个评测记录，到第八个走不出来了。

随即就开始想办法优化。

要么将两个数组合并成一个数组，也就是用一开始用dp数组去存储位置上的金币，

要么将dp数组从二维降为一维。

用dp数组去存储位置上的金币

实际上操作跟之前没有什么不同，而且也是可行的。

因为数组是从左到右，从上到下遍历的，dp[ i ][ j ] 修改后，就不需要起存储该位置上的金币的作用了，也就是时间错开了一下，从而起到数组有两个作用而不冲突。

代码如下

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] dp = new int[n+1][n+1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++ )
                dp[i][j] = scanner.nextInt();//用dp数组去存储位置上的金币
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(i == 1 && j == 1) dp[i][j] = dp[i][j]; 
                else if(i == 1) dp[i][j] = dp[i][j-1] + dp[i][j];
                else if(j == 1) dp[i][j] = dp[i-1][j] + dp[i][j];
                else dp[i][j] = (Math.max(dp[i-1][j], dp[i][j-1]) + dp[i][j]);
            }
        }
        System.out.println(dp[n][n]);
    }
}

dp数组从二维降为一维

• 关键在于一个理清时间的思维。
• 初始化时，我们用dp数组去存储第一行各位置，能拿到的最大金币。
• 在最后一个for循环中，实现了先搜索第i行中的最大金币数，在搜索第i+1行的效果。
  • 两种情况，当j==1时，dp[j] += gold[i][j]，意味着上一行中的dp[j]，加上位置上的金币数，等于这一行第j列拿到的最大金币数。
  • 否则dp[j] = Math.max(dp[j-1],dp[j]) + gold[i][j]。其中max函数中的dp[j-1]意味着从左边来的，也就是左边位置的最大金币数，与从上边来（上一行）的最大金币数去最大值，加上位置上的金币数。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[][] gold = new int[n+1][n+1];
        int[] dp = new int [n+1];
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                gold[i][j] = scanner.nextInt();
        //初始化
        for(int j = 1; j <= n; j++) {
            if(j == 1) dp[1] = gold[1][j];
            else dp[j] = dp[j-1] + gold[1][j];
        }
        for(int i = 2; i <= n; i++) {
            for(int j = 1; j <= n; j++) {
                if(j == 1) dp[j] += gold[i][j];
                else dp[j] = Math.max(dp[j-1],dp[j]) + gold[i][j];
            }
        }
        System.out.println(dp[n]);
    }
}

?第二个方法貌似有时候过不了第九个评测样例，然后多测几次就能通过了，不知道是官方系统的问题还是。

?收获：

for(int i = 1; i <= n; i++) 
    for(int j = 1; j <= n; j++ )
        num[i][j] = scanner.nextInt();

实现样例输入，看来java中隔一个空格后就会进行下一个变量的输入。