|
|
- package com.hisen.dynamicprogramming;
- import java.util.Scanner;
- import javax.swing.plaf.basic.BasicInternalFrameTitlePane.MaximizeAction;
- /**
- * 数学三角形
- *
- * @author WUYIJIE646
- *
- * 5 表示三角形的行数 接下来输入三角形
- *
- * 7
- *
- * 3 8
- *
- * 8 1 0
- *
- * 2 7 4 4
- *
- * 4 5 2 6 5
- *
- * url:http://lib.csdn.net/article/datastructure/9390
- *
- * if ( r == N) MaxSum(r,j) = D(r,j) else MaxSum( r, j) =
- * Max{MaxSum(r＋1,j), MaxSum(r+1,j+1) } + D(r,j)
- *
- */
- public class POJ1163 {
- static int D[][] = new int[101][101];
- static int maxSum[][] = new int[101][101];
- static int n;
- /**
- * 第一版 效率比较低，存在重复计算
- * @param i
- * @param j
- * @return
- */
- static int maxSumOne(int i, int j) {
- if(i==n)
- return D[i][j];
- int x = maxSumOne(i+1, j);
- int y = maxSumOne(i+1, j+1);
- return Math.max(x,y)+D[i][j];
- }
- /**
- * 改进版 记录每次的计算
- * @param i
- * @param j
- * @return
- */
- static int maxSumSecond(int i, int j) {
- if( maxSum[i][j] != -1 )
- return maxSum[i][j];
- if(i==n)
- maxSum[i][j] = D[i][j];
- else{
- int x = maxSumSecond(i+1, j);
- int y = maxSumSecond(i+1, j+1);
- maxSum[i][j] = Math.max(x,y)+D[i][j];
- }
- return maxSum[i][j];
- }
-
- /**
- * 递推关系
- * @param n
- * @return
- */
- static int maxSumThird(int n){
- int i,j;
- for (i = 1; i <= n; ++i) {
- maxSum[n][i] = D[n][i];
- }
- for (i = n-1; i >= 1; ++i) {
- for( j = 1; j <= i; ++j )
- maxSum[i][j] = Math.max(maxSum[i+1][j],maxSum[i+1][j+1]) + D[i][j];
- }
- return maxSumSecond(1,1);
-
- }
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- System.out.println("请输入三角形高度：");
- n = Integer.valueOf(sc.nextLine());
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= i; j++) {
- System.out.println("请输入节点数字：");
- D[i][j] = Integer.valueOf(sc.nextLine());
- maxSum[i][j] = -1;//maxSumSecond 独有
- }
- }
- System.out.println("最大路径 maxSumOne："+maxSumOne(1,1));
- System.out.println("最大路径 maxSumSecond："+maxSumSecond(1,1));
- }
- }
|
|
楼主: 阿星
楼主
发表于 2017-10-19 00:13:11
发表于 2017-11-27 00:20:18
