新闻中心News
软件开发_开发软件_软件外包_APP开发_广州软件开发_网站建设_网站设计_广州网站建设_广州鑫亮信息科技有限公司

「数据结构与算法」动态规划学习笔记:线性动

作者:admin | 点击: | 来源:鑫亮
2611
2021
用动态规划解决问题的过程有以下几个关键点: 状态定义 状态的转移 初始化 边界条件 状态定义 就是定义子问题,如何表示目标规模的问题和更小规模的问题。例如常见的方法:定义状态 d...
用动态规划解决问题的过程有以下几个关键点: 状态定义 状态的转移 初始化 边界条件 状态定义 就是定义子问题,如何表示目标规模的问题和更小规模的问题。例如常见的方法:定义状态 dp[n],表示规模为 n 的问题的解,dp[n - 1] 就表示规模为 n - 1 的子问题的解。在实战中 dp[n] 的具体含义需要首先整理清楚再往下做状态转移 就是子问题之间的关系,例如定义好状态 dp[n],此时子问题是 dp[n-1] 等,并且大规模的问题的解依赖小规模问题的解,此时需要知道怎样通过小规模问题的解推出大规模问题的解。这一步就是列状态转移方程的过程。一般的状态转移方程可以写成如下形式 dp[n] = f(dp[i]) 其中 i < n 按照状态定义和状态转移的常见形式,可以对动态规划进行分类。 其中线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的,较大规模的问题的解依赖较小规模的问题的解。 这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。 线性动态规划简介 线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的,较大规模的问题的解依赖较小规模的问题的解。 这里问题规模为 i 的含义是考虑前 i 个元素 [0..i] 时问题的解。 状态定义: dp[n] := [0..n] 上问题的解 状态转移: dp[n] = f(dp[n-1], ..., dp[0]) 从以上状态定义和状态转移可以看出,大规模问题的状态只与较小规模的问题有关,而问题规模完全用一个变量 i 表示,i 的大小表示了问题规模的大小,因此从小到大推 i 直至推到 n,就得到了大规模问题的解,这就是线性动态规划的过程。 线性动态规划是动态规划中最基本的一类。问题的形式、dp 状态和方程的设计、以及与其它算法的结合上面变化很多。按照 dp 方程中各个维度的含义,可以大致总结出几个主流的问题类型: 单串 双串 矩阵 无串 单串 单串 dp[i] 线性动态规划最简单的一类问题,输入是一个串。 线性动态规划中单串 dp[i] 的问题,状态的推导方向以及推导公式如下: 依赖比 i 小的 O(1) 个子问题:dp[n] 只与常数个小规模子问题有关 状态的推导过程: dp[i] = f(dp[i - 1], dp[i - 2], ...) 时间复杂度 O(n),空间复杂度 O(n) 可以优化为 O(1),例如 LeetCode 70, 801, 790, 746 都属于这类。 如上图所示,虽然蓝紫色部分的 dp[i-1], dp[i-2], ..., dp[0] 均已经计算过,但计算橙色的当前状态时,仅用到 dp[i-1],这属于比 i 小的 O(1) 个子问题。 例如,当 f(dp[i-1], ...) = dp[i-1] + nums[i] 时,当前状态 dp[i] 仅与 dp[i-1] 有关。这个例子是一种数据结构前缀和的状态计算方式。 例题: 一个数组有很多个子数组,求哪个子数组的和最大。可以按照子数组的最后一个元素来分子问题,确定子问题后设计状态 dp[i] := [0..i] 中,以 nums[i] 结尾的最大子数组和 状态的推导是按照 i 从 0 到 n - 1 按顺序推的,推到 dp[i],时,dp[i - 1], ..., dp[0] 已经计算完。因为子数组是连续的,所以子问题 dp[i] 其实只与子问题 dp[i - 1] 有关。如果 [0..i-1] 上以 nums[i-1] 结尾的最大子数组和(缓存在 dp[i-1] )为非负数,则以 nums[i] 结尾的最大子数组和,就在 dp[i-1] 的基础上加上 nums[i] 就是 dp[i] 的结果否则以 i 结尾的子数组就不要 i-1 及之前的数,因为选了的话子数组的和只会更小。 因此,状态转移方程如下: dp[i] = nums[i] + max(dp[i - 1], 0) 依赖比 i 小的 O(n) 个子问题:dp[n] 与此前的更小规模的所有子问题 dp[n - 1], dp[n - 2], ..., dp[1] 都可能有关系 状态推导过程如下: dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0]) 如上图所示,计算橙色的当前状态 dp[i] 时,蓝紫色部分为此前计算过的状态 dp[i-1], ..., dp[0] 均有可能被用到,在计算 dp[i] 时需要将它们遍历一遍完成计算。 其中 f 常见的有 max/min,可能还会对 i-1,i-2,...,0 有一些筛选条件,但推导 dp[n] 时依然是 O(n) 级的子问题数量。 双串 有两个输入从串,长度分别为 m, n,此时子问题需要用 i, j 两个变量表示,分别代表第一个串和第二个串考虑的位置 dp[i][j]:=第一串考虑[0..i],第二串考虑[0..j]时,原问题的解 较大规模的子问题只与常数个较小规模的子问题有关,其中较小规模可能是 i 更小,或者是 j 更小,也可以是 i,j 同时变小。 其中一种最常见的状态转移形式:推导 dp[i][j] 时,dp[i][j] 仅与 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 线性动态规划中双串 dp[i][j] 的问题,状态的推导方向以及推导公式如下 如图所示,绿色部分的 dp[i-1 ~ 0][j-1 ~ 0] 均已经计算过,但计算橙色的当前状态时,仅用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1],即比 i, j 小的 O(1)O(1) 个子问题。 这种形式的线性 DP 的代码常见写法 for i = 1..m for j = 1..n dp[i][j] = f(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) 时间复杂度 O(mn)O(mn),空间复杂度 O(mn)O(mn) 以上是 O(1)O(1) 转移的情况,即计算 dp[i][j] 时,虽然绿色部分的子问题均已经计算完,但只需要用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]。也可能出现更高复杂度的转移,类似单串中依赖比 i 小的 O(n)O(n) 个子问题的情况。 经典问题:最长公共子序列 给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。 思路 单个数组或者字符串要用动态规划时,可以把动态规划 dp[i] 定义为 nums[0:i] 中想要求的结果;当两个数组或者字符串要用动态规划时,可以把动态规划定义成两维的 dp[i][j] ,其含义是在 A[0:i] 与 B[0:j] 之间匹配得到的想要的结果。 状态定义 可以定义 dp[i][j] 表示 text1[0:i-1] 和 text2[0:j-1] 的最长公共子序列。 (注: text1[0:i-1] 表示的是 text1 的 第 0 个元素到第 i - 1 个元素,两端都包含) 之所以 dp[i][j] 的定义不是 text1[0:i] 和 text2[0:j] ,是为了方便当 i = 0 或者 j = 0 的时候, dp[i][j] 表示的为空字符串和另外一个字符串的匹配,这样 dp[i][j] 可以初始化为 0。 状态转移 当 text1[i - 1] == text2[j - 1] 时,说明两个子字符串的最后一位相等,所以最长公共子序列又增加了 1,所以 dp[i][j] = dp[i - 1][j - 1] + 1;举个例子,比如对于 ac 和 bc 而言,他们的最长公共子序列的长度等于 a 和 b 的最长公共子序列长度 0 + 1 = 1。 当 text1[i - 1] != text2[j - 1] 时,说明两个子字符串的最后一位不相等,那么此时的状态 dp[i][j] 应该是 dp[i - 1][j] 和 dp[i][j - 1] 的最大值。举个例子,比如对于 ace 和 bc 而言,他们的最长公共子序列的长度等于 ① ace 和 b 的最长公共子序列长度0 与 ② ac 和 bc 的最长公共子序列长度1 的最大值,即 1。 综上状态转移方程为: dp[i][j] = 1. dp[i-1][j-1] + 1 (text1[i] == text2[j]) 2. max(dp[i][j-1], dp[i-1][j]) (text1[i] != text2[j]) 状态初始化 初始化就是要看当 i = 0 与 j = 0 时, dp[i][j] 应该取值为多少。 当 i = 0 时, dp[0][j] 表示的是 text1text1 中取空字符串 跟 text2 的最长公共子序列,结果肯定为 0。 当 j = 0 时, dp[i][0] 表示的是 text2text2 中取空字符串 跟 text1 的最长公共子序列,结果肯定为 0。 综上,当 i = 0 或者 j = 0 时, dp[i][j] 初始化为 0。 经典问题:最长重复子数组 给两个整数数组 A 和 B ,返回两个数组中公共的、长度最长的子数组的长度。 思路 区分两个概念: 子序列可以是不连续的 子数组(子字符串)需要是连续的 状态定义 定义 dp[i][j] 为以 nums1[i - 1] 和 nums2[j - 1] 为末尾项的公共子数组的长度。 状态转移 当 nums1[i - 1] == nums2[j - 1] 时,以 nums1[i - 1] 和 nums2[j - 1] 为末尾项的公共子数组 dp[i][j] 的长度保底为1,要考虑它俩的前缀数组 dp[i - 1][j - 1] 能为它俩提供多大的公共长度。 当 nums1[i - 1] != nums2[j - 1] 时,以 nums1[i - 1] 和 nums2[j - 1] 为末尾项的公共子数组 dp[i][j] 的长度为0。 综上状态转移方程为: dp[i][j] = 1. dp[i-1][j-1] + 1 (nums1[i] == nums2[j]) 2. 0 (nums1[i] != nums2[j]) 经典问题:编辑距离 给你两个单词 word1 和 word2,请你计算出将 word1 转换成 word2 所使用的最少操作数 。 你可以对一个单词进行如下三种操作: 插入一个字符 删除一个字符 替换一个字符 思路 我们可以对任意一个单词进行三种操作: 插入一个字符 删除一个字符 替换一个字符 题目给定了两个单词,设为 A 和 B,这样我们就能够六种操作方法(插入A、插入B、删除A、删除B、替换A、替换B)。 但可以发现: 对单词 A 删除一个字符和对单词 B 插入一个字符是等价的。例如当单词 A 为 doge,单词 B 为 dog 时,既可以删除单词 A 的最后一个字符 e,得到相同的 dog,也可以在单词 B 末尾添加一个字符 e,得到相同的 doge 对单词 B 删除一个字符和对单词 A 插入一个字符也是等价的 对单词 A 替换一个字符和对单词 B 替换一个字符是等价的。例如当单词 A 为 bat,单词 B 为 cat 时,修改单词 A 的第一个字母 b -> c,和修改单词 B 的第一个字母 c -> b 是等价的。 这样以来,本质不同的操作实际上只有三种: 在单词 A 中插入一个字符 在单词 B 中插入一个字符 修改单词 A 的一个字符 状态定义 定义 dp[i][j] 为word1 中前 i 个字符,变换到 word2 中前 j 个字符,最短需要操作的次数。 需要考虑 word1 或 word2 一个字母都没有,即全增加or全删除的情况,所以预留 dp[0][j] 和 dp[i][0] 。 状态转移 D[i][j-1] 为 word1 的前 i 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符,我们在 word1 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i][j-1] + 1 D[i-1][j] 为word1 的前 i - 1 个字符和 word2 的前 j 个字符编辑距离的子问题。即对于 word1 的第 i 个字符,我们在 word2 的末尾添加了一个相同的字符,那么 D[i][j] 最小可以为 D[i-1][j] + 1 D[i-1][j-1] 为 word1 前 i - 1 个字符和 word2 的前 j - 1 个字符编辑距离的子问题。即对于 word2 的第 j 个字符,我们修改 word1 的第 i 个字符使它们相同,那么 D[i][j] 最小可以为 D[i-1][j-1] + 1。特别地,如果 word1 的第 i 个字符和 word2 的第 j 个字符原本就相同,那么我们实际上不需要进行修改操作。在这种情况下, D[i][j] 最小可以为 D[i-1][j-1] 综上状态转移方程为: dp[i][j] = 1. min(dp[i][j−1] + 1, dp[i−1][j] + 1, dp[i−1][j−1]) (word1[i - 1] == word2[j - 1]) 2. min(dpi][j−1], dp[i−1][j], dp[i−1][j−1]) + 1 (word1[i - 1] != word2[j - 1]) 总结 动态规划中最重要的三个概念:最优子结构,重复子问题,无后效性。 最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构。 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。 重复子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)
    更多知识请点击:http://www.pclrj.com
我要咨询做网站
成功案例
建站流程
  • 网站需
    求分析
  • 网站策
    划方案
  • 页面风
    格设计
  • 程序设
    计研发
  • 资料录
    入优化
  • 确认交
    付使用
  • 后续跟
    踪服务
  • 134-074848-38
    13407484838
Hi,Are you ready?
准备好开始了吗?
那就与我们取得联系吧

咨询送礼现在提交,将获得某某网络策划专家免费为您制作
价值5880元《全网营销方案+优化视频教程》一份!
下单送礼感恩七周年,新老用户下单即送创业型空间+域名等大礼
24小时免费咨询热线134-074848-38
合作意向表
您需要的服务
您最关注的地方
预算
  • 看不清?点击更换

直接咨询