【藍橋杯省賽JavaB組真題詳解】數字三角形（2020）

題目描述

數字三角形

上圖給出了一個數字三角形。從三角形的頂部到底部有很多條不同的路徑。

對于每條路徑，把路徑上面的數加起來可以得到一個和，你的任務就是找到最大的和。

路徑上的每一步隻能從一個數走到下一層和它最近的左邊的那個數或者右邊的那個數。此外，向左下走的次數與向右下走的次數相差不能超過 1。

時間限制: 1.0s 記憶體限制: 512.0MB 本題總分：20 分

輸入格式

輸入的第一行包含一個整數 N (1 < N ≤ 100)，表示三角形的行數。下面的N 行給出數字三角形。數字三角形上的數都是 0 至 100 之間的整數

輸出格式

輸出一個整數

輸入樣例

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

           

輸出樣例

27

解題思路

遞歸

import java.util.Scanner;

public class Digui {
	static int[][] arr=new int [100][100]; 
	static int max = 0,n;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		n=sc.nextInt();
		for(int i = 0;i < n ; i++) {
			for (int j = 0; j <= i; j++) {
				arr[i][j]=sc.nextInt();
			}
		}
		dfs(0,0,0,0,0);
		System.out.println(max);
		sc.close();
	}
	
	public static void dfs(int x,int y,int left,int right,int sum) {
		if(x==(n-1)) {
			sum+=arr[x][y];
			if(sum>max&&Math.abs(left-right)<=1) {
				max=sum;
			}
			return;
		}	
		dfs(x+1, y,left+1,right,sum+arr[x][y]);
		dfs(x+1, y+1,left,right+1,sum+arr[x][y]);	
		return;
	}

}