1. 问题描述
    有如下所示的数塔，要求从顶层走到底层，若每一步只能走到相邻的结点，则经过的结点的数字之和最大是多少？
    

2. 问题分析
    该题为典型的动态规划的题目，我们将其看成从底向上走，并动态修改上层的数值。父节点选择较大的孩子节点作为路径大的值，选了之后并将其加到自身得到的和修改本身的值。用式子表示为：
    a[i][j] = max(a[i+1][j], a[i+1][j+1]) + a[i][j];其中i表示层数，j表示在某一层中的位置
3. 代码实现

#include <iostream>
#include <vector>

using namespace std;

void getMax(vector<int> a[], int h, int &max){
   for(int i = h-2; i >= 0; i--){
       for(int j = 0; j < (i+1); j++){
           if(a[i+1][j] > a[i+1][j+1])
               a[i][j] += a[i+1][j];
           else
               a[i][j] += a[i+1][j+1];
       }
   }
   max = a[0][0];
}
int main(int argc, char *argv[])
{
    int towers;
    cin >> towers;
    for(int t = 0; t < towers; t++){
        int h ;
        cin >> h;

        vector<int> a[h];
        for(int i = 0; i < h; i++){
            vector<int> v;
            for(int j = 0; j < (i+1); j++){
                int num;
                cin >> num;
                v.push_back(num);
            }
            a[i] = v;
        }

        int max;
        getMax(a, h, max);

        cout << max << endl;
    }
    return 0;
}

4. 代码复杂度
    O(n),n为节点个数，或者O(h²),h为数塔的高度

1. 问题描述
    有一个顺序的棋盘，顺序摆满了一连串的棋子，每个棋子都有一个权重，如下图所示。我们的目的是从起始位置经过一系列棋子走到终点位置。走的过程中，要遵循的规则：下一个棋子的权重要大于前一个棋子的权重，棋子可以直接跳到其后面的一个或者是越过几个棋子直接访问后面的，均可。目标是：找出一个路线使得经过的棋子权重之和最大。

#include <iostream>
#include <vector>

using namespace std;

void getMax(int a[], int len, int &max){
    int matrix[len];

    for(int i = 0; i < len; i++){
        int currentMax = a[i];

        for(int j = 0; j < i; j++){
            if((a[i] > a[j]) && (currentMax < (a[i] + matrix[j]))){
                currentMax = a[i] + matrix[j];
            }
        }
        matrix[i] = currentMax;
    }
    max = 0;
    for(int i = 0; i < len; i++){
        if(matrix[i] > max)
            max = matrix[i];
    }
}
int main(int argc, char *argv[])
{
    int c;
    vector<int> maxList;
    while((cin >> c) && c!=0){
        int a[c];
        for(int i = 0; i < c; i++){
            cin >> a[i];
        }
        int max;
        getMax(a, c, max);
        maxList.push_back(max);
    }
    for(int i = 0; i < maxList.size(); i++){
        cout << maxList[i] << endl;
    }
    return 0;
}

4. 复杂度分析
    O(n²)

问题描述：

    一个n×n的二维矩阵，矩阵中的元素的大小范围为：-127~127之间，求该二维矩阵中最大的子矩阵的元素和。

问题分析：

    看到这个问题，我们会想到动态规划里面的一个最基本的问题，即：求一个数组的最大子段和。我们可以对二维矩阵中每两行之间的所有和进行加权，将其变为一个数组中求最大的子段和，通过这样，我们就可以找出最大的子矩阵之和。

1.   一维数组的最大子段和：

    对于一个数组a[n]，我们求数组中最大的子段和。

    该问题我们可以用动态规划去解决，我们用b[k]来保存前k个数中，以a[k]结尾的最大的子段和，计算出所有的b[k]我们就可以找到最大的值即为我们所求的最大值。

对于b[k]，b[k] = max{b[k-1] + a[k], a[k]}，
    max{b[k]} 即为我们找的最大值。

2.   求最大的子矩阵元素之和

    我们可以把第k行矩阵的元素表示为前k行矩阵元素之和，即：

    我们用两个变量i和j来遍历矩阵的行，并且将j行的元素减去i行的元素即为两行之间的元素和，这样我们就把问题转换成对于列而言的一维向量去计算其最大的子段和的简单问题了。

    计算出每两行之间的最大的元素和，然后比较他们的大小，我们选择最大的即为我们最终要求的最大的子矩阵的和。

3.    代码实现：

// Author: zhangxiaolin@software.ict.ac.cn
#include <stdio.h>
int main(int argc, char* argv[]){
  int n;
  scanf("%d", &n);
  int a[100][100];
  for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
      int temp;
      scanf("%d", &temp);
      if(i == 0)
        a[i][j] = temp;
      else
        a[i][j] = a[i-1][j] + temp;
    }
  }
  int result = 0;
  for(int i = 0; i < n; i++){
    for(int j = i; j < n; j++){
      int sum = 0;
      int temp = 0;
      for(int k = 0; k < n; k++){
        int add;
        if( j ==i)
          add = a[j][k];
        else
          add = a[j][k] - a[i][k];
          temp += add;
	  temp = (temp>=0?temp:0);
	  if(temp > sum){
	    sum = temp;
        }
      }
      if(sum > result)
        result = sum;
    }
  }
  printf("%d\n", result);
  return 0;
}

4. 结果分析
    复杂度为：O(n³)