线性 DP | 彩潭有鲤的札记

type

status

date

slug

summary

单串线性DP

单串线性DP问题：问题的输入为单个数组或单个字符串的线性 DP 问题。状态一般可定义为，表示为：

以数组中第个位置元素为结尾的子数组（）的相关解

以数组中第个位置元素为结尾的子数组（）的相关解

以数组中前个元素为子数组（）的相关解

这种状态的定义区别在于相差一个元素。

第种状态：子数组的长度为，子数组长度不可为空；

第种状态、第种状态：这两种状态描述是相同的。子数组的长度为，子数组长度可为空。在时，方便用于表示空数组（以数组中前个元素为子数组）。

正则表达式匹配

题目：给一个字符串s和一个字符规律p，请实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符

'*' 匹配零个或多个前面的那一个元素

所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

示例：

假设dp[i][j]表示s的前i个字符和p的前j个字符是否匹配，其中s和p的下标从0开始。那么可以分为以下几种情况：

如果p[j-1]是普通字符，那么只有当s[i-1]和p[j-1]相同，且s的前i-1个字符和p的前j-1个字符是匹配的，才有dp[i][j]=True。

如果p[j-1]是'.'，那么可以匹配任意字符，因此只有当s的前i-1个字符和p的前j-1个字符是匹配的，才有dp[i][j]=True。

如果p[j-1]是'*'，那么可以匹配零个或多个前面的那一个元素。因此需要考虑以下两种情况：

匹配零个前面的元素。此时dp[i][j]=dp[i][j-2]，表示s的前i个字符和p的前j-2个字符是匹配的。
匹配多个前面的元素。此时需要满足以下两个条件：

s[i-1]和p[j-2]相同或者p[j-2]是'.'，表示前面的元素可以匹配s[i-1]
s的前i-1个字符和p的前j个字符是匹配的，即dp[i-1][j]=True

通配符匹配

题目：给一个输入字符串 (s) 和一个字符模式 (p) ，请实现一个支持 '?' 和 '*' 匹配规则的通配符匹配：

'?' 可以匹配任何单个字符。

'*' 可以匹配任意字符序列（包括空字符序列）。

判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。

示例：

三角形最小路径和

题目：

给定一个三角形 triangle ，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1 。

示例：

用表示从三角形顶部走到位置的最小路径和。这里的位置指的是三角形中第行第列（均从开始编号）的位置。

由于每一步只能移动到下一行「相邻的节点」上，因此要想走到位置，上一步就只能在位置或者位置。在这两个位置中选择一个路径和较小的来进行转移，状态转移方程为：

其中表示位置对应的元素值。

注意第行有个元素，它们对应的的范围为 ]。当或时，上述状态转移方程中有一些项是没有意义的。例如当时，没有意义，因此状态转移方程为：

即当在第行的最左侧时，只能从第行的最左侧移动过来。当时，没有意义，因此状态转移方程为：

最长递增子序列

题目：给你一个整数数组nums ，找到其中最长严格递增子序列的长度。子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。

示例：

最长递增子序列有一个性质：最长递增子序列的尾巴元素一定是这个序列中最大的元素。如果已知一个递增序列和其尾巴元素，向它追加一个值更大的元素，构成的新的子序列也是递增序列。

构造一维数组，dp[i]为考虑前i个元素，以第i个数字结尾的最长上升子序列的长度，注意必须被选取。

假设对于所有小于i的 j，dp[j]是已计算过的。如果 A[i] > A[j]，则最长递增子序列得到扩展，dp[i]至少为dp[j]+1。

此时，dp[i]取所有 dp[j]+1的最大值即可：

如果遇到 A[i]<=A[j]，此时无法形成以元素A[i]结尾的递增子序列，因此不作考虑。

最后，整个数组的最长上升子序列即所有中的最大值。

最长递增子序列的个数

题目：给定一个未排序的整数数组 nums ，返回最长递增子序列的个数。注意这个数列必须是严格递增的。

示例：

定义表示以结尾的最长上升子序列的长度，表示以结尾的最长上升子序列的个数。设的最长上升子序列的长度为，那么答案为所有满足的所对应的之和。

从小到大计算数组的值，在计算之前，已经计算出的值，则状态转移方程为：

即考虑往中最长的上升子序列后面再加一个。由于代表中以结尾的最长上升子序列，所以如果能从这个状态转移过来，那么必然要大于，才能将放在后面以形成更长的上升子序列。

对于，其等于所有满足的之和。在代码实现时，可以在计算的同时统计的值。

最大子数组和

题目：给一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。子数组是数组中的一个连续部分

示例：

用f(i)代表以第i个数结尾的「连续子数组的最大和」，那么很显然要求的答案就是：

因此只需要求出每个位置的f(i)，然后返回f数组中的最大值即可。那么如何求f(i)呢？动态规划转移方程：

乘积最大子数组

题目：给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例：

