算法学习（动态规划）- 数塔问题

前言

之前碰到了扔鸡蛋问题（给你2个鸡蛋，在100层楼上扔，要求想出一个好的策略，去测出哪一层楼开始鸡蛋就会碎掉），一直摸不着头脑。后来才知道可以使用“动态规划”这种思想（或者叫算法范式）去解决这个问题。

但是看了一些鸡蛋问题和动态规划的文章，依然只是流于形式，并不能理解其中的精髓。想想或许是鸡蛋问题对我现在而言难了一些，所以只好找了一些其它的动态规划问题，从简单入手，先去理解“动态规划”的思想精髓，再反过来去思考“鸡蛋问题”。

其中一个经典问题是01背包问题，这是我之前一直想搞懂的一个问题。看了一篇文章，就大致上理解了这个问题的解决办法和思路。所以我就不班门弄斧了，直接推荐这篇文章：动态规划之01背包问题（最易理解的讲解）。

比起一开始就搬概念和公式，这篇文章用了一个“填表格”的方式去让读者理解背包问题的解决过程，这对初学者更友好。推荐大家也试着去画出那个表格，然后自己填一填，不需要编程，只需要一张纸和笔和你的脑子，就能按照文中的思路把表格填完，然后就解决了背包问题。算法编程实际只是对你脑子的这种思维过程的一个模拟。

我想，之所以这种所谓“思想”、“范式”之类的东西难以理解，也许是因为它经过了双重的“抽象”吧。比如，以下是动态规划思想的描述：

动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式…

有时候，真的想吐槽这些东西就是“正确的废话”。你不能说这些描述有什么错，但是真遇到问题的时候，光看这些描述你又完全没办法想出解决问题的方法。

解决某个具体问题，我们会把问题进行抽象，例如把搜索问题抽象成树问题。而这些所谓的“思想”，为了归纳这一类问题的共性，又成了对这类问题的抽象。即，成了“抽象之抽象”，双重抽象。

普适的代价即抽象

不知道别人如何，反正我对于“抽象”这类反人类大脑结构的东西实在无法理解。只能重新“化抽象为形象”，才能去“识”得它。就算是概念、思想这类看不见摸不着的东西，还是得转换成我脑海一个具象化的东西才行。

理解了01背包问题之后，我开始找到第2个动态规划的问题，即数塔问题。企图通过解决这些问题，一窥“动态规划”的冰山一角。

下面进入正题。

问题

如图，有一个数塔，从顶部出发，在每一个节点可以选择向左或者向右走，一直走到底层。要求找出一条路径，使得所走路径上的节点数字之和最大。

（图片来自百度）

分析

1.穷举

1）思路来源

这是在没有去看正确的动态规划方法之前，我自己想出的思路。

虽然不是“动态规划”，但是这个走歪的方向，也许更能让我们理解究竟怎样才算是“动态规划”。所以这个思路也是有价值的，可以说一说。

我一开始的理解，“动态规划”就是“使用已经计算好的信息，避免重复的计算”。这个想法的来源来自于这篇文章：

如何理解动态规划？

文章用了一张图来解释什么是动态规划：

我用当时的个人理解来复述一下：要计算A -> Q -> Z这条线路的最优选择，实际上并不需要我们把 A -> H -> Q -> Z、 A -> I -> Q -> Z 这两条路径都计算出来。 我们在计算A -> Q 的时候， 实际上已经把A -> H ->Q 、A -> I -> Q 这部分计算过了，因此已经得出了A -> Q的最优线路。计算A -> Q -> Z的时候，只需要利用这个结果即可。A -> Q是A -> Q -> Z的一个部分（注意：这个说法不完全正确，所以才会导致我得出了一个不完美的思路），因此能够“使用已经计算好的信息，避免重复的计算”。

当时我的理解不能说十分准确，认为动态规划就是：一个子问题如果属于一个大问题的一部分，就可以利用子问题的结果信息去计算大问题，避免重复计算。这个说法不准确，我后面会纠正这种想法。

