通知
关于网站更多信息请加whimurmur模板/jpress插件QQ群(1061691290)            jpress从3.x升级到4.x,显示有些问题,慢慢修复中

leetcode 动态规划精讲(一)线性动态规划

621人浏览 / 0人评论 / | 作者:whisper  | 分类: 动态规划  | 标签: leetcode  | 

作者:whisper

链接:https://www.proprogrammar.com/article/1015

声明:请尊重原作者的劳动,如需转载请注明出处


这一章将会介绍线性动态规划的相关概念和经典问题,并给出一些练习题供大家演练。

用动态规划解决问题的过程有以下几个关键点:状态定义,状态的转移,初始化和边界条件。

状态定义 就是定义子问题,如何表示目标规模的问题和更小规模的问题。例如常见的方法:定义状态 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] := 考虑[0..i]上,原问题的解,其中 i 位置的处理,根据不同的问题,主要有两种方式:

第一种是 i 位置必须取,此时状态可以进一步描述为 dp[i] := 考虑[0..i]上,且取 i,原问题的解;
第二种是 i 位置可以取可以不取
大部分的问题,对 i 位置的处理是第一种方式,例如力扣:

70 爬楼梯问题
801 使序列递增的最小交换次数
790 多米诺和托米诺平铺
746 使用最小花费爬楼梯
线性动态规划中单串 dp[i] 的问题,状态的推导方向以及推导公式如下

1. 依赖比 i 小的 O(1) 个子问题

dp[n] 只与常数个小规模子问题有关,状态的推导过程 dp[i] = f(dp[i - 1], dp[i - 2], ...)。时间复杂度 O(n)O(n),空间复杂度 O(n)O(n) 可以优化为 O(1)O(1),例如上面提到的 70, 801, 790, 746 都属于这类。

如图所示,虽然紫色部分的 dp[i-1], dp[i-2], ..., dp[0] 均已经计算过,但计算橙色的当前状态时,仅用到 dp[i-1],这属于比 i 小的 O(1)O(1) 个子问题。

例如,当 f(dp[i-1], ...) = dp[i-1] + nums[i] 时,当前状态 dp[i] 仅与 dp[i-1] 有关。这个例子是一种数据结构前缀和的状态计算方式,关于前缀和的详细内容请参考下一章。

2. 依赖比 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)O(n) 级的子问题数量。

例如:

  • 139 单词拆分
  • 818 赛车

以 min 函数为例,这种形式的问题的代码常见写法如下

for i = 1, ..., n
    for j = 1, ..., i-1
        dp[i] = min(dp[i], f(dp[j])

时间复杂度 O(n^2),空间复杂度 O(n)

单串 dp[i] 经典问题

以下内容将涉及到的知识点对应的典型问题进行讲解,题目和解法具有代表性,可以从一个问题推广到一类问题。

1. 依赖比 i 小的 O(1) 个子问题

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。

一个数组有很多个子数组,求哪个子数组的和最大。可以按照子数组的最后一个元素来分子问题,确定子问题后设计状态

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)

这个是单串 dp[i] 的问题,状态的推导方向,以及推导公式如下

在本题中,f(dp[i-1], ..., dp[0]) 即为 max(dp[i-1], 0) + nums[i],dp[i] 仅与 dp[i-1] 1 个子问题有关。因此虽然紫色部分的子问题已经计算完,但是推导当前的橙色状态时,只需要 dp[i-1] 这一个历史状态。

2. 依赖比 i 小的 O(n) 个子问题

给定一个无序的整数数组,找到其中最长上升子序列的长度。

输入是一个单串,首先思考单串问题中设计状态 dp[i] 时拆分子问题的方式:枚举子串或子序列的结尾元素来拆分子问题,设计状态 dp[i] := 在子数组 [0..i] 上,且选了 nums[i] 时,的最长上升子序列。

因为子序列需要上升,因此以 i 结尾的子序列中,nums[i] 之前的数字一定要比 nums[i] 小才行,因此目标就是先找到以此前比 nums[i] 小的各个元素,然后每个所选元素对应一个以它们结尾的最长子序列,从这些子序列中选择最长的,其长度加 1 就是当前的问题的结果。如果此前没有比 nums[i] 小的数字,则当前问题的结果就是 1 。

