动态规划(Dynamic Programming,简称 DP)是一种解决问题的技巧,主要被用来优化那些「记不住自己过去曾解出来的答案所以只好重复再解」的算法,让它们可以「记忆」已经找出来的答案,从而不断利用,以大大降低时间复杂度(从指数级降到线性)。

记忆法(Memoization)与制表法(Tabulation)

以费氏数列来说明。费氏数列又称费布那西(Fibonacci)数列,它是一种发散数列,第 1 项的值为 0,第 2 项的值为 1,第 #{{n}}# 项(#{{ n \geq 3 }}#)的值为第 #{{n - 1}}# 项和第 #{{n - 2}}# 项的总和。费氏数列看起来会长得像以下这样:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, ...

以数学函数 #{{F(n)}}# 来表示费氏数列的第 #{{n}}# 项数值,可以写成:

#{{{
\begin{alignedat}{2}
F(1) &{}={}&& 0 \\
F(2) &{}={}&& 1 \\
F(n) &{}={}&& F(n - 1) + F(n - 2), \text{where } n \geq 3 \\
\end{alignedat}
}}}#

不过由于写程序习惯从 0 开始数,所以最好还是将费氏数列的第一项设计为 #{{F(0)}}#,也就是:

#{{{
\begin{alignedat}{2}
F(0) &{}={}&& 0 \\
F(1) &{}={}&& 1 \\
F(n) &{}={}&& F(n - 1) + F(n - 2), \text{where } n \geq 2 \\
\end{alignedat}
}}}#

这篇文章之后都会用 #{{F(0)}}# 作为费氏数列的第一项。

根据定义,当我们要计算 #{{F(5)}}# 时,要先去算 #{{F(4)}}# 和 #{{F(3)}}#,而要算 #{{F(4)}}# 时,就要先算 #{{F(3)}}# 和 #{{F(2)}}#。有没有发现 #{{F(3)}}# 此时会被算两次?当然,#{{F(2)}}# 也是类似的情形,同样会被计算多次。如果我们画出 #{{F(5)}}# 的递归树(Recursion Tree),会长成以下这样:

                          F(5)
                          /  \
                         /    \
                        /      \
                       /        \
                      /          \
                     /            \
                    /              \
                   /                \
                  /                  \
                 /                    \
                /                      \
              F(4)                     F(3)
              /  \                     /  \
             /    \                   /    \
            /      \                 /      \
           /        \               /        \
          /          \             /          \
       F(3)         F(2)         F(2)         F(1)
       /  \         /  \         /  \
      /    \       /    \       /    \
   F(2)    F(1) F(1)   F(0)  F(1)    F(0)
   /  \
  /    \
F(1)  F(0)

可以明显发现有重复的子树存在,因此如果直接利用费氏数列的定义写成如下的程序,运算起来性能是很差的。时间复杂度为 #{{O(2^n)}}#。

我们可以利用动态规划来优化以上的递归函数(Recursive Function)。动态规划的作法,大方向分为两种,第一种是记忆法,第二种是制表法,前者用于优化从上而下(Top Down)的算法,后者用于产生由下而上(Bottom Up)的算法。

Top-down:记忆法(Memoization)

Top-down 就是从目的开始,往下完成所需的细节。例如要盖一栋 3 层楼的房子,为了要盖第 3 层,就必须要先盖第 2 层。为了要盖第 2 层,就必须要先盖第 1 层。

递归函数通常就是属于 Top-down 的问题解决方法,这种解法通常很容易就能被(抽象、粗略地)理解,但具体要动作的时候就很难知道要从哪里开始、该怎么进行,因为它会把一个大问题自动分成许多小问题。然而,这些小问题可能会像上面提到的费氏数列函数那样「会重复」,如果算法没有机制去避免重复解这些同样的问题,那这个算法就可以使用动态规划的记忆法来优化,大大减少递归函数的调用次数。

