综合技术

动态规划学习笔记

微信扫一扫,分享到朋友圈

动态规划学习笔记
0

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 = 1

r 2 = 5

r 3 = 8

r 4 = 10

r 5 = 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 4 =16个节点。可以证明(此处略)为了解决长度为n的钢铁切割问题,生成的递归树一共有2 n 个节点,代表调用了2 n 次递归函数。随着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 这种指数级别的递归数量降至多项式n 2 级别。

现在实现第二种:

// 第二种:自底向上
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序列对齐问题的推广。

总结

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

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

阅读原文...


微信扫一扫,分享到朋友圈

动态规划学习笔记
0

稀土掘金

Axure教程:如何制作有趣的小红书促销小游戏?

上一篇

spring5.1.1源码剖析之AbstractAutowireCapableBeanFactory

下一篇

评论已经被关闭。

插入图片

热门分类

往期推荐

动态规划学习笔记

长按储存图像,分享给朋友