bluess

用户名：bluess

访问量：2725

签　名：

等　　级
排　　名	24168
经　　验	622
参赛次数	0
文章发表	3
年　　龄	0
在职情况	学生
学　　校	东莞理工学院
专　　业

　　自我简介：

TA的其他文章

三角形-题解(Java代码) 递归记忆化搜索
浏览：629

你可能喜欢

三角形-题解(Java代码) 递归记忆化搜索

　　作者: bluess　　　　发表时间：2019-12-01 13:47:50 浏览：629　|　评论：0　

原题链接：三角形

第一次解这题时直接用了递归算法，结果50%超时，于是就用记忆化搜索优化一下递归，就是用一个容器将递归中会重复计算的值装起来，等到要进行重复计算时直接调用这个值免去了重复计算的步骤

import java.util.Scanner;
    
    public class Main {
    	public static void main(String args[]){
    		Scanner sc=new Scanner(System.in);
    		int n=sc.nextInt();
    		while(n!=0){
    			int num=sc.nextInt();
    			int nums[][]=new int[num][num];
    			Contain contain[][]=new Contain[num][num];
    			for(int i=0;i<num;i++){
    				for(int j=0;j<i+1;j++){
    					nums[j][i]=sc.nextInt();
    					contain[j][i]=new Contain(-1);//初始化对象数组便于存放某条路径的值
    				}
    			}
    			System.out.println(count(nums,0,0,num,contain));//调用函数求三角形底部到顶点p(0,0)路径的最大值
    			n--;
    		}
    	}
    	
    	public static long count(int nums[][],int i,int n,int num,Contain contain[][]){//递归+记忆化搜索算法
    		long result=nums[i][n];
    		if(n!=num-1){//当路径未到达底部时调用递归
    			if(contain[i][n].value!=-1)//若对象数组中已存放了路径的最大值则直接返回该值，标记为对象的value值不为-1
    				return contain[i][n].value;
    			else{//若三角形底部对应点p(i,n)路径的最大值未存进对象数组，则需要调用递归算法进行计算
    				contain[i][n].value=result+max(count(nums,i,n+1,num,contain),count(nums,i+1,n+1,num,contain));
    				return contain[i][n].value;
    			}
    		}
    		else//当对象到达底部时直接返回result即p(i,n)点的值
    			return result;
    	}
    	public static long max(long a,long b){
    		if(a<b)
    			return b;
    		else
    			return a;
    	}
    }
    class Contain{//一个简单的类相当于结构体，用来存放已经求出的三角形底部到p(i,j)点的最大值
    	long value;
    	public Contain(long value) {
    		super();
    		this.value = value;
    	}
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

bluess

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【出圈】（C语言代码）用单项循环链表

C语言训练-斐波纳契数列（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

三角形-题解(Java代码) 递归记忆化搜索

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

模拟计算器（C++代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

判定字符位置（C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

小O的图案（C语言代码）

C语言训练-排序问题<1> （C语言代码）

bluess

TA的其他文章

你可能喜欢

关于逻辑非“！”与取反“~”运算符

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

【出圈】 （C语言代码）用单项循环链表

C语言训练-斐波纳契数列 （C语言代码）

C语言训练-求矩阵的两对角线上的元素之和 （C语言代码）

三角形-题解(Java代码) 递归记忆化搜索

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题11.1 （C语言代码）

WU-蓝桥杯算法提高VIP-企业奖金发放 （C++代码）

C语言程序设计教程（第三版）课后习题5.8 （C语言代码）

模拟计算器 （C++代码）

C语言程序设计教程（第三版）课后习题11.8 （C语言代码）

判定字符位置 （C语言代码）

C语言程序设计教程（第三版）课后习题7.3 （C语言代码）

小O的图案 （C语言代码）

C语言训练-排序问题<1> （C语言代码）

【出圈】（C语言代码）用单项循环链表

C语言训练-斐波纳契数列（C语言代码）

C语言训练-求矩阵的两对角线上的元素之和（C语言代码）

　　评论区

WU-蓝桥杯算法提高VIP-企业奖金发放（C++代码）

模拟计算器（C++代码）

判定字符位置（C语言代码）

小O的图案（C语言代码）