动态规划学习笔记

R.Bellman从1955年开始系统地研究动态规划方法，为这个领域奠定了坚实的数学基础。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。距今（2019）已经62年。

动态规划（Dynamic programming，简称DP）是一种在数学、管理科学、计算机科学、经济学和生物信息学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。(dynamic programming 中的"programming"指的是一种表格法，并非编写计算机程序)

分治法通常将问题划分为互不相交的子问题，递归求解子问题，再将他们的解组合起来。

与分治法不同的是，动态规划应用于子问题重叠的情况，即不同的子问题具有公共的子子问题。动态规划对每个子子问题只求解一次，把结果保存到一个表格(programming)当中，避免了像分治法一样不断重复计算。

动态规划方法通常用来求解最优化问题,重点寻找最优值，而非所有最优解。

最优值：最优化的结果的值，例如商旅问题里的最短路径的值。

最优解：能构造最优值的解决方案，例如商旅问题里达到最短路径的行路方案。

简单示例

以下示例都不止一种解法，本文里只讲动态规划的解法。

爬楼梯问题

习题来自leetcode.

问题

假设你正在爬楼梯。需要 n (n是一个正整数)阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？(必须正好到达楼顶）

写一个程序，输入为n，输出为n阶楼梯对应的方法总数。

示例

当n=2，返回2，方法有：1步+1步; 2步; 当n=3，返回3，方法有：1步+1步+1步; 1步+2步; 2步+1步; 当n=4，返回5，方法有：1步+1步+1步+1步; 1步+1步+2步; 1步+2步+1步; 2步+1步+1步; 2步+2步;

动态规划求解

有n阶楼梯时，令C(n)为所有可以爬到楼顶的方法的总数，即C(n)为n阶爬楼梯问题的解。

由题已知，n > 0, C(1) = 1，C(2) = 2

现在来讨论n>2时，n阶楼梯的解

图中表示了爬n阶楼梯的两种情况，一种是最后一次选择跨两步，一种是最后一次选择跨一步。（刻画一个最优解的结构特征）

选择最后一次跨两步的时候，之前还有n-2阶台阶。由于n-2阶台阶怎么爬与最后一次无关，所以在这种情况下，n阶台阶可以看成n-2阶楼梯问题的任一爬法 + 最后一次爬两阶。那么n-2阶楼梯有多少种解法，此种情况下的n阶楼梯就是多少种解法，即最后一次爬两阶时，n阶楼梯的解法有C(n-2)种。

同理，选择最后一次跨一步的时候，n阶台阶可以看成n-1阶楼梯问题的任一爬法 + 最后一次爬一阶，此种情况下n阶楼梯的解法就是n-1阶的解法C(n-1)。

由于以上两种情况加起来就是所有的情况，所以n阶的解法等于n-1阶的解法加n-2阶的解法。公式就是C(n) = C(n-1) + C(n-2)，是一个典型的斐波那契数列。（递归地定义最优解的值）

斐波那契数列是有计算公式的，可以直接利用公式求解。但是我们现在学习动态规划，就先假装不知道这个公式，利用动态规划的思想去求解。

定义一个数组dp, dp[i]表示i阶爬楼梯问题的解。

const dp = []; // 储存子问题最优解的表格
复制代码

现在已知初始条件

dp[1] = 1;
dp[2] = 2;
复制代码

根据递归公式可得

dp[i] = dp[i-1] + dp[i-2]
复制代码

递归公式加上初始条件和循环，得到整体的程序

var climbStairs = function(n) {
    const dp = new Array(n+1);
    // 假设dp[0] = 1，令dp[2] = dp[1] + dp[0],这样就构造了一个完整的斐波那契数列
    dp[0] = dp[1] = 1;
    for(let i = 2; i <= n; i++){
        // 计算最优解的值，通常采用自底向上（从最小的子问题开始求解）的方法。
        dp[i] = dp[i-1] + dp[i-2];
    }
    return dp[n];
}
复制代码

可能有人会注意到，其实每次计算dp[i]只用到了dp[i-1]、dp[i-2]这两个值，可以考虑只用两个变量储存之前的计算结果，每次更新对应的两个值就可以了。这是可以的，就当做另外的习题做一做吧。

至此，爬楼梯问题就通过动态规划解决啦，算法时间复杂度为O(n),空间复杂度为O(n)(如果只更新两个值，那空间复杂度为O(1))。

通常按以下步骤来设计一个动态规划算法：

1. 刻画一个最优解的结构特征。
2. 递归地定义最优解的值。
3. 计算最优解的值，通常采用自底向上（从最小的子问题开始求解）的方法。
4. 利用计算出的信息构造出一个最优解（如果只需要最优值、不需要最优解，可忽略此步骤）。

钢铁的最优切割问题

习题及解题思路来自《算法导论》。

问题

假设出售一段长度为i的钢条的价格为Pi(i = 1,2,3,...)，钢条的长度为整数，给出了一个价格表的样例：

长度i	1	2	3	4	5	6	7	8	9	10
价格pi	1	5	8	9	10	17	17	20	24	30

现在给定一段长度为n英寸的钢条和如上的价格表，求钢条切割方案，使得销售收益 r _n 最大。注意，不切割的方案有可能是收益最大的方案。

示例

当n = 4时，包括不切割的方案在内，一共有八种切割方案。如图所示，图中数字代表该段钢条的价格。其中将钢条切成两段2英寸的钢条的方案总收益最高，为10。

r ₁ = 1

r ₂ = 5

r ₃ = 8

r ₄ = 10

r ₅ = 13

...

动态规划求解

问题分析

当钢条长度为n时，将钢条水平放置。

从左往右计量下刀位置，假设切第一刀，第一刀的位置范围是[1,n]，为n表示不切割。长度为0时，钢条价值为0。

第一刀左边的钢条长度为i，这段钢条不再切割，其价值为p _i ；第一刀右边的钢条长度为n-i, 可切割，其价值为r _n-i 。

只要遍历所有第一刀（包括不切）的情况,找到其中的最大值，就能找到此时钢条的最优切割方案 r _n 。

现在我们可以得到公式：

朴素的递归算法

有了这个递推公式，我们就可以实现一个递推算法：

function cut_recursive(p, n) {
    if(n===0){
        return 0;
    }
    let q = Number.NEGATIVE_INFINITY;
    for(let i = 1; i <= n; i++) {
        q = Math.max(q, p[i]+ cut_recursive(p, n-i));
    }
    return q;
}
复制代码

现在来考察一下这个递推算法的复杂度

上图里树的每一个节点代表一次递归，节点的数字代表当前cut_recursive的参数n，n是钢条长度。其子节点为当前递归为了解决问题需要再次调用的递归及参数n。例如根节点4，表示本次递归的钢条长度为4，为了解决这个问题，还需要通过递归求解钢条长度为3、钢条长度为2、钢条长度为1、钢条长度为0的问题。

图中的树有2 ⁴ =16个节点。可以证明（此处略）为了解决长度为n的钢铁切割问题，生成的递归树一共有2 ⁿ 个节点，代表调用了2 ⁿ 次递归函数。随着n增大，算法递归的数量呈指数型增长。

朴素递归算法+备忘

我们在问题分析里，找到了具有最优子结构的分解方式，以及相应的递推公式，这已经完成了动态规划的重要部分：刻画最优解的结构特征和递归的定义最优解的值。我们可以接着上面的分解方式来完成接下来的动态规划求解。

现在已知递归方程式：

仔细观察递归树可以发现，有些节点是不断重复的：

将相同问题进行同色着色处理，其实要解决的非重复问题只有5个，大多数都是递归过程中不断求解重复的问题。

假如我们安排一下计算的顺序，将计算过的结果保存下来，再遇到相同的子问题时，可以直接使用计算好的值，不必再重新计算。因此：

动态规划方法中，会付出额外的内存空间来节省计算时间，是典型的时空权衡（time-memory trade-off)。

