1.问题描述及状态定义

数字三角形问题：有一个非负整数组成的三角形，第一行只有一个数，除了最下行之外每个数字的坐下方和右下方各有一个数。如下图所示：

从第一行开的数开始走，每次可以往下或右走一格，直到走到最下行，把沿途经过的数全部加起来。如何走才能使得这个和最大?

2.尝试找到最优解

我们可以先尝试找找看，能不能找到最优解，也就是找到最大的那个和是多少。

第一条路：1，3，4，4 和是12

第二条路：1，3，10，3 和是17

第三条路：1，2，1，10 和是14

.......

在这里我们基本找到了最大的和。回过头来想一个问题, 是不是贪心?。

很显然，不是贪心，我们在这个过程中，无法按照某一个特定的策略找到最大值。比如下面这张图：

如果，我们按照贪心策略，在每一层都选最大的，那面我的选择一定是1，3，10，3。而不是1，2，9，10。所以，动态规划问题不是贪心问题，区别在于这是一个动态的决策过程。

3.分析

    如果熟悉回溯法，可以看出这是一个动态的过程——每次有两种选择——左下或右上。如果用回溯法求出所有可能的录像，就可以从中选出最优路线。但是回溯法的效率太低：一个n层数字三角形的完整线路有2n-1条，当n很大时回溯法不再适用。

    为了得到更高效的算法，需要用抽象的方法思考问题：把当前的位置（i，j）看出一个状态，然后定义状态（i，j）的函数d(i，j)。其含义为从格子（i，j）出发时能得到的最大和(包括格子（i，j）本身的值)。可以用下面带编号的图辅助理解。

    根据上面画的辅助图，我们看看不同状态之间是如何转移的。

    从格子（i，j）出发有量两种决策。如果往左走则是（i+1,j），后需要求 从“（i+1，j）出发后得到的最大和“这一问题，即d(i+1，j)。

    如果是忘右走，需要求解 从 d(i+1，j+1)。

    由于可以在这两个决策中自由选择，所以应该选择d(i+1，j)和d(i+1，j+1)中较大的一个。换句话说，我们得到了所谓的状态转移方程：

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

    如果往左走，那么最好情况等于（i，j）格子里的值a(i，j)与”从（i+1,j）出发的最大总和“之和，此时需要注意这里的”最大“二字。如果连”从（i+1,j）出发走到底部“这部分的和都不是最大的，加上a(i，j)之后肯定也不是最大。这个性质称为”最优子结构“，也可以描述为”全局最优解包含局部最优解“。

    状态和状态转移方程一起完整地描述了具体的算法。

3.关于动态规划中“自底向上”的理解

在动态规划中，解题步骤中一般要求“自底向上”求解。什么是“自底向上”求解。还是拿上面的图举例。

在上面的分析中，我们从最顶点开始考虑，然后递归到底部求解得出结论。自底向上求解就是从最底部开始，两者当中取较大者往上加。比如，最后一层到倒数第二层的结果是：

在最后一层中，4和3比较，4比较大，所以选4，到了上一层加上原来的4就变成8。同理，3和2比较，3比较大，到了上面一层加上原来的10变成13。2和10比较10比较大，加上原来的9变成19。

然后继续往上走。

然后8和13比较，13比较大，到上一层变成16，13和19比较19比较大。到上一层变成21。最大值22。最大值路径还是跟原来一样。

(adsbygoogle = window.adsbygoogle || []).push({});