目录
题目:
问题描述
输入格式
输出格式
解题过程
第一步 定义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]);
}
}
第二个方法貌似有时候过不了第九个评测样例,然后多测几次就能通过了,不知道是官方系统的问题还是。文章来源:https://www.toymoban.com/news/detail-796599.html
收获:
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模板网!