三角数塔问题

1、三角数塔问题
设有一个三角形的数塔，顶点为根结点，每个结点有一个整数值。从顶点出发，可以向左走或向右走，如图所示： 


要求从根结点开始，请找出一条路径，使路径之和最大，只要输出路径的和。

package com.iflytek.dp;


public class TriangularTower{
private int[][] matrix;
private int high, width;
public int[][] dp;

public TriangularTower(int[][] matrix){
this.matrix = matrix;
this.high = matrix.length;
this.width = matrix[0].length;

this.dp = new int[this.high][];
for(int i = 0; i < this.high; i++){
this.dp[i] = new int[this.width];
}
}

public void fun() {
for (int i = 0; i < high; i++) {
for (int j = 0; j < i + 1; j++) {
if (i == 0 && j == 0) {
dp[i][j] = this.matrix[i][j];
} else {
if (i >= 1 && j > 0 && j < i)
dp[i][j] = Math.max(dp[i - 1][j - 1], dp[i - 1][j]) + this.matrix[i][j];
else {
if (j == 0) {
dp[i][j] = dp[i - 1][j] + this.matrix[i][j];
} else {
dp[i][j] = dp[i - 1][j - 1] + this.matrix[i][j];
}
}
}
}
}
}


public static void main(String[] args) {
int[][] matrix = {
{13, 0, 0, 0, 0},
{11, 8, 0, 0, 0},
{12, 7,26, 0, 0},
{6 ,14,15, 8, 0},
{12, 7,13,24,11}};

TriangularTower tt = new TriangularTower(matrix);
tt.fun();
System.out.println(tt.dp);
}


}

来自 “ ITPUB博客 ” ，链接：http://blog.itpub.net/29653519/viewspace-1713923/，如需转载，请注明出处，否则将追究法律责任。