首页 > 试题广场 >

数字三角形

[编程题]数字三角形

热度指数：2142 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

    7
   3 8
  8 1 0
2 7 4 4
4 5 2 6 5
如上图所示，从一个数字三角形的顶部走到底部有很多条不同的路径，规则是只能从当前节点走到下一层相邻的节点，即下一层的左边或右边。例如第三行第二个数字“1”只能走到第四行的第二个数字“7”与第三个数字“4”。
请寻找最佳一条路径，使得这条路径上节点的数字总和最大。

输入描述:

输入包含多组。每组数据的第一行包含一个正整数n（1≤n≤100），代表三角形的层数。

紧接着有n行数字，第i（1≤i≤n）行包含i个自然数。

输出描述:

对应每组数据，输出最大的和。

示例1

输入

输出

算法知识视频讲解

Java

别骂了别骂了

注意两点：

1.while循环输入，处理多个case

2.使用数组存已经计算好的代价，去掉重复计算，降低时间复杂度

import java.util.Scanner;

public class Main {
    public static  int MaxSum(int x,int y,int N,int[][] array,int[][] maxSum )
    {
        if(maxSum[x][y]!=-1)
        {
            return maxSum[x][y];
        }
        if(x==N-1)
        {

            return maxSum[x][y]=array[x][y];
            
        }
        else
        {
            int xx=MaxSum(x+1,y,N,array,maxSum);
            int yy=MaxSum(x+1,y+1,N,array,maxSum);
            maxSum[x][y]=Math.max(xx,yy)+array[x][y];
            return maxSum[x][y];
        }
    }

    public static void main(String[] args) {
        int N;
        Scanner reader =new Scanner(System.in);
        while(reader.hasNextInt())
        {
            N = reader.nextInt();
            int[][] array=new int [N][N]; 
            int[][] maxSum=new int[N][N];
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<=i;j++)
                {
                    maxSum[i][j]=-1;
                }
            }
            for(int i=0;i<N;i++)
            {
                for(int j=0;j<=i;j++)
                {
                    array[i][j]=reader.nextInt();
                }
            }
            System.out.println(MaxSum(0,0,N,array,maxSum));
        }
    }
}

发表于 2019-09-04 20:49:33 回复(0)

Java

安徒生的谎言

import java.util.Scanner;

public class TrangleDemo {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()) {
            int n=sc.nextInt();
            int[][] nums=new int[n][n];
            for(int i=0;i<n;i++) {
                for(int j=0;j<=i;j++) {
                    nums[i][j]=sc.nextInt();
                }
            }
            int[][] dp=new int[n][n];
            for(int i=n-1;i>=0;i--) {
                for(int j=0;j<=i;j++) {
                    if(i==n-1) {
                        dp[i][j]=nums[i][j];
                    }else {
                        dp[i][j]=Math.max(dp[i+1][j]+nums[i][j], dp[i+1][j+1]+nums[i][j]);
                    }
                    
                }
            }
            System.out.println(dp[0][0]);
        }
    }
}

发表于 2018-01-26 14:54:45 回复(0)

Java

詆調壹點

import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int n = sc.nextInt();
			int[][] arr = new int[n][];
			for (int i = 0; i < n; i ++ ) {
				int[] a = new int[i + 1];
				for (int j = 0; j < i + 1; j ++ ) {
					a[j] = sc.nextInt();
				}
				arr[i] = a;
			}
			for (int i = n - 1; i >= 0; i -- ) {
				for (int j = 0; j < i; j ++ ) {
					arr[i - 1][j] += arr[i][j] > arr[i][j + 1] ? arr[i][j] : arr[i][j + 1];
				}
			}
			System.out.println(arr[0][0]);
		}
	}
}

发表于 2016-10-13 00:25:12 回复(0)

Java

ZhanHeng

import java.util.Scanner;

//经典的动态规划问题，把状态转移方程弄出来整个题目就一目了然！
public class Main {
	public static int getMaxPathValue(int[][] arr , int n){
		int[][] dp = new int[n+1][n+1];
		//初始化第一列 , 值累加
		for (int i = 1; i <=n; i++) {
			dp[i][1] = dp[i-1][1]+ arr[i][1];
		}
        int max = dp[1][1] ;
		for (int i = 2; i <=n; i++) {
			for (int j = 2; j <=i ; j++) {  //dp[i][j]的值要不来自正上方 、要不来自左上方 , 顺便记录最大值
				dp[i][j] = Math.max(dp[i-1][j] + arr[i][j], dp[i-1][j-1]+ arr[i][j]);
				max = Math.max(max, dp[i][j]);
			}
		}
		return max;
	}
	public static void main(String[] args) {
		Scanner cin = new Scanner(System.in);
		while (cin.hasNextInt()) {
			int n = cin.nextInt();
			int[][] arr = new int [n+1][n+1];
			for (int i = 1; i <=n ; i++) {
				for (int j = 1; j <=i ; j++) {
					arr[i][j] = cin.nextInt();
				}
			}
			System.out.println(getMaxPathValue(arr, n));
		}
	}
}

发表于 2016-09-03 18:43:39 回复(0)