以上面提到的费氏数列函数来说,我们可以创建一个大小为 n + 1 的 dp 数组,将数组元素值初始化为能够判断是否已经保存结果的值(以费氏数列来说可以设成 0 或是整数的最大值)。第一次计算 #{{F(k)}}#,#{{k <= n}}#,在计算出 #{{F(k - 1) + F(k - 2)}}# 的结果后,把结果保存到 dp[k] 中,之后如果又要计算 #{{F(k)}}#,只需要从 dp[k] 中取得已知的结果就好了。

所以把费氏数列的递归函数加入动态规划的记忆法后,代码如下:

此时 #{{F(5)}}# 的递归树就会变成:

                          F(5)
                          /  \
                         /    \
                        /      \
                       /        \
                      /          \
                     /            \
                    /              \
                   /                \
                  /                  \
                 /                    \
                /                      \
              F(4)                     F(3)
              /  \
             /    \
            /      \
           /        \
          /          \
       F(3)         F(2)
       /  \
      /    \
   F(2)    F(1)
   /  \
  /    \
F(1)  F(0)

时间复杂度顿时减少为 #{{O(n)}}# 了。

Bottom-up:制表法(Tabulation)

Bottom-up 就是先完成细节,再逐步达成目的。例如要盖一栋 3 层楼的房子,盖好第 1 层后盖第 2 层,盖好第 2 层后盖第 3 层。

Bottom-up 的问题解决方法,通常不容易被理解,但具体要动作的时候可以清楚地知道要从哪里开始、该怎么进行。

对于一个可以用动态规划记忆法优化的算法,我们其实也可以直接用制表法来改写它。如果原本是递归的算法,也可以顺便把递归转成迭代。首先要做的就是观察 Top-down 的问题解决顺序,创建出足够保存过程中所有问题的解的保存空间,然后从最小的问题开始解,把解保存起来,以便之后解大问题的时候取用。

以上面提到的费氏数列函数来说,我们可以创建一个大小为 n + 1 的 dp 数组,dp[i] 预计要用来保存 #{{F(i)}}# 的解。先根据费氏数列的基本案例(base case),把 dp[0] 指派为 0、dp[1] 指派为 1,接着利用循环计算 #{{i = 2 \text{ to } n}}# 时,dp[i] 的结果。最后算出来的 dp[n],就是 F(n) 的值。

所以把费氏数列的递归函数用动态规划的制表法改写后,代码如下:

以上的迭代版的费氏数列函数,时间复杂度为 #{{O(n)}}#。

当然,以上程序还有能够小改进的地方,因为在算 #{{F(i)}}# 的时候只有 #{{F(i - 1)}}# 和 #{{F(i - 2)}}# 的解会被使用到,所以我们只需保存前两个问题的解就好了。将代码优化如下:

制表法必须从最小的问题开始,一步步地将问题扩大到我们想要解决的大问题,在这个过程中很可能会去解到不需要解的小问题。因此在理想的情况下(忽略为了分割子问题而产生的开支)或是某些情况下(制表法需要去解非常多不需要解的小问题),用 Top-down 搭配记忆法来解决问题会是比较好的方式。

有重叠子问题的问题

当一个问题能被分解成子问题,而子问题再继续分解下去的子问题有重复的情况时,表示这个问题有重叠子问题(Overlapping Subproblem)。动态规划可以使这些重叠子问题只会被计算一次。

底下会再举几个有重叠子问题的题型。

爬楼梯问题(排列)

一个有着 #{{n}}# 阶的阶梯,如果每步可以爬 1 阶、2 阶或 3 阶,要爬完 #{{n}}# 阶,有几种走法?

