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

发布时间:2024年01月14日

目录

题目:

问题描述

输入格式

输出格式

解题过程

第一步 定义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中隔一个空格后就会进行下一个变量的输入。

文章来源:https://blog.csdn.net/weixin_72939806/article/details/135566038
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。