动态规划一般有两种保存结果的实现方法：

第一种是 带备忘的自顶向下法 。自顶向下法可以用递归实现，加上保存计算结果的备忘即可。在朴素的递归算法里，只要稍微修改一下，求值时先检查备忘里是否已经有计算好的值，如果有，直接使用计算好的值，否则进入下一层递归。

第二种是 自底向上法 。自底向上法是预先求出小问题的解，再通过小问题的解构成大问题的解。

// 第一种：带备忘的自顶向下法
function memory_cut(p, n) {
    let r = new Array(n+1).fill(Number.NEGATIVE_INFINITY);
    return memory_cut_recursive(p, n, r)
}
function memory_cut_recursive(p, n, r) {
    if(r[n] >= 0){
        // 检查是否存在计算过的值
        return r[n];
    }
    // 没有计算过则按正常流程计算
    if(n===0){
        return 0;
    }
    let q = Number.NEGATIVE_INFINITY;
    for(let i = 1; i <= n; i++) {
        q = Math.max(q, p[i]+ memory_cut_recursive(p, n-i, r));
    }
    return q;
}
复制代码

在原来递归算法的基础上加上备忘就实现了第一种方法。现在的递归调用树情况：

图中带五角星的节点在递归过程中直接返回了之前的计算结果。可以看到，现在已经减少了许多不必要的计算过程，生成的递归树一共有(n*(n+1)/2) + 1个节点。与原来的算法相比，已经从2 ⁿ 这种指数级别的递归数量降至多项式n ² 级别。

现在实现第二种：

// 第二种：自底向上
function buttom_up_cut(p, n) {
    const dp = new Array(n+1);
    dp[0] = 0;
    for(let i = 1; i <= n; i++){
        // 从规模小的问题开始求解
        let q = Number.NEGATIVE_INFINITY;
        for(let j = 1; j <= i; j++){
            // 求解规模为i的问题时，可以直接使用比i规模更小的子问题的结果dp[i-j]
            q = Math.max(q, p[j] + dp[i - j]);
        }
        dp[i] = q;
    }
    return dp[n];
}
复制代码

自底向上的方案的思想就是先求出小规模问题，在求解大规模问题时，就可以直接使用之前计算储存好的结果。