先以 Top-down 的方式来思考这个问题。因为在最后一步要爬完 #{{n}}# 阶,所以在运行最后一步前,有可能已经爬完了 #{{n - 1}}# 阶、#{{n - 2}}# 阶和 #{{n - 3}}# 阶,那么从底部爬到第 #{{n}}# 阶的走法之数量就会是爬完 #{{n - 1}}#、#{{n - 2}}# 和 #{{n - 3}}# 阶的走法之数量的总和。最小的问题为爬 0 阶(1 种走法,那就是不走)、爬 1 阶(1 种走法)和爬 2 阶(2 种走法,一步 2 阶或是两步 1 阶)。

以程序来解题的话,我们可以写出以下的递归函数:

当然,这个函数的性能很差,时间复杂度为 #{{O(3^n)}}#,先不管它。因为还有个更严重的地方,那就是这个程序目前只能固定地计算每步爬 1 阶、2 阶或 3 阶,功能实在太弱了!所以我们要把程序改成可以从函数参数输入一步允许走几阶(假设每次至少会走一步,每步至少会走 1 阶,且会递增输入)。而因为输入的最小步可能会大于 1 阶,所以需要注意到无解的情形(例如一步可以走 3 阶或 7 阶,那么要爬到第 11 阶就是不可能的)。若是无解,则把结果当作 0。

程序强化功能后如下:

由于以上代码有重叠子问题,所以可以用动态规划的记忆法来优化或是用制表法将其改写成迭代函数。

以制表法为例,改写如下:

还可以继续优化:

贴磁砖问题(排列)

现在有一个尺寸为 #{{X \times Y}}# 的平面,要用尺寸为 #{{X \times 1}}# 的磁砖贴满(不留缝隙),磁砖只能被横贴(#{{X \times 1}}#)和直贴(#{{1 \times X}}#),有几种方式?

先以 Top-down 的方式来思考这个问题。首先要知道 #{{X}}# 和 #{{Y}}# 谁大谁小,若 #{{X > Y}}#,则只有一种贴法(全部横贴);若 #{{X = Y}}#,则只有两种贴法(全部横贴或是全部直贴)。若 #{{ X < Y }}#,且最后一步是横贴的话,表示在运行最后一步前,已经贴满了 #{{X \times (Y - 1)}}#,而如果最后一步是直贴的话,表示先前已经贴满了 #{{X \times (Y - X)}}#,并且又再直贴了 #{{X - 1}}# 个磁砖,所以还剩最后一个磁砖要直贴。也就是说,全部贴满有几种方式就是,贴满 #{{X \times (Y - 1)}}# 有几种方式和贴满 #{{X \times (Y - X)}}# 有几种方式的总和。

以程序来解题的话,我们可以写出以下的递归函数:

由于以上代码有重叠子问题,所以可以用动态规划的记忆法来优化或是用制表法将其改写成迭代函数。

以制表法为例,改写如下:

因为原本函数的 x 参数并不会在递归时发生变化,所以在使用动态规划时,只需创建出一维数组就好了。

买东西问题(组合)

一片薯饼 10 元、一杯可乐 20 元、一个汉堡 40 元,刚好买到 #{{n}}# 元有几种组合?

先以 Top-down 的方式来思考这个问题。首先要注意的是,这是一个「组合」(Combination)问题,例如「先买两个汉堡,再买一杯可乐」(40→80→100)和「先买一杯可乐,再买两个汉堡」(20→60→100)只能算是同一种买法。

如果我们永远按照物品的某种顺序来购买的话,就可以得到该组合唯一的一种排列方式。

那么假设我们从便宜的物品开始买。因为在最后一步要买到 #{{n}}# 元,所以在运行最后一步前,有可能已经买到了 #{{n - 10}}# 元、#{{n - 20}}# 元或 #{{n - 40}}# 元,所以从 0 元买到 #{{n}}# 元的组合方式之数量为买到 #{{n - 10}}# 元、#{{n - 20}}# 元和 #{{n - 40}}# 元的组合方式之数量的总和。若倒数第二步是买到 #{{n - 10}}# 元(最后一步花了 10 元),那么倒数第三步就只能是买到 #{{n - 10 - 10}}# 元(倒数第二步只能花 10 元);若倒数第二步是买到 #{{n - 20}}# 元(最后一步花了 20 元),那么倒数第三步就可以是买到 #{{n - 20 - 10}}# 元或是 #{{n - 20 - 20}}# 元(倒数第二步花了 10 元或是 20 元)……依此类推。最小的问题为买到 0 元(1 种买法,那就是都不买)、买到 1~9 元(0 种买法,无法达成)、买到 10 元(1 种买法,买 1 个薯饼)和买到 11 ~ 39 元,但是买到 11 ~ 39 元我们不太能够直接知道有多少种买法,所以不要把它当作是基本案例(base case)。