首先来考虑数组全部都是大于0的场景：在这种场景下，因为元素都是正数，cur_max[i]=cur_max[i-1]*nums[i]

接下来再看下数组中含0的场景：这个时候，cur_max[2]=0，nums[3]=3，如果继续套用上面的公式算出cur_max[3]=cur_max[2]*nums[3]=0，显然这是不对的，正确的结果cur_max[3]=nums[3]=3。需要修改下上面的公式： cur_max[i]=max{cur_max[i-1]*nums[i], nums[i]}。

最后再来考虑下包含负数的场景：负数比较特殊，cur_max[2]=-1，但cur_max[3]!=max{cur_max[2]*nums[3], nums[3]}。这是因为负数的存在可能会导致最大值乘以负数变最小值，最小值乘以负数变最大值。针对这种情况增加一个数组cur_min[i]来表示以nums中第i个元素结尾子数组乘积最小的值。这个时候最终获得的状态转移公式如下。

cur_max[i]=max{cur_max[i-1]*nums[i], cur_min[i-1]*nums[i], nums[i]},   cur_min[i]=min{cur_max[i-1]*nums[i], cur_min[i-1]*nums[i], nums[i]}

。

买卖股票的最佳时机

题目：给定一个数组prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。只能选择某一天买入这只股票，并选择在未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例：

表示前天的最大利润，因为始终要使利润最大化，则：

打家劫舍

题目：你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。给定一个代表每个房屋存放金额的非负整数数组，计算不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例：

假设一共有个房子，每个房子的金额分别是，子问题表示从前个房子（即）中能偷到的最大金额。那么，偷个房子有两种偷法：

当时，没有房子，所以；当时，只有一个房子，偷这个房子即可，所以。

dp[k] 对应子问题f(k)，即偷前k间房子的最大金额。dp[k]依赖dp[k-1]和dp[k-2]

空间优化

打家劫舍 II

题目：你是一个专业的小偷，计划偷窃沿街的房屋，每间房内都藏有一定的现金。这个地方所有的房屋都 围成一圈 ，这意味着第一个房屋和最后一个房屋是紧挨着的。同时，相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警 。给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下 ，今晚能够偷窃到的最高金额。

示例：

以分成两种情况来讨论：

不偷窃最后一间房间，那么问题转化为偷窃1号到i - 1号房间所能获得的最高金额

不偷窃第一间房间，那么问题转化为偷窃2号到i号房间所能获得的最高金额

交错字符串

题目：给定三个字符串 s1、s2、s3，请帮忙验证 s3 是否是由 s1 和 s2 交错组成的。两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s1 + s2 + ... + sn

t = t1 + t2 + ... + tm

|n - m| <= 1

交错是 s1 + t1 + s2 + t2 + s3 + t3 + ... 或者 t1 + s1 + t2 + s2 + t3 + s3 + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例：

最长回文子序列

题目：给你一个字符串 s ，找出其中最长的回文子序列，并返回该序列的长度。子序列定义为：不改变剩余字符顺序的情况下，删除某些字符或者不删除任何字符形成的一个序列。

示例：

dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。

如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2;

如果s[i]与s[j]不相同，说明s[i]和s[j]的同时加入并不能增加[i,j]区间回文子串的长度，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。

加入s[j]的回文子序列长度为dp[i + 1][j]。加入s[i]的回文子序列长度为dp[i][j - 1]。

那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);

解码方法

题目：

一条包含字母 A-Z 的消息通过以下映射进行了编码：

要解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

"AAJF" ，将消息分组为 (1 1 10 6)

"KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给一个只含数字的非空字符串 s ，请计算并返回解码方法的总数。题目数据保证答案肯定是一个 32 位 的整数。

示例：

f[i]表示前i个数字一共有多少种解码方式，那么，f[n]就表示前n个数字一共有多少种不同的解码方式，即为答案。

设定字符串数组为s[](数组下标从1开始)，考虑最后一次解码方式，因此对于第i - 1和第i个数字，分为两种决策：

如果s[i]不为0，则可以单独解码s[i]，由于求的是方案数，如果确定了第i个数字的翻译方式，那么解码前i个数字和解码前i - 1个数的方案数就是相同的，即f[i] = f[i - 1]。(s[]数组下标从1开始)

将s[i]和s[i - 1]组合起来解码（组合的数字范围在10 ~ 26之间）。如果确定了第i个数和第i - 1个数的解码方式，那么解码前i个数字和解码前i - 2个数的方案数就是相同的，即f[i] = f[i - 2]。(s[]数组下标从1开始)

最后将两种决策的方案数加起来，因此，状态转移方程为： f[i] = f[i - 1] + f[i - 2]。

鸡蛋掉落

题目：给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。已知存在楼层 f ，满足 0 <= f <= n ，任何从高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？

示例：

双串线性DP

双串线性DP问题：问题的输入为两个数组或两个字符串的线性DP问题。状态一般可定义为，表示为：

