杭电oj1176，2084java实现

2084题目链接
1176题目链接
数塔问题，刚开始知道是动态规划确发现怎么想都想不出来，参考学习了其他人写的才知道这是一个数塔问题，建议写这题之前把2084做了。
2084显然是dp,但是数塔和普通的不同就是数塔从后往前递减。附上代码如下：

import java.util.Scanner;
/*
 * 数塔
 */
public class 杭电2084 {
	public static void main(String[] args) { Scanner sc=new Scanner(System.in);
	 int t=sc.nextInt();
	 while(t-->0)
	 { int n=sc.nextInt();//高度 int a[][]=new int[n 2][n 2];//赋值 int dp[][]=new int[n 3][n 3]; for(int i=1;i=1;i--) { for(int j=1;jj?i:j;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

1176：核心状态方程为：dp[i][j]=max(dp[i 1][j-1],dp[i 1][j],dp[i 1][j 1]) a[i][j];
解释：第i秒的位置j最大是由第i 1秒的j-1,j,j 1三个位置的最大dp决定的。申请数组是多申请两位这样就不雅J越界报错了；
附上代码

import java.util.Scanner;
/*
 * 数塔问题。倒过来看
 */
public class 杭电1176 {
	public static void main(String[] args) { Scanner sc=new Scanner(System.in);
	 while(sc.hasNext())
	 { int n=sc.nextInt(); if(n==0)break; int max=0; int a[][]=new int[100003][13]; long dp[][]=new long[100003][13]; for(int i=0;imax) {max=t1;} a[t1][x1 1] ; } for(int i=max;i>=0;i--) { for(int j=1;j<12;j ) { dp[i][j]=max(dp[i 1][j-1],dp[i 1][j],dp[i 1][j 1]) a[i][j]; } } System.out.println(dp[0][6]);
	 }
	}
	private static long max(long i, long j, long k) {
		if(ik?i:k;
	}
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
 

文章来源: bigsai.blog.csdn.net，作者：Big sai，版权归原作者所有，如需转载，请联系作者。

原文链接：bigsai.blog.csdn.net/article/details/79631046