按照以上的分析,状态的转移方程可以写出来,如下

本题依然是单串 dp[i] 的问题,状态的推导方向,以及推导公式与上一题的图示相同,

状态的推导依然是按照 i 从 0 到 n-1 推的,计算 dp[i] 时,dp[i-1], dp[i-2], ..., dp[0] 依然已经计算完。

但本题与上一题的区别是推导 dp[i] 时,dp[i-1]. dp[i-2], ..., dp[0] 均可能需要用上,即,因此计算当前的橙色状态时,紫色部分此前计算过的状态都可能需要用上。

单串相关练习题

  1. 最经典单串 LIS 系列
  2. 最大子数组和系列
  3. 打家劫舍系列
  4. 变形:需要两个位置的情况
  5. 与其它算法配合
  6. 其它单串 dp[i] 问题
  7. 带维度单串 dp[i][k]
  8. 股票系列

单串问题:最经典单串 LIS 系列

LIS 是单串上最经典的问题,它的状态设计是单串动态规划最经典的状态设计。很多单串的题目。状态设计都是启发自这道题的设计,因此需要专门练习,加深印象。

最长上升子序列
最长递增子序列的个数
俄罗斯套娃信封问题 —— LIS

单串问题:最大子数组和系列

从动态规划角度讲,最大子数组和是以一类较简单的 DP 问题,但它的状态设计比较经典,同时也是很多问题的基础组件,需要专门掌握。

最大子序和
乘积最大子数组
环形子数组的最大和 —— 环形数组的处理
最大子矩阵 —— 思路类似一维的最大子数组和
矩形区域不超过 K 的最大数值和 —— 在上一题基础上加了一个 K

单串问题:打家劫舍系列

打家劫舍主要是不相邻子序列的最大和问题,以及若干变形

  • 打家劫舍
  • 打家劫舍 II
  • 删除与获得点数
  • 3n 块披萨

单串问题:变形,需要两个位置的情况: dp[i][j] 以 j, i 结尾

 有一些单串问题在涉及状态时需要考虑最后两位的情况,因为只考虑最后一个的话无法对状态描述清楚,例如下面两道题。

  • 最长的斐波那契子序列的长度 —— dp[i][j]:= 以 j, i 结尾,转移时在 [0..j] 中找满足条件的 k 这一步可以二分或哈希表
  • 最长等差数列 —— dp[i][j]:= 以 j, i 结尾,转移时在 [0..j] 中找满足条件的 k 这一步用哈希表,键为数组值,值为保存下标的平衡树

单串问题:与其它算法配合

线性动态规划经常要与其它算法和数据结构配合来解决问题,例如二分,贪心,排序的等。

  • 形成字符串的最短路径 —— DP + 二分,贪心
  • 最大整除子集 —— 先对数组排序

单串问题:其它单串 dp[i] 问题

除以上提到的类型外 线性 DP 还有一些问题没有显式的数组,字符串等。此类问题一般没有什么固定的模式,需要通过多做题来积累。

  • 最长有效括号
  • 等差数列划分
  • 解码方法
  • 分割回文串 II
  • 比特位计数
  • 使序列递增的最小交换次数
  • 最低加油次数
  • 两个字符串的删除操作

带维度单串 dp[i][k]

单串的问题,子问题仅与位置 i 有关时,就形成单串 dp[i] 的问题。在此基础上,如果子问题还与某种指标 k 有关,k 的物理意义比较常见的有长度,个数,次数,颜色等,则是另一大类问题,状态通常写成 dp[i][k]。其中 k 上可能有二分,贪心等算法.

当 i 变小时,形成小规模子问题,当 k 变小时,也形成小规模子问题,因此推导 dp[i][k] 时,i 和 k 两个维度分别是一个独立的单串 dp[i] 问题。推导 k 时,k 可能与 k - 1,...,1 中的所有小规模问题有关,也可能只与其中常数个有关,参考单串 dp[i] 问题中的两种情况。

