数字三角形

数字三角形

问题描述和状态定义 —— 非负数字组成的三角形，从第一个数开始每次可以向右或者向下走一格，直到最下行，求沿途经过数和的最大值。这是一个动态决策的问题，每次都面临两种选择，如果用回溯法找所有路线，则n层三角形有2的n次方条的路线，效率很低。

所以引入状态转移的概念：

把当前位置 ( i, j)看成一个状态，定义函数 d( i, j)为从( i, j)出发后能得到的最大的和，那么可以写出一个递推方程：

d( i, j) = a( i, j) + max{ d( i, j + 1), d( i + 1, j + 1)};

d( i, j + 1)为从( i, j + 1)出发的最大和，即一个最优子结构，也可以描述成“全局最优解包含局部最优解”。上式是一个状态转移方程，状态和状态转移方程是动态规划的核心

记忆化搜索与递推
方法一：递归计算

int solve(int i , int j){
     return a[i][j] + ( i == n ? 0 : max( solve(i+1,j), solve(i+1, j+1) )   );
}  //注意处理边界

这样做正确，但重复计算

数字三角形

方法二： 递推计算

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

一层一层从下至上递推，复杂度为O(N^2)

方法三：记忆化搜索

int solve(int i, int j){
    if(d[i][j] >= 0) return d[i][j];
    return d[i][j] = a[i][j] + (i == n?0:max(solve(i+1,j), solve(i+1, j+1)));
}//别忘了队d[i][j]赋值

已经搜过则判断后不再计算，直接用该值，由于i,j都在,1~n之间，所有不相同的结点一共只有O（n^{2）个，不论以怎样的顺序访问，时间复杂度均为O（n}2）

数字三角形