但此时我们就顺着这种错误想法，看看这种想法会产生怎样的解题思路。

2）思维过程

毫无疑问，我们可以把问题图中的数塔看成一个大数塔，它其实可以看作包含了很多小数塔。比如只有两层的 9、12、15：

或者三层的9、12、15、10、6、8：

总之一个大数塔是可以拆分成小数塔的。那么，为了找到一个大数塔哪条路最优，是不是可以对小数塔找到最优？然后每一层每一层我们都最优，最后就能得到大数塔的最优了呢？

咋听起来很诱人，似乎找到了很厉害很巧妙的办法。但可惜，在这里行不通。这实际上就是“贪心算法”（em…又一种算法思想范式…）的本质：只要每一步我们都找最优，找到最后我们就能找到最后的最优。

还是引用推荐文章的一张图：

去计算A -> Z的最优线路，我们先一步一步来。先算A到“H or I”的最优线路，然后往下算“H or I”到“P or Q”的最优线路，最后算“P or Q”到Z的最优线路。算到最后，我们就得到了A到Z的最优线路。

这种情况下，我们才能用“贪心法”。看上去似乎跟“动态规划”的图不太一样，我把这张图改改，把“H or I”、“P or Q”这两个节点展开：

可以看到，任意一层的任意节点，都与下一层的所有节点有连接。第一层的A，与第二层的H、I都是连接的。第二层的H、I，与三层的P、Q都是连接的。第三层的P、Q，与第四层的Z都是连接的。

大概只有问题的推理形式具有这样的图特性，我们才能使用“贪心”法去解决吧。

我来再来看看我们的数塔，如果我把数塔横着倒放，变成这样：

看起来是不是跟“贪心法”的结构图不一样？是不是更像“动态规划”的那张结构图：

这也就说明了，为什么数塔问题可以用“动态规划”去解决。

3）解决办法（当然，最后想歪了，得出了穷举法。。。）

既然没办法通过一步步计算最优，来得出最后的最优，那我就妥协一些。每一次计算某一级子树塔的时候，我就用低一层级的子数塔的全部路线，然后再跟这一层的全部节点作一个连接，得出新的路线。

这样一步步不断计算出路线、以及这些路线的节点数值之和，最后把所有路线全部计算出来，作一个排序，就能知道哪条路线节点数值之和最大，不是就能得出问题答案了么？

想出这个办法的时候，我并不能确定这到底是不是“动态规划”，毕竟这时候对“动态规划”的理解还太浅了。但是又感觉这似乎不是“穷举”，因为我并没有把从根节点到末尾节点的路线全部列举一遍（至少从程序上我不会），我是“一步一步”计算的路线，并且我也把大数塔拆成来小数塔解决，相当于“把大问题拆分成相似的子问题”。从这些特征来看，这似乎也不算是“太笨的方法”，怎么会是“穷举”呢？(￣▽￣)\"

再根据这个思路写写程序，发现我居然可以用递归！？这么一来似乎就更自信了。因为之前曾经看过，“递归”是“动态规划”过程中使用的一种手段（当然，这句话也不准确。。。后面也会纠正它），这些特征表面，我使用的方法就算是“动态规划”了吧？

怀着将信将疑的态度，试着去查找了别人的文章，发现想了那么多层，最后自己还是没绕出“穷举”这个坑。/(ㄒoㄒ)/~~

4）分析纠正

前面说了几点“动态规划”特征的个人理解，很遗憾的是，那几点理解都不是严格地准确。这里我们来分析、纠正一下它们：

<1> 一个子问题如果属于一个大问题的一部分，就可以利用子问题的结果信息去计算大问题，避免重复计算

其实这并算是“动态规划”独有的特征。算法优化的本质就是为了“避免重复计算”。那么问题来了：都是在“避免重复计算”，不同的方法又有什么不同？它们避免重复计算的部分不一样吗？

而且，不是只有动态规划问题才能拆成子问题，例如贪心类型问题，把一段长的路拆成一步步的小路，把整体最优拆成计算局部最优，不也是可以大问题拆成小问题么？

