动态规划精讲（一）A单串

单串

单串 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(1)，例如上面提到的 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] 有关。这个例子是一种数据结构前缀和的状态计算方式，关于前缀和的详细内容请参考下一章。

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) 个子问题
53. 最大子数组和
给定一个整数数组 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] 的问题，状态的推导方向，以及推导公式如下

dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])

在本题中，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) 个子问题
300. 最长上升子序列
给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入是一个单串，首先思考单串问题中设计状态 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] 均可能需要用上，即，因此计算当前的橙色状态时，绿色部分此前计算过的状态都可能需要用上。

单串相关练习题
最经典单串 LIS 系列
最大子数组和系列
打家劫舍系列
变形：需要两个位置的情况
与其它算法配合
其它单串 dp[i] 问题
带维度单串 dp[i][k]
股票系列

巴特西

动态规划精讲（一）A单串

单串

最新文章

热门文章