题解 | 三角形取数(Hard Version)

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		long INF=-1000000000000000000L;
		Scanner scanner=new Scanner(System.in);
		int n=scanner.nextInt();
		int k=scanner.nextInt();
		long value[][]=new long[n][];//创建一个能装n个一维数组的二维数组，一维数组后面再定义
		for (int i = 0; i < value.length; i++) {
			long a[]=new long[2*i+1];
			for (int j = 0; j < a.length; j++) {
				a[j]=scanner.nextLong();
			}
			value[i]=a;//实现将一维数组装入二维数组
		}
		long dp[][]=new long[n][];//创建dp数组，dp[i][j]表示从第i行第j列出发，到达最后一行的最大数值之和
		for (int i = 0; i < n; i++) {
			dp[i]=new long[2*i+1];//将一维dp数组装入
		}
		//进行初始化dp
		long a[]=new long[2*n-1];
		long center=n-1;//最后一行中心位置
		for (int j = 0; j < 2*n-1; j++) {
			if(Math.abs(j-center)<=k) {
				a[j]=value[n-1][j];
			}else {
				a[j]=INF;
			}
		}
		dp[n-1]=a;
		long max=value[n-1][0];
		//接下来从下往上进行处理
		for (int i = n-2; i >= 0; i--) {
			for (int j = 0; j < 2*i+1; j++) {
				max=Math.max(dp[i+1][j], Math.max(dp[i+1][j+1], dp[i+1][j+2]));
				if(max>INF) {
					dp[i][j]=max+value[i][j];
				}else {
					dp[i][j]=INF;
				}
			}
		}
		System.out.println(dp[0][0]);
		
		
		

	}

}

这题确实有难度，首先要把三角形装入二维数组中，原来还可以这样创建二维数组，先定义装了多少个一维数组，后面再把一维数组装进去。创建dp[][],dp[i][j]表示从第i行第j列出发，走到最后一行所能积累的最大值，初始化dp就是把最后一行的情况输入进去，然后自下而上地求解，在这里还定义了INF，表示一个非常小的数，如果后面发现max等于INF，那说明从该dp[i][j]出发没有合法的路线抵达最后一行。那么就继续把dp[i][j]赋值为INF。max是Math.max(dp[i+1][j], Math.max(dp[i+1][j+1], dp[i+1][j+2]))，原本三角形的(i+1,j -1) (i+1,j) (i+1,j+1)在二维数组中其实就是上面三个