两种方案的时间复杂度是相近的，空间复杂度均为O(n)。但是由于自底向上的方案没有调用递归函数的开销，所以一般倾向于使用自底向上的方案。

通常按以下步骤来设计一个动态规划算法（再来一次）：

1. 刻画一个最优解的结构特征。
2. 递归地定义最优解的值。
3. 计算最优解的值，通常采用自底向上（从最小的子问题开始求解）的方法。
4. 利用计算出的信息构造出一个最优解（如果只需要最优值、不需要最优解，可忽略此步骤）。

动态规划原理

怎么判断一个问题能否用动态规划去解决呢？《算法导论》一书上提到适合的场景应该具有的两个要素： 最优子结构和子问题重叠 。

最优子结构

大问题的最优解可以由其分裂出的子问题的最优解推导得到，就称该问题具有最优子结构。

例如爬楼梯问题，n阶楼梯的最优解由子问题n-1阶、子问题n-2阶的最优解推导得到。

刻画最优解的结构时，分裂出的子问题之间应该是 无关 的，否则此种子结构不能用于动态规划。

无关的意思： 子问题 M 如何构成其最优解不会影响子问题 N 如何构成最优解，则子问题 M 与子问题 N 无关。

举一个子问题相关的例子。求无权最长路程（无环）：假设u为起点，v为终点，求u到v的最长路径（无环）。位置如下图所示：

假如将原问题u->v拆分为子问题1 u->w和子问题2 w->v，想要通过求两个子问题的最长路径来求得u->v的最长路径时，就会出现一些问题：

如果不考虑其他子问题如何求解，直接求解自己的最长路径时：

u->w的最长路径是u->t->w, w->v的最长路径是 w->t->v，出现了一个闭环w->t->w

所以求解子问题2 w->v时，必须考虑子问题1用到了哪些点，子问题1用过的点就不能再用了。子问题2就与子问题1相关了。这种子结构划分不适合用动态规划求解。

子问题重叠

在动态规划的递归过程中，如果会反复地求解相同的子问题，而不是一直生成新的子问题，这样就称为最优化问题具有重叠子问题特性。

动态规划会把每一个子问题的解都存在一张表里，这样在求解重复子问题的时候，就能直接查表，时间代价为常量。动态规划虽然付出了额外的空间，但是时间上的提升可能是巨大的，是典型的时空权衡。

子问题重叠性质与子问题无关并不矛盾，它们描述的是不同层面的性质。以钢铁切割问题为例，求解长度为4的钢铁切割问题时，需要考虑到第一次切割后是1+3的情况

子问题1为长度1的钢铁切割，子问题2为长度为3的钢铁切割。这两个子问题是无关的，第一个子钢铁怎么切割与第二个钢铁怎么切割无关。

而求解子问题2时，会进一步拆分子问题，出现子子问题1（长度为1的钢铁切割）、子子问题2（长度为2的钢铁切割）。此时子子问题1和子问题1是同一个问题。 此时该结构就有重叠的子问题。

经典示例

编辑距离

题目描述来自leetcode

问题

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：

• 插入一个字符
• 删除一个字符
• 替换一个字符

示例

输入: word1 = "horse", word2 = "ros"

输出: 3

解释:

horse -> rorse (将 'h' 替换为 'r')

rorse -> rose (删除 'r')

rose -> ros (删除 'e')

动态规划求解

本例不做详细的分析了，直接给出结构特征和递归方程式：

M为可以操作的字符串，N为目标字符串

m[i]包含字符串M中第1到第i个字符的子字符串（字符位置从1开始计数），n[j]包含字符串N中第1到第j个字符的子字符串，令dp[i][j]为m[i]与n[j]的最小编辑距离。

第一种情况是当M[i]与N[j]的字符相同时，不需要进行任何操作，所以dp[i][j] = dp[i-1][j-1]

第二种情况是当M[i]与N[j]字符不相同时，可能会进行三种操作：

• 在M[i-1]后，增加一个和N[j]一样的字符，则dp[i-1][j] = dp[i-1][j-1] + 1，即dp[i][j] = dp[i][j-1] + 1。
• 删除M[i]，则dp[i][j-1] = dp[i-1][j-1] + 1。 替换一下参数，即dp[i][j] = dp[i-1][j] + 1。
• 直接将M[i]替换为N[j]字符，则dp[i][j] = dp[i-1][j-1] + 1。

三种操作中，操作数最小的为dp[i][j]的编辑距离。

延伸

《算法导论》第15章的习题15-5里有操作步骤更为复杂的编辑距离问题。编辑距离问题是DNA序列对齐问题的推广。

总结

动态规划的核心其实是找到具有 最优子结构 的特征，以及可以由子问题最优解构造问题最优解的 递归方程式 。只要找到这些，加上 备忘 的使用，就可以将一个看起来很复杂需要遍历的问题，转化为多项式时间的带备忘的递归问题。

本文只是个人学习的心得体会，涉及的范围不够广和深，相当于一篇入门介绍。鉴于自己是初学者，可能理解不够到位，若有错漏欢迎指出！