以程序来解题的话,我们可以写出以下的递归函数:

当然,这个函数的性能很差,先不管它。因为还有个更严重的地方,那就是这个程序目前只能固定地用单价 10、20、40 元的商品来计算,功能实在太弱了!所以我们要把程序改成可以从函数参数输入商品的单价(假设至少有一种商品,每种商品的单价至少会有 1 元,且会递增输入)。

程序强化功能后如下:

由于以上代码有重叠子问题,所以可以用动态规划的记忆法来优化或是用制表法将其改写成迭代函数。

以制表法为例,改写如下:

观察以上程序,可以发现 dp 数组能简化成长度为 target_cost + 1 的一维数组。程序继续优化如下:

而以上程序,又可以再优化成:

经过简化并优化之后的函数,仿佛使用了一个全新的算法。以自然语言来描述的话,就是:先找出只能买第一个商品时的所有组合,再利用这个结果,找出第二个商品也能买时的所有组合,再利用这个结果,找出第三个商品也能买时的所有组合……

以题目来说明,重温一下题目:一片薯饼 10 元、一杯可乐 20 元、一个汉堡 40 元,刚好买到 #{{n}}# 元有几种组合?

若 #{{n = 40}}#,当只能买第一个商品时,0 元、10 元、20 元、30 元、40 元各会有一种组合,也就是买 0 片、1 片、2 片、3 片、4 片薯饼。

当第二个商品也能买时,组合就会是 0 片薯饼 +0 杯可乐(0 元)、0 片薯饼 +1 杯可乐(20 元)、0 片薯饼 +2 杯可乐(40 元)、1 片薯饼 +0 杯可乐(10 元)、1 片薯饼 +1 杯可乐(30 元)、2 片薯饼 +0 杯可乐(20 元)、2 片薯饼 +1 杯可乐(40 元)、3 片薯饼 +0 杯可乐(30 元)、4 片薯饼 +0 杯可乐(40 元)。排序一下:

  • 0 元:0 片薯饼 +0 杯可乐
  • 10 元:1 片薯饼 +0 杯可乐
  • 20 元:2 片薯饼 +0 杯可乐、0 片薯饼 +1 杯可乐
  • 30 元:3 片薯饼 +0 杯可乐、1 片薯饼 +1 杯可乐
  • 40 元:4 片薯饼 +0 杯可乐、2 片薯饼 +1 杯可乐、0 片薯饼 +2 杯可乐

当第三个商品也能买时:

  • 0 元:0 片薯饼 +0 杯可乐
  • 10 元:1 片薯饼 +0 杯可乐
  • 20 元:2 片薯饼 +0 杯可乐、0 片薯饼 +1 杯可乐
  • 30 元:3 片薯饼 +0 杯可乐、1 片薯饼 +1 杯可乐
  • 40 元:4 片薯饼 +0 杯可乐、2 片薯饼 +1 杯可乐、0 片薯饼 +2 杯可乐、0 片薯饼 +1 个汉堡

观察一下上述两清单的规律,就可以知道为什么程序要这样算了。

可以再利用「最大公因数(GCD)」来修改这个程序,避免价格太大时,每次迭代 i 只加 1 造成的浪费(太多 0 种组合)。有关于最大公因数的找法可以查看这篇文章:

程序修改如下: