最新公告
  • 欢迎光临数据科学与编程,我们是数据学科学兴趣交流小组立即加入我们
  • 动态规划思想及经典算法

    01 DP基本思想

    对于给定一个问题,可以将其分解成不同子问题,之后对对其不同子问题 进行求解,再合并子问题解以得出原问题的解。

    通常情况下,子问题具有一定的相似性,因此,动态规划试图仅仅解决每个子问题一次,从而减少计算量:一旦某个给定的子问题的解已经算出,则将其存储,以便下次需要同一个子问题时直接查表使用。

    分治与动态规划

    共同点:二者都要求原问题具有最优子结构,都是将原问题进行分解,分而治之,分解成若干个子问题,然后将子问题的解进行合并,形成原问题的解。

    不同点:

    • 分治法分解后的子问题是相互独立的,最后通过递归进行合并

    • 动态规划分解后的子问题相互之间有联系,最后通过迭代来做

    02 求解过程

    1.找出最优解的性质,刻画其结构特征和最优子结构特征,将原问题分解成若干个子问题;

    把原问题分解为若干个子问题,子问题和原问题形式相同或类似,只不过规模变小了。子问题都解决,原问题即解决,子问题的解一旦求出就会被保存,所以每个子问题只需求解一次。

    2.递归地定义最优值,刻画原问题解与子问题解间的关系,确定状态;

    在用动态规划解题时,我们往往将和子问题相关的各个变量的一组取值,称之为一个“状态”。一个“状态”对应于一个或多个子问题, 所谓某个“状态”下的“值”,就是这个“状态”所对应的子问题的解。所有“状态”的集合,构成问题的“状态空间”。“状态空间”的大小,与用动态规划解决问题的时间复杂度直接相关。

    3.以自底向上的方式计算出各个子问题、原问题的最优值,并避免子问题的重复计算;

    定义出什么是“状态”,以及在该“状态”下的“值”后,就要找出不同的状态之间如何迁移――即如何从一个或多个“值”已知的 “状态”,求出另一个“状态”的“值”(递推型)。

    4.根据计算最优值时得到的信息,构造最优解,确定转移方程;

    状态的迁移可以用递推公式表示,此递推公式也可被称作“状态转移方程”。

    03 具体问题

    3.1 01背包

    1) 问题描述

    有 N 件物品和一个容量为 V 的背包。第i件物品的费用是 c[i],价值是 w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

    2) 求解过程

    f[i][v] 表示前 i 件物品恰放入一个容量为 v 的背包可以获得的最大价值。则其状态转移方程便是:

    将”前 i 件物品放入容量为 v 的背包中”这个子问题,若只考虑第 i 件物品的策略(放或不放),那么就可以转化为一个只牵扯前 i-1 件物品的问题。如果不放第 i 件物品,那么问题就转化为”前 i-1 件物品放入容量为 v 的背包中”;如果放第 i 件物品,那么问题就转化为”前 i-1 件物品放入剩下的容量为 v-c[i] 的背包中”,此时能获得的最大价值就是 f [i-1][v-c[i]] 再加上通过放入第 i 件物品获得的价值 w[i] 。

    3) 伪代码


     

    4) 空间优化

    二位数组的空间复杂度显而易见为 O(nm) ,n 可能不大,但是实际应用的 w 可能会很大,这样造成了比较大的空间占用。而仔细观察发现,矩阵中的值只与当前值的左上角的矩阵里的值有关。并且是按行进行更新的,所以可以用一个一维数据就能进行状态的更替,不过要注意更新的方向。

    所以依赖关系为:下面依赖上面,右边依赖左边;

    如果正常地从左到右边,那么右边面等待更新的值需要的依赖(左边)就会被覆盖掉,所以应该每行从右边开始更新。代码如下:

    3.2 字符匹配

    1) 问题描述

    给定两个字符word1和word2,找到将word1和word2匹配的最大字符,所需操作的最小步数。(每个操作计为1步)。

    对单词允许以下3种操作:

    a)插入字符

    b)删除字符

    c)替换字符

    2) 求解过程

    定义两个字符串之间的编辑距离:从字符串str1str2的最少的操作次数。首先,编辑距离是不会大于str1.length + str2.length的(可以通过删除操作把两个字符串都转化为空串)。假设求字符AB的编辑距离,考虑下面几种情况:

    如果A[i] = B[j],那么这时候还需要操作吗?

    这个时候的删除和替换操作只会让情况变得更坏,而且插入操作不会使情况变得更好,只要计算    和    的距离就可以了,所以此时F(i, j) = F(i-1, j-1)

    如果A[i] != B[j],怎么办呢?需要进行如下操作:

    1. 删除A串的第一个字符,然后计算    和   的距离;

    2. 删除B串的第一个字符,然后计算    和    的距离;

    3. 修改A串的第一个字符为B串的第一个字符,然后计算    和    的距离;

    4. 修改B串的第一个字符为A串的第一个字符,然后计算    和    的距离;

    5. 增加B串的第一个字符到A串的第一个字符之前,然后计算    和    的距离;

    6. 增加A串的第一个字符到B串的第一个字符之前,然后计算   和    的距离;

    合并之后可以简化为以下三步:

    1. 从    变过来,这时候只需要把    替换为   即可;

    2. 从    变过来,这时候只需要将    删除即可;

    3. 从    变过来,这时候只需要在    后插入字符    即可;

    那么此时

     ,,,,,

    注:其中    表示    和    之间的编辑距离。

    多步决策可如下表示:

    3) 伪代码

    4) 空间优化

    二维数组复杂度为   ,分析矩阵法的执行过程,会发现每次计算的时候只需要本行和上一行的结果,而和再之前的行无关,如果第 i 行已经完成计算,则第 i-1 行就不再需要了,所以可以只采用两行的矩阵来实现,当字符串长度大的时候可以有效的节省存储空间。

     

    本站上原创文章未经作者许可,不得用于商业用途,仅做学习交流使用,本站免责声明。转载请注明出处,否则保留追究法律责任的权利。《署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0)》许可协议授权
    数据科学与编程 » 动态规划思想及经典算法

    发表评论

    • 52会员总数(位)
    • 320资源总数(个)
    • 25本周发布(个)
    • 3 今日发布(个)
    • 333稳定运行(天)

    提供最优质的博文资源集合

    立即阅览 了解详情