「以第一个数组中第个位置元素为结尾的子数组（）」与「以第二个数组中第个位置元素为结尾的子数组（）」的相关解

「以第一个数组中第个位置元素为结尾的子数组（）」与「以第二个数组中第个位置元素为结尾的子数组（）」的相关解

「以第一个数组中前个元素为子数组（）」与「以第二个数组中前个元素为子数组（）」的相关解

这种状态的定义区别在于相差一个元素或

第种状态：子数组的长度为或，子数组长度不可为空

第种状态、第种状态：子数组的长度为或，子数组长度可为空。或时，方便用于表示空数组（以数组中前个元素为子数组）。

最大公共子序列

题目：给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。如果不存在公共子序列 ，返回0 。一个字符串的子序列是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。例如，"ace"是"abcde"的子序列，但"aec" 不是"abcde"的子序列。两个字符串的公共子序列是这两个字符串所共同拥有的子序列。

示例：

状态表示：定义 f[i][j]表示字符串text1的[1,i]区间和字符串text2的[1,j]区间的最长公共子序列长度（下标从1开始）

可以根据text1[i]和text2[j]的情况，分为两种决策：

若text1[i] == text2[j]，也就是说两个字符串的最后一位相等，那么问题就转化成了字符串text1的[1,j-1]区间和字符串text2的[1,j-1]区间的最长公共子序列长度再加上一，即f[i][j] = f[i - 1][j - 1] + 1。

若text1[i] != text2[j]，也就是说两个字符串的最后一位不相等，那么字符串text1的[1,i]区间和字符串text2的[1,j]区间的最长公共子序列长度无法延长，因此f[i][j]就会继承f[i-1][j]与f[i][j-1]中的较大值，即f[i][j] = max(f[i - 1][j],f[i][j - 1])

因此，状态转移方程为：

f[i][j] = f[i-1][j-1] + 1，当text1[i]==text2[j]

f[i][j] = max(f[i-1][j],f[i][j-1])，当text1[i]!=text2[j]

初始化：f[i][0]=f[0][j] = 0，(0<=i<=n, 0<=j<=m)

最大重复子数组

题目：给两个整数数组nums1和nums2，返回两个数组中公共的 、长度最长的子数组的长度

示例：

编辑距离

题目：给两个单词word1和word2，请返回将word1转换成word2所使用的最少操作数。可以对一个单词进行如下三种操作：插入一个字符、删除一个字符、替换一个字符

示例：

定义 dp[i][j]，代表 word1中前i个字符，变换到word2中前 j个字符，最短需要操作的次数。需要考虑word1或word2 一个字母都没有，即全增加/删除的情况，所以预留 dp[0][j]和dp[i][0]

状态转移

增dp[i][j] = dp[i][j-1] + 1

删dp[i][j] = dp[i-1][j] + 1

改dp[i][j] = dp[i-1][j-1] + 1

按顺序计算，当计算dp[i][j] 时，dp[i-1][j] ， dp[i][j-1] ， dp[i-1][j-1] 均已经确定了。配合增删改这三种操作，需要对应的 dp 把操作次数加一，取三种的最小。如果刚好这两个字母相同 word1[i-1] = word2[j-1] ，那么可以直接参考dp[i-1][j-1] ，操作不用加一。

矩阵线性DP

问题的输入为二维矩阵的线性 DP 问题。状态一般可定义为，表示为：从「位置」到达「位置」的相关解

最小路径和

题目：给定一个包含非负整数的mxn网格grid ，找出一条从左上角到右下角的路径，使得路径上的数字总和为最小，每次只能向下或者向右移动一步。

示例：

最大正方形

题目：在一个由 '0'和 '1'组成的二维矩阵内，找到只包含 '1'的最大正方形，并返回其面积

示例：

用表示以为右下角，且只包含1的正方形的边长最大值。只有当矩阵位置值为1时，才有可能存在正方形。如果矩阵位置上值为0，则。

如果矩阵位置上值为1，则的值由该位置上方、左侧、左上方三者共同约束的，为三者中最小值加1。即：

无串线性DP

问题的输入不是显式的数组或字符串，但依然可分解为若干子问题的线性 DP 问题。

整数拆分

题目：给定一个正整数n，将其拆分为k个正整数的和（ k>=2），并使这些整数的乘积最大化，返回可以获得的最大乘积。

示例：

创建数组，其中表示将正整数拆分成至少两个正整数的和之后，这些正整数的最大乘积。特别地，和都不能拆分，因此。

当时，假设对正整数拆分出的第一个正整数是，则有以下两种方案：

将拆分成和的和，且不再拆分成多个正整数，此时的乘积是

将拆分成和的和，且继续拆分成多个正整数，此时的乘积是

因此，当固定时，有。由于的取值范围是1到，需要遍历所有的得到的最大值，因此可以得到状态转移方程如下：