动态规划算法：数字三角形（附三种解题方式）

题目

• 数字三角形：即由数字组成三边的三角形。
  例如：
  7
  38
  810
  2744
  45265
• 问题：如何求解某点到底边所能获得的最大值路径。

解题

由于直接使用递归求解的话，时间复杂度过大O(2^n)，会超时而无法计算，因此我们一般不采用递归。

解法1

采用多一个二维数组，存储当前数值到结尾所能走的最大值，避免 同一个结果重复计算n次。

//数字三角形（递归思想+记忆数组避免运算重复）
//传入的ij是三角形的起始点
public static void digTalTriangleByRecursion(int i,int j,int tri[][]){
	int a = tri.length;
	int b=tri[0].length;
	int maxSum[][]=new int[a][b];
	for (int m=0;m<a;m++){
		for (int n=0;n<b;n++) {
			maxSum[m][n] = -1;
		}
	}
	System.out.println("最大值是:"+maxNum(i,j,tri,maxSum));
}
private static int maxNum(int i,int j,int tri[][],int maxSum[][]){
	if(maxSum[i][j]!=-1){	//已经计算过最大值
		return maxSum[i][j];
	}
	if(i==tri.length-1){
		maxSum[i][j]=tri[i][j];
	}else{
		int x=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20