例如 256. 粉刷房子 ,其中 k 这一维度的物理意义是颜色推导 k 时,k 与 k - 1,...,1 中的所有小规模问题有关,则 k 这一维度的时间复杂度为 O(K^2)

单串 dp[i][k] 的问题,推导状态时可以先枚举 k,再枚举 i,对于固定的 k,求 dp[i][k] 相当于就是在求一个单串 dp[i] 的问题,但是计算 dp[i][k] 时可能会需要 k-1 时的状态。具体的转移需要根据题目条件确定。参考 813。

矩阵上的 dp[i][j] 这类问题中也有可能会多出 k 这个维度,状态的定义就是 dp[i][j][k],例如

  • 576 出界的路径数
  • 688 “马”在棋盘上的概率

单串 dp[i][k] 经典问题

以下将涉及到的知识点对应的典型问题进行讲解,题目和解法具有代表性,可以从一个问题推广到一类问题。

我们将给定的数组 A 分成 K 个相邻的非空子数组 ,我们的分数由每个子数组内的平均值的总和构成。计算我们所能得到的最大分数是多少。

注意我们必须使用 A 数组中的每一个数进行分组,并且分数不一定需要是整数。

输入是单串,但是有一个额外的次数的指标 k。在这种情况下,第一步是考虑单串 dp[i] 的子问题拆分方式:枚举子数组的起点来拆分子问题。

设计状态 dp[i] := [i..n-1] 上原问题的解,即 [i..n-1] 上分成 K 个相邻的非空子数组可得的最大分数

第二步是将额外的指标 K 作为一个维度加到状态里 dp[i][k] := [i..n-1] 上原问题的解,即 [i..n-1] 上分成 k 个相邻的非空子数组可得的最大分数

在推导状态时,先枚举 k,对于固定的 k,枚举 i ,枚举 i 时,相当于是在推导一个单串 dp[i] 的问题,但是计算 dp[i][k] 时需要用到 k-1 时的状态,这个区别在 $2-1-4 中也有讨论。

由于 i 枚举的是起点,因此 i 越小的时候,子问题规模越大,需要从 n-1 到 0 枚举。

上面提到,固定 k 时,枚举 i ,相当于是在推导一个单串 dp[i] 的问题,这个问题在计算 i 的时候,需要此前已经计算的所有状态,即 i+1, i+2, ..., n-1。这相当于 $2-1-1 中的第二种情况,但区别是这里有 k 这一个额外指标影响状态的推导。

对于区间 [i..n-1],若分出了区间 [i,j-1], 则在区间 [j..n-1] 上分 k - 1 个区间,就可以将 [i..n-1] 分成 k 个区间。而 [i+1, .., n-1] 均有可能是这个 j。因此枚举这些 j ,将 [j, n-1] 上分 k-1 份的结果 dp[j][k-1] 加上 [i..j-1] 上的平均追 avg(i, j-1)avg(i,j−1) 就得到了当前待计算状态 dp[i][k]。

结合题目条件,这个单串 dp[i][k] 的问题,状态的推导方向,以及推导公式如下:

按照以上的分析,状态的转移方程可以写出来,如下:

其中 avg(i, j),是求子串 (i, j) 上的平均值,其中中间的一步求 sum(i, j),可以用前缀和实现。前缀和的内容参考下一章。

单串问题:带维度单串 dp[i][k],i 为位置,k 为附加的维度

在单串问题中,可能仅用一个维度表示当前子问题是考虑到串上的哪个位置是不够的,需要增加维度,通常用 k 表示,k 随着题目的不同,可以表示长度,个数,次数,颜色等,同时 k 这个维度的枚举和转移可能涉及到二分,贪心等算法。这是线性而动态规划比较难的部分。

  • 最大平均值和的分组 —— k 是个数
  • 鸡蛋掉落 —— k 是次数,k 上有二分
  • 粉刷房子 —— k 是颜色
  • 粉刷房子 II —— k 是颜色
  • 奇偶跳 —— k 表示当前的奇偶状态
  • 青蛙过河 —— k 表示上一步的跳的步数
  • 安排邮筒 —— k 是个数,前缀和维护状态转移时的查询
  • 抛掷硬币 —— k 是个数
  • 分割数组的最大值 —— k 是份数
  • 给房子涂色 III —— 有两个指标 k 颜色;t 街区数

单串问题:股票系列: dp[i][k][state] i 是时间,k 是次数,state 是状态

股票系列问题是 dp[i][k] 这种状态设计模式的经典问题。

  • 买卖股票的最佳时机
  • 买卖股票的最佳时机 II
  • 买卖股票的最佳时机 III
  • 买卖股票的最佳时机 IV
  • 最佳买卖股票时机含冷冻期
  • 买卖股票的最佳时机含手续费

双串

有两个输入从串,长度分别为 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],例如

  • 72 编辑距离
  • 712 两个字符串的最小 ASCII 删除和

线性动态规划中双串 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)个子问题。

这种形式的线性 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(1) 转移的情况,即计算 dp[i][j] 时,虽然绿色部分的子问题均已经计算完,但只需要用到 dp[i-1][j], dp[i][j-1], dp[i-1][j-1]。也可能出现更高复杂度的转移,类似单串中依赖比 i 小的 O(n)O(n) 个子问题的情况。

双串 dp[i][j] 经典问题

以下将涉及到的知识点对应的典型问题进行讲解,题目和解法具有代表性,可以从一个问题推广到一类问题。

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

输入是双串,首先思考双串问题中设计状态 dp[i][j] 时拆分子问题的方式:枚举第一串的子序列的结尾和第二串的子序列的结尾来拆分子问题,设计状态 dp[i][j] := text1 考虑 [0..i], text2 考虑 [0..j] 时,原问题的解,即 LCS 长度

这个是单串 dp[i][j] 的问题,状态的推导方向,以及推导公式如下

状态的推导是按照 i 从 0 到 n - 1、j 从 0 到 m - 1 顺序推的,推到 dp[i][j] 时,dp[i - 1 .. 0][j - 1 .. 0] 均已经计算完。

因为两个子序列需要相同,若两个串的末尾元素相同,则可以选择 text1[i] 和 text2[j],此时再根据此前已经 text1[0..i-1] 和 text[0..j-1] 的 LCS 长度。若两个串的末尾元素不同,则 text1[i] 和 text2[j] 中只能选一个,

  • 若选了 text1[i],则 text2 只能取到 j-1,此时 dp[i-1][j] 的结果就是当前状态 dp[i][j] 的结果。
  • 若选了 text2[j],则 text1 只能取到 i-1,此时 dp[i][j-1] 的结果就是当前状态 dp[i][j] 的结果。

两个结果要取一个最长的。

按照以上的分析,状态的转移方程可以写出来,如下

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])
两者取较大值

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

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

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

输入是双串,首先思考双串问题中设计状态 dp[i][j] 时拆分子问题的方式:枚举第一串的子序列的结尾和第二串的子序列的结尾来拆分子问题,设计状态 dp[i][j] := word1 考虑 [0..i], word2 考虑 [0..j] 时,原问题的解,即 word1 转换成 word2 的最少操作数

这个是单串 dp[i][j] 的问题,状态的推导方向,以及推导公式与上一题的图示相同

同样地,状态的推导是按照 i 从 0 到 n - 1、j 从 0 到 m - 1 顺序推的,推到 dp[i][j] 时,dp[i - 1 .. 0][j - 1 .. 0] 均已经计算完。

因为操作之后两个 word 需要相同,如果两个串的末尾元素 word1[i] 和 word2[j] 不相同,则可以在 word1 的末尾元素上使用插入,删除,替>换这三种操作,操作数都要 + 1,如果两个串的末尾元素 word1[i] 和 word2[j] 相同,依然可以在 word1 的末尾元素上使用插入,删除,替换这三种操作,但是此时如果使用改,则操作数不 +1,因为两个末尾元素已经相等了。

按照以上的分析,状态的转移方程可以写出来,如下

dp[i][j] =
1. dp[i][j-1] + 1  (最后一步是插入)
2. dp[i-1][j] + 1  (最后一步是删)
3. dp[i-1][j-1] + 1  (最后一步是改,且 word1[i] != word2[j])
4. dp[i-1][j-1]  (最后一步是改,且 word1[i] == word2[j])
取较小值

