线性动态规划
线性动态规划的主要特点是状态的推导是按照问题规模 i 从小到大依次推过去的,较大规模的问题的解依赖较小规模的问题的解。
dp[n] := [0..n] 上问题的解
状态转移:
dp[n] = f(dp[n-1], ..., dp[0])
大规模问题的状态只与较小规模的问题有关,而问题规模完全用一个变量 i 表示,i 的大小表示了问题规模的大小,因此从小到大推 i 直至推到 n,就得到了大规模问题的解,这就是线性动态规划的过程。
按照问题的输入格式,线性动态规划解决的问题主要是单串,双串,矩阵上的问题,因为在单串,双串,矩阵上问题规模可以完全用位置表示,并且位置的大小就是问题规模的大小。因此从前往后推位置就相当于从小到大推问题规模。
线性动态规划是动态规划中最基本的一类。问题的形式、dp 状态和方程的设计、以及与其它算法的结合上面变化很多。按照 dp 方程中各个维度的含义,可以大致总结出几个主流的问题类型,除此之外还有很多没有总结进来的变种问题,小众问题,和困难问题,这些问题的解法更多地需要结合自己的做题经验去积累,除此之外,常见的,主流的问题和解法都可以总结成下面的四个小类别。
单串
依赖比 i 小的 O (1) 个子问题
单串 dp [i]
线性动态规划最简单的一类问题,输入是一个串,状态一般定义为 dp[i] := 考虑 [0..i]
上,原问题的解,其中 i 位置的处理,根据不同的问题,主要有两种方式:
第一种是 i 位置必须取,此时状态可以进一步描述为 dp[i] := 考虑 [0..i] 上
,且取 i,原问题的解;
第二种是 i 位置可以取可以不取
dp[i] = f(dp[i - 1], dp[i - 2], ...)。
dp[n] 只与常数个小规模子问题有关,状态的推导过程.时间复杂度 O(n),空间复杂度 O(n) 可以优化为 O(1),例如上面提到的 70, 801, 790, 746 都属于这类。
依赖比 i 小的 O (n) 个子问题
dp[i] = f(dp[i - 1], dp[i - 2], ..., dp[0])
因此在计算
dp[i]
时需要将它们遍历一遍完成计算。f 常见的有 max/min,可能还会对 i-1,i-2,…,0 有一些筛选条件,但推导dp[n]
时依然是O(n)
级的子问题数量。 以 min 函数为例,这种形式的问题的代码常见写法如下
for i = 1, ..., n
for j = 1, ..., i-1
dp[i] = min(dp[i], f(dp[j])
Kadane’s 模版
Kadane’s 算法(Kadane’s algorithm)是一种用于在数组中寻找最大子数组的算法,其时间复杂度为 O(n)。它的基本思想是维护两个变量:当前最大子数组和和当前最大子数组的右端点。
Kadane’s 算法的基本思路是,从数组的左端开始,累积地求和,并在每个位置记录到目前为止得到的最大和或者最小和。如果在某个位置,当前的累积和小于0,那么就放弃到目前为止的累积和,从下一个位置开始重新计算累积和。或者当前的累积和大于0,那么就放弃到目前为止的累积和,从下一个位置开始重新计算累积和 这是因为,一个负的累积和加上任何后续的正数,都不会使得和增大。或者一个正的累计和加上任何后面的都不会使得和变小。
其代码大概如下:
func maxSubarraySumCircular(A []int) int {
maxVal, minVal, sum, tempMax, tempMin := A[0], A[0], A[0], A[0], A[0]
for i := 1; i < len(A); i++ {
if tempMax >0{
tempMax = A[i]+tempMax
}else{
tempMax = A[i]
}
maxVal = max(maxVal,tempMax)
if tempMin<0{
tempMin = A[i]+tempMin
}else{
tempMin = A[i]
}
minVal = min(minVal,tempMin)
sum += A[i]
}
if sum == minVal { // 防止全部为负数的情况
return maxVal
}
return max(maxVal, sum-minVal)
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
func min(a int,b int)int{
if a<b{
return a
}
return b
}
Kadane的算法其实是动态规划(DP)的一个特例,DP的核心思想是将原问题分解为子问题,并保存子问题的答案,若下次再遇到相同的子问题,直接取出答案.
最大的子序列和
func maxSubArray(nums []int)int{
dp:=make([]int,len(nums))
dp[0]= nums[0]
rea:=-1<<31
for j:=1;j<len(nums);j++{
dp[j] = max(dp[j-1]+nums[j],nums[j])
res = max(res,dp[j])
}
return res
}
构成最大的子序列和的坐标范围
func maxSubArray(nums []int)[]int{
dp:=make([]int,len(nums))
dp[0]= nums[0]
rea:=[]int{}
for j:=1;j<len(nums);j++{
dp[j] = max(dp[j-1]+nums[j],nums[j])
res = max(res,dp[j])
}
return res
}
构成最大的子序列和的坐标范围
func maxSubArray(nums []int) (int, int, int) {
start:=0
end:=0
currentSum:=nums[0]
maxSum:=nums[0]
tempStart:=0
for i:=1;i<len(nums);i++{
if currentSum > 0{
currentSum = currentSum + nums[i]
}else{
currentSum = nums[i]
tempStart=i
}
if currentSum > maxSum {
maxSum = currentSum
start = tempStart
end = i
}
}
return []int{start,end}
}
并查集思想在动态规划中的运用
/*368. 最大整除子集
给一个由 无重复 正整数组成的集合 nums ,请找出并返回其中最大的整除子集 answer ,子集中每一元素对 (answer[i], answer[j]) 都应当满足:
answer[i] % answer[j] == 0 ,或
answer[j] % answer[i] == 0
如果存在多个有效解子集,返回其中任何一个均可*/
func largestDivisibleSubset(nums []int) []int {
sort.Ints(nums)
n := len(nums)
f := make([]int, n)
g := make([]int, n)
for i := 0; i < n; i++ {
// 至少包含自身一个数,因此起始长度为 1,由自身转移而来
length, prev := 1, i
for j := 0; j < i; j++ {
if nums[i]%nums[j] == 0 {
// 如果能接在更长的序列后面,则更新「最大长度」&「从何转移而来」
if f[j]+1 > length {
length = f[j] + 1
prev = j
}
}
}
// 记录「最终长度」&「从何转移而来」
f[i] = length
g[i] = prev
}
// 遍历所有的 f[i],取得「最大长度」和「对应下标」
maxLen := -1
idx := -1
for i := 0; i < n; i++ {
if f[i] > maxLen {
maxLen = f[i]
idx = i
}
}
// 使用 g[] 数组回溯出最长上升子序列
path := make([]int, 0)
for {
path = append(path, nums[idx])
if idx == g[idx] {
break
}
idx = g[idx]
}
return path
}
带维度的动态规划
package main
import (
"fmt"
"math"
)
func splitArray(nums []int, m int) int {
n := len(nums)
// 前缀和
sum := make([]int, n+1)
for i := 1; i <= n; i++ {
sum[i] = sum[i-1] + nums[i-1]
}
// 动态规划
dp := make([][]int, n+1)
for i := 0; i <= n; i++ {
dp[i] = make([]int, m+1)
for j := 0; j <= m; j++ {
dp[i][j] = math.MaxInt32
}
}
dp[0][0] = 0
for i := 1; i <= n; i++ {
for j := 1; j <= min(i, m); j++ {
for k := i; k >= j; k-- {
dp[i][j] = min(dp[i][j], max(dp[k-1][j-1], sum[i]-sum[k-1]))
}
}
}
return dp[n][m]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a, b int) int {
if a > b {
return a
}
return b
}
带维度的单串
这类问题通常涉及到两个维度,一个是字符串或数组的位置,另一个是额外的指标,如分组数量、颜色、次数等。状态转移通常涉及到当前状态与前一状态的关系,以及在当前状态下可以进行的操作。
以下是这类问题的一些常见特点和处理方法:
状态定义:通常会定义一个二维的动态规划数组dp[i][k]
,其中dp[i][k]
表示在前i个字符或元素中进行k次操作的某种关系。这种关系取决于具体的问题,可能是最大利润、最小花费等。
状态转移:状态dp[i][k]
的值通常会依赖于dp[i-1][k]
,dp[i][k-1]
,dp[i-1][k-1]
的值,以及在当前状态下可以进行的操作。具体的状态转移方程取决于具体的问题。
边界条件:当i=0或k=0时,dp[i][k]
通常会有特殊的定义,这代表没有字符或元素,或者不能进行操作。
遍历顺序:由于dp[i][k]
的值依赖于dp[i-1][k]
,dp[i][k-1]
和dp[i-1][k-1]
的值,所以在计算dp数组的时候,需要按照从左到右,从上到下的顺序进行遍历。
func solve(arr []int, K int) int {
n := len(arr)
dp := make([][]int, n+1)
for i := range dp {
dp[i] = make([]int, K+1)
}
// 初始化边界条件
for i := 0; i <= n; i++ {
dp[i][0] = ... // 根据具体问题来定义
}
for k := 0; k <= K; k++ {
dp[0][k] = ... // 根据具体问题来定义
}
// 状态转移
for i := 1; i <= n; i++ {
for k := 1; k <= K; k++ {
dp[i][k] = ... // 根据具体问题来定义
}
}
return dp[n][K]
}
双串
最经典双串 LCS 系列
双串线性动态规划问题是一类常见的动态规划问题,它涉及到两个输入字符串,并且子问题的定义通常涉及到两个字符串的子串。这类问题的状态转移方程通常会涉及到当前状态与前一状态的关系。 以下是这类问题的一些常见特点和处理方法:
状态定义:通常会定义一个二维的动态规划数组dp[i][j]
,其中dp[i][j]
表示第一个字符串的前i个字符和第二个字符串的前j个字符之间的某种关系。这种关系取决于具体的问题,可能是最长公共子序列的长度,也可能是最小编辑距离等。
状态转移:状态dp[i][j]
的值通常会依赖于dp[i-1][j]
,dp[i][j-1]
和dp[i-1][j-1]
的值。具体的状态转移方程取决于具体的问题。
边界条件:当i=0或j=0时,dp[i][j]
通常会有特殊的定义,这代表其中一个字符串为空字符串。
遍历顺序:由于dp[i][j]
的值依赖于dp[i-1][j]
,dp[i][j-1]
和dp[i-1][j-1]
的值,所以在计算dp数组的时候,需要按照从左到右,从上到下的顺序进行遍历。
// 最长子序列问题
func solve(str1 string, str2 string) int {
m, n := len(str1), len(str2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
// 初始化边界条件
for i := 0; i <= m; i++ {
dp[i][0] = ... // 根据具体问题来定义
}
for j := 0; j <= n; j++ {
dp[0][j] = ... // 根据具体问题来定义
}
// 状态转移
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if str1[i-1] == str2[j-1] {
dp[i][j] = ... // 根据具体问题来定义
} else {
dp[i][j] = ... // 根据具体问题来定义
}
}
}
return dp[m][n]
}
// 最长子数组问题
func findLength(nums1 []int, nums2 []int) int {
// dp[i][j]表示的是以nums1[i-1]和nums2[j-1]结尾的最长公共子数组的长度
m:= len(nums1)
n:=len(nums2)
dp:= make([][]int,m+1)
for k,_:= range dp{
dp[k] = make([]int,n+1)
}
res:=0
for i:=1;i<=m;i++{
for j:=1;j<=n;j++{
if nums1[i-1] == nums2[j-1]{
dp[i][j] = dp[i-1][j-1]+1
if dp[i][j]>res{
res= dp[i][j]
}
}
}
}
return res
}
func max( a int,b int) int{
if a>b {
return a
}
return b
}
字符串匹配系列
// 通配符匹配
func isMatch(s string, p string) bool {
m:= len(s)
n:= len(p)
dp:=make([][]bool,m+1)
for k,_:= range dp{
dp[k] = make([]bool,n+1)
}
dp[0][0] = true
for j := 1; j <= n; j++ {
if p[j-1] == '*' {
dp[0][j] = dp[0][j-1]
}
}
for i:=1;i<=m;i++{
for j:=1;j<=n ;j++{
if p[j-1]=='?'{
dp[i][j] = dp[i-1][j-1]
}else if p[j-1] == '*'{
dp[i][j] = dp[i][j-1] || dp[i-1][j]
}else if s[i-1]==p[j-1]{
dp[i][j] = dp[i-1][j-1]
}else{
}
}
}
return dp[m][n]
}
// 正则表达式匹配
func isMatch(s string, p string) bool {
m:= len(s)
n:= len(p)
dp:=make([][]bool,m+1)
for k,_:= range dp{
dp[k] = make([]bool,n+1)
}
dp[0][0] = true
for j := 2; j <= n; j++ {
if p[j-1] == '*' {
dp[0][j] = dp[0][j-2]
}
}
for i:=1;i<=m;i++{
for j:=1;j<=n ;j++{
if p[j-1]=='.'{
dp[i][j] = dp[i-1][j-1]
}else if p[j-1] == '*'{
if p[j-2] != s[i-1] && p[j-2] != '.' {
dp[i][j] = dp[i][j-2]
} else {
dp[i][j] = dp[i-1][j] || dp[i][j-2]
}
}else if s[i-1]==p[j-1]{
dp[i][j] = dp[i-1][j-1]
}else{
}
}
}
return dp[m][n]
}
// 交错字符串
func isInterleave(s1 string, s2 string, s3 string) bool {
m:= len(s1)
n:=len(s2)
if m + n != len(s3) {
return false
}
dp:= make([][]bool,m+1)
for k,_:= range dp{
dp[k] = make([]bool,n+1)
}
dp[0][0]=true
for i := 1; i <= m; i++ {
dp[i][0] = dp[i-1][0] && s1[i-1] == s3[i-1]
}
for j := 1; j <= n; j++ {
dp[0][j] = dp[0][j-1] && s2[j-1] == s3[j-1]
}
for i:=1;i<=m;i++{
for j:=1;j<=n;j++{
dp[i][j] = dp[i][j] || ( dp[i-1][j] && s1[i-1] == s3[i+j-1])
dp[i][j]= dp[i][j] || ( dp[i][j-1] && s2[j-1] == s3[i+j-1])
}
}
return dp[m][n]
}
矩阵系列
这类题目通常涉及到二维数组或矩阵,问题的规模由两个维度决定。状态转移方程通常会涉及到当前状态的上一状态,例如 dp[i-1][j]
,dp[i][j-1]
,或者 dp[i-1][j-1]
。这类题目的关键在于找到合适的状态定义和状态转移方程。
以下是这类题目的一般步骤:
定义状态:定义一个二维数组 dp,其中 dp[i][j]
表示考虑到第 i 个元素和第 j 个元素时的问题解。
初始化状态:根据问题的具体情况,初始化 dp 数组的边界值。
状态转移:根据状态转移方程,从小到大遍历 i 和 j,计算 dp[i][j]
的值。
返回结果:根据问题的具体情况,返回 dp 数组的某个值作为结果。
func solve(matrix [][]int) int {
m, n := len(matrix), len(matrix[0])
dp := make([][]int, m)
for i := range dp {
dp[i] = make([]int, n)
}
// 初始化 dp 数组的边界值
// ...
// 状态转移
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
// 根据状态转移方程计算 dp[i][j] 的值
// dp[i][j] = ...
}
}
// 返回结果
return dp[m-1][n-1]
}