<2>“递归”是“动态规划”过程中使用的一种手段

同理，并不是只有动态规划才会用到递归。“递归”说来，实际上是属于编程层面的东西，“函数自己调用自己”，是一种代码文字的书写、组织、表达方式，一种手段。而动态规划是一种思想，是可以脱离编程、程序而存在的，你可以在自己脑海中去运行这种思想。

2.动态规划

1）理论分析

正经的动态规划方法我参考学习了这篇文章：几个经典的动态规划问题

事实上，动态规划方法最重要的，是找到一个当前状态与前一状态对应的关系。因为在动态规划结构的问题中，当前状态会依赖于上一个状态（或认为是，当前的“可选”与之前的“选择”有关）。

如果拿数塔来说的话，就是我这一层能够选择哪些岔路，跟我之前走过、选择的路是有关系的。比如下图，我走了第一层的“9”，然后走了第二层的“15”，到了第三层我就只能走“6”、“8”这两种选择了，而不可能走“10”这个节点。这就说明我第三层的可选项跟我第一、二层的选择是有关系的。

如果是贪心结构的问题，比如下图，那当前的选择，就跟我之前的选择没有什么关系。比如我走到第二层，将要考虑如何选择第三层的路，不管我现在是处于H还是I，我的可选项都是一样（都是P、Q），我可以走到第三层的任意节点，因为H、I与第三层所有节点都是通的。每一步都随你瞎走，反正最后给你的选项都是一样的，至于路线是不是最优，那就是另说了。

如果把这种“可选项”理解成一种状态的话，那么动态规划结构的问题，每一层都是有很多种状态的，且不同的状态取决于上一层是的哪种状态。而贪心结构的问题，每一层的状态都只有一种。

明白了动态规划问题存在着“状态”，并且状态与上个状态是存在着某种关系之后，我们去找出这种关系，将这种关系总结、归纳成“状态转换方程”，然后就是去编程实现了。动态规划问题的基本思路就是如此（当然这还是“正确的废话”，就算告诉你要去找状态转换方程，你也未必就能找出๑乛◡乛๑）

直接说吧，数塔问题的状态转换方程是这个：