双串相关练习题

  1. 最经典双串 LCS 系列
  2. 字符串匹配系列
  3. 其它双串 dp[i][j] 问题
  4. 带维度双串 dp[i][j][k]

双串问题:最经典双串 LCS 系列

最长公共子序列是双串的最经典的问题,很多双串问题的状态设计都是启发自这到底。

  • 最长公共子序列
  • 两个字符串的最小 ASCII 删除和 —— LCS,len 和 ascii 各一个 dp
  • 最长重复子数组 —— 最长公共子串,注意与最长公共子序列的区别

双串问题:字符串匹配系列

双串的问题一般是给定两个字符串,或者两个数组。这种情况的状态设计一般都会首先考虑如下的状态设计,这也是最长公共子序列问题启发我们的。

dp[i][j] := 第一串考虑到 i, 第二船考虑得到 j ,原问题的解。

有了这种状态设计方法,我们立刻就可以解决一些初看比较难的字符串的模糊匹配的问题

  • 编辑距离
  • 通配符匹配
  • 正则表达式匹配

双串问题:其它双串 dp[i][j] 问题

以下两道题较难,但仍然用到了前面的状态设计方法。

  • 交错字符串
  • 不同的子序列

双串问题:带维度双串 dp[i][j][k]

在双串的场景下,依然可能会有额外的维度需要插入,例如下面这一题

  • 扰乱字符串

矩阵

输入是一个矩阵,宽和高分别为 m, n,用两个维度表示问题规模 dp[i][j]:=第一维度考虑[0..i], 第二维度考虑[0..j],原问题的解

这样的状态定义,i 减小,j 减小均可以得到小规模子问题,两个维度均从小到大按顺序推,单独看各自维度,均是一个类似 上 的单串 dp[i] 问题,同样有单串中的两种情况,即转移时要考虑 O(1) 个小规模子问题,和转移时要考虑 O(n) 个子问题。

两个维度均只需考虑 O(1)个子问题是最简单的情况,一般 dp[i][j] 就只与 dp[i-1][j], dp[i][j-1], dp[i-1][j-1] 有关,例如 64,但是也有可能出现需要其它位置的状态的情况,需要结合题目分析,这里分析的计算 dp[i][j] 需要哪些状态,决定了状态推导的方向。

线性动态规划中矩阵 dp[i][j] 的问题,状态的推导方向以及推导公式与双串 dp[i][j] 相同,但是物理意义不一样,且求 dp[i][j] 时所需的子问题的变化相对更多。

矩阵 dp[i][j] 经典问题

以下将涉及到的知识点对应的典型问题进行讲解,题目和解法具有代表性,可以从一个问题推广到一类问题。

给定一个包含非负整数的 m x n 网格,请找出一条从左上角到右下角的路径,使得路径上的数字总和为最小。

输入是矩阵,首先思考矩阵问题中设计状态 dp[i][j] 时拆分子问题的方式:枚举右下角的点的子序列的结尾和第二串的子序列的结尾来拆分子问题,设计状态 dp[i][j] := 从 (0,0) 走到 (i,j),原问题的解,即 (0,0) 走到 (i,j) 最小的路径和

这个是单串 dp[i][j] 的问题,状态的推导方向,以及推导公式与上一题的图示相同,状态的推导是按照 i 从 0 到 n - 1、j 从 0 到 m - 1 顺序推的,推到 dp[i][j] 时,dp[i - 1 .. 0][j - 1 .. 0] 均已经计算完。

因为行走的路线只能向左或向下,因此计算 dp[i][j] 时只需要 dp[i-1][j] 和 dp[i][j-1] 的状态。当前位置可能从上面走来,此时就取 dp[i-1][j] 加上当前点的值 nums[i][j],当前位置也可能从左边走来,此时就取 dp[i][j-1] 加上当前点的值 nums[i][j]。除了这两种情况,没有其它情况可以到达当前点 (i, j) 了。

按照以上的分析,状态的转移方程可以写出来,如下

dp[i][j] =
1. dp[i-1][j] + nums[i][j]  (从上边走来)
2. dp[i][j-1] + nums[i][j]  (从左边走来)
取较小值

矩阵相关练习题

  1. 矩阵 dp[i][j]
  2. 矩阵 dp[i][j][k]

矩阵问题:矩阵 dp[i][j]

除了数组和字符串外,矩阵也是一种线性结构,很多一维数组或字符串的问题可以推广到二维,因此矩阵上也有一些经典的动态规划问题,矩阵上的动态规划问题,基本的状态设计就是用两维变量 (i, j) 共同表示以 (0, 0) 为左上角,(i, j) 为右下角的子问题。

  • 三角形最小路径和
  • 最小路径和
  • 地下城游戏
  • 下降路径最小和
  • 最大正方形
  • 下降路径最小和 II

矩阵问题:矩阵 dp[i][j][k]

与一维的情况一样,矩阵上也有问题仅仅用 (i, j) 表示子问题边界点的位置是不够的,需要增加维度 k,其中随着题目不同 k 可能是次数,长度等指标

  • 最大矩形
  • 矩形区域不超过 K 的最大数值和 —— k 为宽度
  • 最大子矩阵 —— 思路类似一维的最大子数组和
  • 切披萨的方案数 —— 需要二维前缀和判断两个状态之间能否转移

无串线性问题

线性动态规划有一类问题是没有显式的数组或字符串的。但在计算中依然可以分成若干子问题,且有动态规划的三条性质。因此也可以用动态规划来解。

  • 只有两个键的键盘
  • 丑数 II
  • 完全平方数
  • 整数拆分

总结

线性动态规划是动态规划中最基础的一类,它的状态一般物理意义很明确,易于分析。在初学动态规划时,通过线性动态规划的大量练习,可以不断加深动态规划的概念理解,例如动态规划中最重要的三个概念:最优子结构,重复子问题,无后效性。下面对动态规划的三个基本概念做个简要回顾,在线性动态规划的题目练习中可以不断地加深理解,之后再学习其它的动态规划类型就会容易很多。

  1. 最优子结构:如果问题的最优解所包含的子问题的解也是最优的,就称该问题具有最优子结构。
  2. 无后效性:即某阶段状态一旦确定,就不受这个状态以后决策的影响。也就是说,某状态以后的过程不会影响以前的状态,只与当前状态有关。
  3. 重复子问题:即子问题之间是不独立的,一个子问题在下一阶段决策中可能被多次使用到。(该性质并不是动态规划适用的必要条件,但是如果没有这条性质,动态规划算法同其他算法相比就不具备优势)

线性动态规划是动态规划中变化最多的一类。

首先线性动态规划针对的问题是最常见的数组,字符串,矩阵等,这三种数据结构本身就是线性的,因此出现这些类型的输入的时候,如果要用到动态规划,首先考虑线性动态规划就很合理了,因此很多问题不论最后正解是不是线性动态规划,都会首先想一下线性动态规划是否可行。

其次由于大部分问题的数据都是以这三种形式给出的,因此题目的变化会非常多,很多常见的输入形式以及问题都非常经典,都存在经典的状态设计。因此不考虑一些比较 Trick 的解法,仅仅是经典问题的经典状态设计,就比其它种类的动态规划问题多很多了。

例如单个数组或字符串上设计一维状态,两个数组或字符串上设计两维状态,以及矩阵上设计两维状态等等,同时以上三种情况的状态设计都有可能再加上额外的指标的状态,就是前面例题中的 k,这里面变化就很多了,比如有的题目在 k 这一维上要使用二分,贪心的策略,有的题目需要 DP 状态与数据结构配合来解决问题。

除此之外还有一类问题没有显式的数组,字符串,但是在求解的时候依然满足前面提到的动态规划三条基本概念,可以用动态规划求解,这种问题通常也是线性动态规划。如此多的变化仅仅本小节例举的题目是远远不够的,下一小节是线性动态规划的练习题,涉及到对线性动态规划的更多的变化。


亲爱的读者:有时间可以点赞评论一下

点赞(1) 打赏

全部评论

还没有评论!
广告位-帮帮忙点下广告