数字三角形问题

给定一个数字等腰的数字三角形，第一行只有一个数字，每增加一行数字的个数就加一。然后现在要求从三角形顶部到底边所经过的路径的数字之和的最大值。

我们先定义一个二维数组来存放数字三角形，这个三角形的存放是直角三角形的形状。

这个问题使用递归的方式来求解，相当的简单。

1
2
3
4
5
6
7
8
9
10
int D[MAX][MAX];

// i j 代表从数组的第i行第j个开始求和  n代表三角形的最大行数
int MaxSum(int i, int j, int n){
    if(i == n)
        return D[i][j];
    int x = MaxSum(i + 1, j, n);
    int y = MaxSum(i + 1, j + 1, n);
    return max(x, y) + D[i][j];
}

缺点：这个程序的时间复杂度太大了！！！！当三角形高度过大的时候，会超时的！！ O(2^n) !!

改进方法，每算出一个maxsum就保存起来，下次直接取值。不需要再访问。$O（n^2)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 记忆递归形程序
int D[MAX][MAX];
int maxsum[MAX][MAX];  // 初始化为 -1
int n;

int MaxSum(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 = MaxSum(i + 1, j);
        int y = MaxSum(i + 1, j + 1);
        maxsum[i][j] = x + y + D[i][j];
    }
    return maxsum[i]][j];
}

写成递推的方式.同样是$O(n^2)$ 

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
#include <iostream>
#include <algorithm>
using namespace std;

#define MAX 101
int D[MAX][MAX];
int n;
int maxsum[MAX][MAX];  // 初始化为 -1

int main(){
   int i, j = 0;
    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(i = n - 1; i >= 1; i--){
        for(j = 1; j <= i; j++){
            maxsum[i][j] = max(maxsum[i + 1][j] + maxsum[i + 1][j + 1]) + D[i][j];
        }
    }
    cout << maxsum[1][1] << endl;
}

对上述方式进行空间优化就是利用一维数组maxsum来存放每一层递推求解的结果。因为在当前递推层结束之后，上一层递推的结果是多余的，不会再用到了，我们可以直接覆盖之。

1
2
3
4
5
6
7
8
9
10
11
// 核心代码是
int maxsum[MAX]； 

for(int i = 1; i <= n; ++i){
	max[i] = D[n][i];
}
for(int i = n - 1; i >= 0; i--){
    for(int j = 1; j <= n, j++){
		maxsum[j] = max(maxsum[j], maxsum[j+1]) + D[i][j];
    }
}

更精简的做法是，使用D数组的最后一行当作一维的maxsum数组。。。空间更加节省了。

1
D[n][j] = max(D[n][j], D[n][j+1]) + D[i][j];

动态规划的思路就是找到一个问题的子问题，对子问题逐步细化到最简单的状态，然后子问题逐层递推（递归）解决，最终保证问题的解决。

我们需要找到子问题的状态转移过程，理解完过程之后就比较好写代码了。

建议从最简单的递归程序实现，然后递推实现优化时间复杂度，再来就考虑空间优化。