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

这篇具有很好参考价值的文章主要介绍了蓝桥杯备赛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]);
    }
}

 报错:内存超限

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

蓝桥杯备赛day02 -- 算法训练题 拿金币Java,蓝桥杯java组备赛,蓝桥杯,算法,职场和发展,java,动态规划,开发语言
随即就开始想办法优化。

要么将两个数组合并成一个数组,也就是用一开始用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://www.toymoban.com/news/detail-796599.html

到了这里,关于蓝桥杯备赛day02 -- 算法训练题 拿金币Java的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 蓝桥杯备赛 | 洛谷做题打卡day5

    题目描述 小 K 喜欢翻看洛谷博客获取知识。每篇文章可能会有若干个(也有可能没有)参考文献的链接指向别的博客文章。小 K 求知欲旺盛,如果他看了某篇文章,那么他一定会去看这篇文章的参考文献(如果他之前已经看过这篇参考文献的话就不用再看它了)。 假设洛谷

    2024年01月17日
    浏览(58)
  • 蓝桥杯备赛 | 洛谷做题打卡day2

    ​ 题目来源:洛谷P2670 [NOIP2015 普及组] 扫雷游戏 NOIP2015 普及组 T2 扫雷游戏是一款十分经典的单机小游戏。在 n n n 行 m m m 列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示

    2024年01月16日
    浏览(58)
  • 蓝桥杯备赛 day 3 —— 高精度(C/C++,零基础,配图)

    目录 🌈前言: 📁 高精度的概念 📁 高精度加法和其模板 📁 高精度减法和其模板 📁 高精度乘法和其模板 📁 高精度除法和其模板 📁 总结         这篇文章主要是准备蓝桥杯竞赛同学所写,为你更好准备蓝桥杯比赛涉及的算法知识点。不知道你是否苦恼于不知算法从何

    2024年01月18日
    浏览(41)
  • 【蓝桥杯备赛Java组】语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月21日
    浏览(70)
  • 【蓝桥杯备赛Java组】第一章·语言基础|竞赛常用库函数|输入输出|String的使用|常见的数学方法|大小写转换

    🎥 个人主页:深鱼~ 🔥收录专栏:蓝桥杯 🌄欢迎 👍点赞✍评论⭐收藏 目录 一、编程基础 1.1 Java类的创建  1.2 Java方法  1.3 输入输出  1.4 String的使用 二、竞赛常用库函数 1.常见的数学方法 2.大小写转换 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,

    2024年01月19日
    浏览(72)
  • 蓝桥杯备赛|成绩统计|排列字母|纸张尺寸

    目录   1 成绩统计 题目描述 输入描述 输出描述 输入输出样例 示例 1.1 解题思路 1.2 AC_Code Python 标程 2 排列字母 问题描述 2.1 解题思路 2.2 AC_Code Python 标程 3 纸张尺寸 问题描述 输入格式 输出格式 样例输入1 样例输出1 样例输入 2 样例输出 2 运行限制 3.1 解题思路 3.2 AC_Code P

    2023年04月09日
    浏览(41)
  • 【AcWing】蓝桥杯备赛-深度优先搜索-dfs(1)

    目录 写在前面: 题目:92. 递归实现指数型枚举 - AcWing题库 读题: 输入格式: 输出格式: 数据范围: 输入样例: 输出样例: 解题思路: 代码: AC !!!!!!!!!! 写在最后: 距离蓝桥杯已经不足一个月了, 根据江湖上的传言, 蓝桥杯最喜欢考的是深度优先搜索和

    2024年02月03日
    浏览(54)
  • 蓝桥杯备赛之动态规划篇——涂色问题(区间DP)

    2023第十四届蓝桥杯模拟赛第二期个人题解(Java实现) 2023第十四届蓝桥杯模拟赛第三期个人题解(Java实现) 蓝桥杯备赛之动态规划篇——背包问题 蓝桥杯真题——单词分析(Java实现) 😘😘 哈喽,大家好!这里是蓝桥杯系列文章的动态规划章节🔥🔥,今天要讲解的是区

    2024年01月23日
    浏览(48)
  • 算法竞赛备赛之贪心算法训练提升,贪心算法基础掌握

    905.区间选点 给定N个闭区间[ai, bi],请你在数轴上选择尽量少的点,使得每个区间内至少包含一个选出的点。 输出选择的点的最小数量,位于区间端点上的点也算作是区间内。 将每个按区间的右端点从小到大排序 从前往后依次枚举每个区间 如果当前区间中已经包含点,则直

    2024年02月08日
    浏览(35)
  • 算法竞赛备赛进阶之数位DP训练

    数位DP的思想就是对每一位进行DP,计算时记忆化每一位可以有的状态,其作用是减少运算时间,避免重复计算。 数位DP是一种计数用的DP,一般就是要统计一个区间[A,B]内满足一些条件数的个数。 以1e9甚至1e18、1e100的问题为例,因为在统计情况下有很多重复的计算,数位DP实

    2024年01月16日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包