动态规划-数字三角形

数字三角形

问题

• 求自顶向下的最大路径之和，只能往左下和右下走，三角形行数最大为100。
  

输入格式

• 怎么用数组存储三角形的数据，使用二维数组A
  5 // A[0][0]三角形的行数
  7
  3 8
  8 1 0
  2 7 4 4
  4 5 2 6 5

解题思路

• D(i,j)：第i行第j列(i，j从1开始算起)。这是一个二维数组用来存储三角形数据。
• MaxSum(i,j)：从D(i,j)到底边的各条路径中最大的路径和，可能不唯一。
• D(i,j)出发，下一步只能走D(i+1,j) or D(i+1,j+1)
• 所以只需以下步骤

if(r == N)
	MaxSum(i,j) = D(i,j)
else
	MaxSum(i,j) = Max{ MaxSum(i+1,j), MaxSum(i+1,j+1) } + D(i,j)
	// D(i,j)是一个具体的数，从他下面求最大路径+自己的值=他到底边最大路径

递归的伪代码表示

• 此法不可行，时间复杂度为2^n，发生了子问题的重复求解。

int D[MAX][MAX];	//MAX:三角形行的最大值，预先定义
int n;	//三角形的行数，用户输入
int MaxSum(int i, int j){
	if (i==n) return D[i][j]	//如果就是在底边上，那么最大值就是自己
	int x = MaxSum(i+1, j);
	int y = MaxSum(i+1, j+1);
	return max(x,y)+D[i][j]
}

int main(){
	int i,j;	
	cin >> n;	//输入三角形行数
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)	//三角形列数=行数，第一行1个，第二行2个，第n行n个
			cin >> D[i][j]	//给数字三角形赋值
	cout << MaxSum(1,1)	//即求自顶向下的最大路径
}

• 如图，1的次数=3的时候计算1次，8的时候计算1次
• 7的次数=8的时候计算1次，1的时候计算2次

备忘录法(自顶向下：需要递归)

• 只要把每次计算的值存储起来MaxSum(i , j)就不用重复计算了，计算之前先判断此值有没有被计算过即可。
• 由于只要计算n行个数，1+2+3+…+n = n(n+1)/2，所以时间复杂度是O(n^2)。

#define MAX 101;	//MAX:三角形行的最大值，预先定义
int D[MAX][MAX];	
int maxSum[MAX][MAX];	//用来保存计算过的数
int n;	//三角形的行数，用户输入
int MaxSum(int i, int j){
	if (maxSum[i][j] != -1)	
        //判断是否计算过，例如判断第3行是否被计算过，如果是，直接返回第3行的最大值
        //如果没有，就计算第二行的最大值+第3行的数。再判断第2行有没有计算过
        //假如有，则返回该行最大值参与(本块17行)的计算。以此类推
		return maxSum[i][j]
	
	if (i==n) 
		maxSum[i][j] = D[i][j]	//如果就是在底边上，那么最大值就是自己
	else
        int x = MaxSum(i+1, j);
        int y = MaxSum(i+1, j+1);
        maxSum[i][j] = max(x,y)+D[i][j]	
        //每次计算过后把该数到底部最大路径存起来
        //下次计算之前就判断有没有计算过，从而避免重复计算
  	return maxSum[i][j]	//返回最大路径
}

int main(){
	int i,j;	
	cin >> n;	//输入三角形行数
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)	//三角形列数=行数，第一行1个，第二行2个，第n行n个
			cin >> D[i][j]	//给数字三角形赋值
			maxSum[i][j] = -1	
			//赋初值-1，因为从D(i,j)到底边的最大路径为正数，-1表示没有被计算过
	cout << MaxSum(1,1)	//即求自顶向下的最大路径
}

递推法(自底向上：不用递归)

• 以此法填完表格，如下图。所以可以使用2层循环语句替换递归表达式。

int maxSum[MAX][MAX]
int main(){
	int i,j
	cin >> n
	
	// 给数字三角形赋值
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			cin >> D[i][j]

	for(int i = 1; i <= n; ++i)
		maxSum[n][i] = D[n][i]
		// 一开始给最后一行赋值，就是本身的值
		
	for(int i = n-1; i >= 1; --i)	//从倒数第2行开始往上
		for(int j = 1; j<=i; ++j)	//第几行就有几个数
			maxSum[i][j]=max(maxSum[i+1][j], maxSum[i+1][j+1]) + D[i][j]
			//此时的i是倒数第2行的数，所以倒数第2行+下面一行最大值=该数最大值
	cout << maxSum[1][1]
}

递推法的空间优化