Java实现格子取数问题
JAVA 实现 问题 格子 取数
2023-09-14 08:58:12 时间
1 问题描述
有n*n个格子,每个格子里有正数或者0,从最左上角往最右下角走,只能向下和向右走,一共走两次(即从左上角往右下角走两趟),把所有经过的格子里的数加起来,求总和的最大值。如果两次经过同一个格子,则最后求得的总和中该格子中的数只加一次。
2 解决方案
此处采用动态规划法,可以较大的提高时间效率。
package com.liuzhen.practice;
import java.util.Scanner;
public class Main {
public boolean judge(int s, int i ,int j ,int len) {
int x1 = s - i, x2 = s - j;
if(x1 >= 0 && x1 < len && x2 >= 0 && x2 < len && i >= 0 && j >= 0 && i < len && j < len)
return true;
return false;
}
public int getValue(int[][][] dp, int s, int i , int j, int len) {
if(judge(s, i, j, len))
return dp[s][i][j];
return -1;
}
public void getResult(int[][] value) {
int len = value.length;
int[][][] dp = new int[len * 2][len][len];
dp[0][0][0] = value[0][0];
for(int s = 1;s <= len * 2 - 2;s++) {
for(int i = 0;i < len;i++) {
for(int j = 0;j < len;j++) {
if(judge(s, i, j, len)) {
if(i != j)
dp[s][i][j] = Math.max(Math.max(getValue(dp,s-1,i-1,j-1,len),getValue(dp,s-1,i,j,len)),
Math.max(getValue(dp,s-1,i-1,j,len), getValue(dp,s-1,i,j-1,len))) + value[i][s-i] + value[j][s-j];
else
dp[s][i][j] = Math.max(getValue(dp,s-1,i-1,j-1,len),
Math.max(getValue(dp,s-1,i-1,j,len), getValue(dp,s-1,i,j,len))) + value[i][s-i];
}
}
}
}
System.out.println(dp[2 * len - 2][len - 1][len - 1]);
return;
}
public static void main(String[] args) {
Main test = new Main();
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] value = new int[n][n];
for(int i = 0;i < n;i++)
for(int j = 0;j < n;j++)
value[i][j] = in.nextInt();
test.getResult(value);
}
}
运行结果:
0 0 3 0 2 0
0 3 0 0 0
0 3 0 0 0
0 0 0 4 0
0 0 0 4 0
0 3 0 0 0
0 0 0 0 0 0 0 0
0 13 0 0 6 0 0
0 0 0 7 0 0 0
0 0 14 0 0 0 0
21 0 0 0 4 0 0
0 15 0 0 0 0 0
14 0 0 0 0 0 0
0 0 0 0 0 0 0
相关文章
- Java实现 蓝桥杯 算法训练VIP 报数(暴力+数学)约瑟夫环问题
- Java实现 LeetCode 719 找出第 k 小的距离对(二分搜索法+二分猜数字)
- Java实现 LeetCode 433 最小基因变化
- Java实现 LeetCode 417 太平洋大西洋水流问题
- Java实现 LeetCode 377 组合总和 Ⅳ
- Java实现洛谷 P2802 回家
- Java实现 洛谷 P2024 [NOI2001]食物链
- Java实现 洛谷 P1115 最大子段和
- Java实现 洛谷 P1421 小玉买文具
- java实现亲密数
- java实现迷宫问题
- java实现找素数
- java实现找素数
- Java实现第九届蓝桥杯倍数问题
- Java实现最小费用最大流问题
- Java实现硬币收集问题
- Java实现预排序
- Java实现汉诺塔问题
- Java实现汉诺塔问题
- Java实现 蓝桥杯VIP 算法提高 阮小二买彩票
- Java实现 蓝桥杯VIP 基础练习 报时助手
- Java实现 蓝桥杯 算法训练 删除数组零元素
- (Java实现) 工作分配问题
- (Java实现) 装载问题
- (Java实现) 最大团问题 部落卫队
- Java实现单例模式的9种方法
- 通过Java实现斗地主
- JAVA集合类(代码手写实现,全面梳理)
- 基于JAVA实现的WEB端UI自动化 - WebDriver框架篇 - ant使用 - ant安装、环境变量配置、ant实例及运行Ant Build 出现问题的解决方法