数字三角形--动态规划

问题的提出：

• 在数字三角形中寻找一条从顶部到底边的路径，
• 使得路径上所经过的数字之和最大。
  如：
  {2},
  {6,9},
  {9,5,6},
  {9,8,1,9},
  {4,5,2,6,5}
  最大和为 2+9+9+9+6=35 （分治法）

常规的思路是应用分治法 找出每一层最大的项 统一相加得到最大路径
此处使用动态规划的方法。

算法思想：

• 1.将原问题分解为子问题：原问题为求解顶层到底层路径最大数字和，分解为每一层到底层路径最大数字和，5个问题
• 2.确定状态：使用 mstb (max_sum_to_bottom) 数组保存每一层次到底边的最大和
• 3.确定初始态值：此处初始态为底边到底边最大值 即mstb[4]
• 4.确定状态转移方程：mstb[i] = mstb[i + 1] + getMaxNumber(numbers[i]);

C++代码

class MaxSum
{
    //数字三角形
    //此处使用初始化的数组 避免手动初始化的麻烦
    //此处仅做演示，如果用作其他用途可改写
    int numbers[5][5] = { 
        {2}, 
        {6,9}, 
        {9,5,6}, 
        {9,8,1,9}, 
        {4,5,2,6,5} 
    };
    int mstb[5];	//max_sum_to_bottom，某一层到达底边最大的和，mstb[0]表示第一层到达底边最大和
	public:
    //找出数组最大元素
    int getMaxNumber(int* const &numbers) {
        int max = 0;
        int length = sizeof(numbers);
        for (int i = 0; i < length;i++) {
            if (max < numbers[i]) {
                max = numbers[i];
            }
        }
        return max;
    }
    //输出三角形
    void print() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 5; j++) {
                if (numbers[i][j] > 0) {
                    cout << numbers[i][j] << ends;		//undo: 没有对0以及负数做考虑
                }
            }
            cout << endl;
        }
    }
    //获取从顶至底最大和
    int getMaxSum() {
        mstb[4] = getMaxNumber(numbers[5]);
        for (int i = 3; i >= 0; i--) {
            mstb[i] = mstb[i + 1] + getMaxNumber(numbers[i]);
        }
        return mstb[0];
    }
};

测试代码

class Problem1Tester{
public:
    MaxSum max_sum;

    void getMaxNumber_Test() {
        max_sum.print();
        int numbers[5] = {8,5,9,5,1};
        cout << max_sum.getMaxNumber(numbers) << endl;
    }
    void getMaxSum_Test() {
        max_sum.print();
        cout << max_sum.getMaxSum() << endl;
    }
}tester1;

参考：
http://blog.****.net/baidu_28312631/article/details/47418773