dp(i, j） = Max( dp(i+1, j), dp(i+1, j+1 ) )+ f [ i ][ j ]

还需要把它翻译成人话：

为了便于说明，咱们先约定一下节点的表示方法吧：[ i, j ] ，它指的是第 i 层的第 j 个节点。比如下图[ 1, 1 ] 节点就是第1层、第1个节点，即“9”。

dp(i, j)函数的值，是[ i, j ] 这个节点，到最底层之后，所有可能路线的节点数值之和的最大值。还拿上图来说，比如dp(5, 1)其实就是[5, 1]这个节点（第5层、第1个）到最底层（第5层，也是它自己所在这一层）所有可能路线只有一条，即它自身“19”，所以dp[5, 1] = 19。

又比如dp(4, 2)，即[4, 2]这个节点，它到最底层（还是第5层）的所有路线有两条：7 -> 18、10 -> 18。数值和分别是25、28，28更大，所以最大值为28。因此dp(4, 2) = 28。

所有情况依次类推。

然后我们来解释一下这个状态转移方程式在说什么吧，dp(i, j） = Max( dp(i+1, j), dp(i+1, j+1 ) )+ f [ i ][ j ]，意思是dp(i , j)这个的值，等于dp(i+1, j)、dp(i+1, j+1 ) 两者之间取大的，然后再加上 f [ i ][ j ]这个。

f [ i ][ j ]的含义是节点[i, j]的数值，比如上图[1, 1]节点，值是9，所以f[1][1 ]= 9。

再翻译得更通俗，就是你想要知道[i, j]这个节点到最底层的最大数值和，首先要知道[i+1, j]和[i+1, j+1]这两节点到最底层的最大数值和。知道之后，我们取大的，然后加上[i, j]节点的值，即f[i][j]，就是我们要求的结果。

我们要求第1层、第1个节点到最底层的最大数值和，本质上就是要求dp(1, 1)。

2）实际操作

即使把公式翻译得通俗了，可能依然很绕口。我们就直接拿题目来说，一步步地来说明我们每一步怎么做。

想要知道根节点“9”到最底层的最大数值和，首先得知道第二层的“12”和“15”到最底层的最大数值和。我假设它们分别是M和N，假如“15”这条线路的数值和更大，即Max(M, N) = N，那么“9”到最底层的最大数值和，就是N + 9, 即下一层级的数值和 加上它自己。

然后我们反推一步，按照第一步的类似原理，我们要知道“12”和“15”到最底层的最大数值和，就得知道第三层的“10”、”6“、”8“到最底层的最大数值和。

其中，连接“12”这个节点的是“10”、“6”。我假设这两条支线的数值和最大分别是O、P，假如”10“这条线路的更大，即Max(O、P) = O，那么“12”这条线到最底层的最大数值和就是 O + 12。

其中，连接“15”这个节点的是“6”、“8”。我假设这两条支线的数值和最大分别是P、Q（注意到，P就是上段话里的那个P，因为节点都是“6”，所以这个值是一样的），假如”6“这条线路的更大，即Max(P，Q) = P，那么“15”这条线到最底层的最大数值和就是 P + 12。

然后我们继续，往下一层推理、不断推理…

最后推理到了最底层，就没法继续往下推了，已经到了一个结束点。此时节点到最底层的数值和最大值，就是它自身。比如“19”，它到最底层线路的数值和最大就是它自己——19了。

现在我们明白了，要想知道第一层的信息，就必须知道第二层。 要想知道第二层的信息，又必须知道第三层…依次类推，只有最底层的信息，我们不需要由别的层来推导，而是可以直接得出。因此，最底层就是一个计算的起始点。

若从实现来说，确实也需要用到递归。最底层既是计算的起始点，同时又是递归的终止点、回溯点。

实现

说了那么多，我们就用程序来实现、验证吧。

1）数塔生成器

先来实现一个数塔生成器吧：

function createNumberTower (level) {
    let tower = new Array();
    for (let i = 1; i < level + 1 ; i++) {
        let arr = new Array(i)
        for (let j = 0; j < arr.length; j++) {
            arr[j] = parseInt(Math.random() * 20)
        }
        tower.push(arr)
    }
    return tower;
}

实际上就是生成一个二维数组，只是第二维的长度变化是有规律的，依次是1、2、3、4…这样自增。例如题目图里的数塔用数组表示就是[[9], [12, 15], [10, 6, 8], [2, 18, 9, 5], [19, 7, 10, 4, 16]]

参数是level，即要生成的数塔的层数。

这里我把每个节点设置为0~20的随机数，要想生成别的数，可以自行修改。

arr[j] = parseInt(Math.random() * 20)

2) 穷举法

虽然这个方法的效率低，但是既然已经思考出来了，那还是把它也一块实现了吧。穷举法的结果一般比较准确，正好可以用来验证我们的动态规划法的结果是否正确。

function findPath(tower) {
    let level = tower.length - 1;
    let prevPaths = tower.length === 2 ? [{path: [0], value: tower[0][0]}] : findPath(tower.slice(0, level))
    let newPaths = new Array();
    for (let path of prevPaths) {
        let lastNode = path.path[path.path.length - 1];
        newPaths.push({ 
            path: Array.from([...path.path,lastNode]),
            value: path.value + tower[level][lastNode]
        })
        newPaths.push({ 
            path: Array.from([...path.path,lastNode + 1]),
            value: path.value + tower[level][lastNode + 1]
        })

    }
    return newPaths;
}

结果将是一个数组，数组的每个元素是一条路径。里面包含两个字段信息：path、value。

path也是一个数组，用来表示路径每一层的节点索引。那题目图的数塔举例子，例如某条路径的path值是[0, 1, 2, 3, 4]，那就说明第一层我走的是第1个元素（个数 = 索引 + 1嘛），第二层走的也是第2个元素，第三层走的是第3个元素，第四层走的是第4个元素，第五层走的是第5个元素。即9 -> 15 -> 8 -> 5 -> 16这一条路线。

value就是这一条路线所有节点的数值之和了。穷举了所用路线之后，按照value由大到小排序，就能知道哪一条路线数值之和最大了。

3）动态规划法

出乎意料，动态规划法的代码极其简单优雅，不过数行。

let fullTower = createNumberTower(30); // 生成数塔
function dp(i, j) {
    if (i === fullTower.length - 1) { // 起始点
        return fullTower[i][j];
    } else {
        return Math.max(dp(i+1, j), dp(i+1, j+1)) + fullTower[i][j];
    }
}

注意：为了编程方便，i，j 我用的是数组索引，即初始值是0。在这里dp(0 , 0)表示的才是对第1层第1个节点求解，而不是上文分析说明里的dp(1, 1)了。

4）验证

我们来验证一下，先把原题目求解一下。这里就不需要我们的数塔生成器了，直接把题目数塔写成一个二维数组

let fullTower = [[9], [12, 15], [10, 6, 8], [2, 18, 9, 5], [19, 7, 10, 4, 16]]

然后是穷举法：

findPath(fullTower).sort((prev, next) => next.value - prev.value)
输出：
 [{ path: [ 0, 0, 0, 1, 2 ], value: 59 },
  { path: [ 0, 1, 1, 1, 2 ], value: 58 },
  { path: [ 0, 0, 0, 1, 1 ], value: 56 },
  { path: [ 0, 0, 1, 1, 2 ], value: 55 },
  { path: [ 0, 1, 1, 1, 1 ], value: 55 },
  { path: [ 0, 1, 2, 3, 4 ], value: 53 },
  { path: [ 0, 0, 0, 0, 0 ], value: 52 },
  { path: [ 0, 0, 1, 1, 1 ], value: 52 },
  { path: [ 0, 1, 2, 2, 2 ], value: 51 },
  { path: [ 0, 1, 1, 2, 2 ], value: 49 },
  { path: [ 0, 0, 1, 2, 2 ], value: 46 },
  { path: [ 0, 1, 2, 2, 3 ], value: 45 },
  { path: [ 0, 1, 1, 2, 3 ], value: 43 },
  { path: [ 0, 1, 2, 3, 3 ], value: 41 },
  { path: [ 0, 0, 0, 0, 1 ], value: 40 },
  { path: [ 0, 0, 1, 2, 3 ], value: 40 }]

可见，数值和最大的路径是[ 0, 0, 0, 1, 2 ]这种路线，也就是数塔图的9 - > 12 -> 10 -> 18 -> 10这种走法。该路线的和为59。

我们用动态规划来验证一下：

dp(0, 0)
输出：59

对比一下，发现与穷举法结果一致。证明我们的动态规划函数也是对的。为了简单性，这个dp函数里，我就不像穷举法一样，去列出具体的路径节点了。

我们再用数塔函数，随意生成一个数塔来试试。来生成一个层数更多的数塔吧，比如10层的：

let fullTower = createNumberTower(10);
输出：[
  [ 16 ],
  [ 13, 0 ],
  [ 2, 14, 1 ],
  [ 10, 5, 17, 15 ],     
  [ 14, 9, 10, 14, 16 ], 
  [ 1, 7, 2, 18, 5, 19 ],
  [
    11,  0, 8, 5,        
     4, 11, 5
  ],
  [
    13, 13, 11,  3,
     2,  3,  9, 16
  ],
  [
     3, 18,  3, 17, 13,
    11, 18, 10, 18
  ],
  [
    17,  2, 9,  7, 8,
     2, 13, 8, 11, 5
  ],
  [
     4, 5, 15,  0,  6,
     9, 0, 12, 14, 19,
    19
  ],
  [
     7,  3, 17,  3, 3,
    17, 13, 10, 11, 6,
     5,  2
  ],
  [
    14,  0, 5, 2, 9, 17,
    10, 18, 6, 4, 6,  4,
    19
  ],
  [
    18,  9, 5, 12, 15,  8,
    13,  0, 3,  2, 14, 17,
    11, 15
  ],
  [
     1, 6,  4, 18,  8, 3,
     0, 1, 12, 12, 15, 6,
    11, 7,  4
  ],
  [
     7,  5,  4,  0,  1, 19,
    10,  6, 18,  5, 16, 12,
     2, 13, 10, 11
  ],
  [
     1, 19, 11,  0, 15, 4, 15,
    18,  0,  9, 14, 18, 4, 11,
     1,  5,  7
  ],
  [
    10, 8,  0,  8,  5, 11,  2,
     1, 5, 16, 19, 16, 15, 14,
    14, 4, 16, 15
  ],
  [
    3, 19,  2,  4, 10,  2, 16,
    1, 12, 10,  6,  5, 16, 15,
    8,  7, 18, 10, 15
  ],
  [
    2,  1, 10,  4, 12, 19, 11,
    7, 16, 13,  0, 18, 14, 17,
    0,  1, 13, 15,  5,  5
  ],
  [
    16,  3,  1,  0,  1,  2,  5,
     4,  8, 10, 17,  2, 18, 19,
     6, 12,  8, 13, 10,  6, 16
  ],
  [
     4, 15,  9,  6, 10, 17, 2,
    11,  7, 17, 16,  2,  5, 2,
    10, 15,  9, 15,  0, 10, 7,
     8
  ],
  [
    18, 18, 11, 11,  4,  1, 4, 13,
    18, 13,  7, 18, 10, 15, 7,  5,
    12, 18, 10, 15, 12,  0, 9
  ],
  [
     8,  8, 11, 18,  6,  4, 17, 15,
     7,  2,  7, 12, 12, 11,  9,  7,
    17, 15,  5,  3, 12, 10,  5,  7
  ],
  [
    14,  2,  5, 16,  1,  6,  7,  6,
    10, 15,  6,  1,  6,  3, 16,  4,
     8,  0, 16,  5, 11, 10,  9, 16,
     1
  ],
  [
    13,  0, 13,  3, 19, 11, 3, 9,
     5,  5, 11, 11, 15,  7, 9, 3,
    11,  2,  0,  2, 11, 19, 5, 1,
    18, 12
  ],
  [
    10, 10, 16, 12, 14,  3, 19, 11,
     9,  0, 10,  6,  7,  0,  6, 14,
     5,  1, 11, 10,  6, 13,  5,  5,
     3, 14,  5
  ],
  [
     3,  5,  4, 14, 13, 15,  1,  8,
    18, 14,  5, 16, 11,  5, 10,  6,
    15, 10, 10,  6
  ],
  [
    10, 18,  7, 17,  1, 10, 17,  9, 3,
    17, 16, 10,  3,  1, 17,  1, 12, 6,
     9, 19, 13, 18, 14,  0,  5,  5, 0,
    19, 17
  ],
  [
     0, 17, 18, 16,  2,  5,  9, 13, 15,
     0, 18, 13,  8,  0,  0, 15, 16,  4,
    12, 10, 12,  8, 15, 16,  2,  9,  1,
     4,  7, 15
  ]
]

穷举法的结果是：

findPath(fullTower).sort((prev, next) => next.value - prev.value)
输出：[
  {
    path: [
      0, 1, 2, 3, 4,
      4, 5, 6, 7, 8
    ],
    value: 126
  },
  {
    path: [
      0, 1, 1, 1, 2,
      3, 3, 4, 5, 5
    ],
    value: 123
  },
  {
    path: [
      0, 1, 1, 2, 3,
      4, 5, 6, 7, 8
    ],
    value: 122
  } ....]

动态规划法给出的结果是：

dp(0, 0)
输出：126

可见也是一致的。多次尝试，结果都是一致，这样就验证了我们想法的正确性。