前置知识：讲解067、讲解068 二维动态规划及其空间压缩技巧、区间dp-上

区间 dp

区间 dp：大范围的问题拆分成若干小范围的问题来求解

可能性展开的常见方式：

基于两侧端点讨论的可能性展开
基于范围上划分点的可能性展开

区间 dp 专题分为上、下两期，一共 12 个题

本节课再安排 6 个题，继续见识更多的区间 dp 题目

题目1.括号区间匹配

题目描述

给定一个由 [、]、(、) 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。

例如当前串是 "([[])"，那么插入一个 ']' 即可满足。

数据规模字符串长度满足 1 ≤ n ≤ 100

测试链接

括号区间匹配

思路

区间 dp：基于两侧端点讨论的可能性展开 + 基于范围上划分点的可能性展开

所有括号左右配对：字符串由 [] 和 () 并列或嵌套组合

记忆化搜索

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
)
 
const (
	MAXN    = 101
	MAX_INT = math.MaxInt
)
 
var (
	s     string
	n     int
	cache = [MAXN][MAXN]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		s = in.Text()
		n = len(s)
		build()
		fmt.Fprintln(out, f(0, n-1))
	}
	out.Flush()
}
 
func build() {
	for i := 0; i < n; i++ {
		for j := 0; j < n; j++ {
			cache[i][j] = -1
		}
	}
}
 
// 让 s[l:r+1] 所有括号左右配对至少需要插入几个字符
func f(l, r int) int {
	if l == r {
		// 只有一个字符，插入一个相匹配的括号即可
		return 1
	}
	if l+1 == r {
		// 有两个字符
		// 如果两个字符相匹配，就不用插入
		// 如果两个字符不匹配，就需要插入 2 个字符
		if s[l] == '(' && s[r] == ')' || s[l] == '[' && s[r] == ']' {
			return 0
		}
		return 2
	}
	if cache[l][r] != -1 {
		return cache[l][r]
	}
	// l~r 字符数量 >= 3
 
	// 可能性 1：l、r 是配对的，继续搞定 s[l+1,r-1] 即可
	// 嵌套
	p1 := MAX_INT
	if s[l] == '(' && s[r] == ')' || s[l] == '[' && s[r] == ']' {
		p1 = f(l+1, r-1)
	}
	// 可能性 2：基于每个可能的划分点，做左右划分
	// 并列
	p2 := MAX_INT
	for m := l; m < r; m++ {
		p2 = min(p2, f(l, m)+f(m+1, r))
	}
	cache[l][r] = min(p1, p2)
	return cache[l][r]
}
 
// 牛客 go 版本太低，没有内置的 min 函数
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

位置依赖

package main
 
import (
	"bufio"
	"fmt"
	"math"
	"os"
)
 
const (
	MAXN    = 101
	MAX_INT = math.MaxInt
)
 
var (
	s  string
	n  int
	dp = [MAXN][MAXN]int{}
)
 
func main() {
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		s = in.Text()
		n = len(s)
		fmt.Fprintln(out, compute())
	}
	out.Flush()
}
 
func compute() int {
	// 初始化
	for i := 0; i < n; i++ {
		// 只有一个字符，插入一个相匹配的括号即可
		dp[i][i] = 1
		// 有两个字符
		// 如果两个字符相匹配，就不用插入
		// 如果两个字符不匹配，就需要插入 2 个字符
		if i+1 < n {
			if s[i] == '(' && s[i+1] == ')' || s[i] == '[' && s[i+1] == ']' {
				dp[i][i+1] = 0
			} else {
				dp[i][i+1] = 2
			}
		}
	}
 
	for l := n - 3; l >= 0; l-- {
		// r := l+2：l~r 字符数量 >= 3
		for r := l + 2; r < n; r++ {
			// 初始化：防止上一组测试带来的影响
			dp[l][r] = MAX_INT
			// 可能性 1：l、r 是配对的，继续搞定 s[l+1,r-1] 即可
			// 嵌套
			if s[l] == '(' && s[r] == ')' || s[l] == '[' && s[r] == ']' {
				dp[l][r] = dp[l+1][r-1]
			}
			// 可能性 2：基于每个可能的划分点，做左右划分
			// 并列
			for m := l; m < r; m++ {
				dp[l][r] = min(dp[l][r], dp[l][m]+dp[m+1][r])
			}
		}
	}
	return dp[0][n-1]
}
 
// 牛客 go 版本太低，没有内置的 min 函数
func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

题目2.奇怪的打印机

题目描述

有台奇怪的打印机有以下两个特殊要求：

打印机每次只能打印由 同一个字符 组成的序列。
每次可以在从起始到结束的任意位置打印新字符，并且会覆盖掉原来已有的字符。

给你一个字符串 s，你的任务是计算这个打印机打印它需要的最少打印次数。

示例 1：

输入：s = "aaabbb"

输出：2

解释：首先打印 "aaa" 然后打印 "bbb"。

示例 2：

输入：s = "aba"

输出：2

解释：首先打印 "aaa" 然后在第二个位置打印 "b" 覆盖掉原来的字符 'a'。

提示：

1 <= s.length <= 100
s 由小写英文字母组成

测试链接

洛谷：P4170【CQOI2007】涂色
力扣：664.奇怪的打印机

思路

区间 dp：基于两侧端点讨论的可能性展开 + 基于范围上划分点的可能性展开

答案

func strangePrinter(s string) int {
	n := len(s)
	// dp[l][r]：打印 s[l:r+1] 需要的最少打印次数
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		// 初始化
		// 只有一个字符：打印一次
		dp[i][i] = 1
		// 有两个字符：两个字符一样就打印一次、不一样就打印两次
		if i+1 < n {
			if s[i] == s[i+1] {
				dp[i][i+1] = 1
			} else {
				dp[i][i+1] = 2
			}
		}
	}
 
	for l := n - 3; l >= 0; l-- {
		for r := l + 2; r < n; r++ {
			// 能涂左右两侧就先涂左右两侧，在中间位置继续递推
			// 因为左右两侧不会再被覆盖
			if s[l] == s[r] {
				// 左右两侧相同就就把整个 l~r 都涂了
				// 就是 dp[l][r-1]，最右位置相当于在涂 l~r-1 的过程就涂了
				// 而不是 dp[l+1][r-1] + 1，因为 l~r 都是一个字符的话，每次都 +1，就不对了
				dp[l][r] = dp[l][r-1] // 或：dp[l+1][r]
			} else {
				dp[l][r] = math.MaxInt
				// 遍历每个划分点，分别考虑涂 l~m 和 m+1~r
				for m := l; m < r; m++ {
					dp[l][r] = min(dp[l][r], dp[l][m]+dp[m+1][r])
				}
			}
		}
	}
 
	return dp[0][n-1]
}

题目3.合唱队

题目描述

将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 n 个人，第 i 个人的身高为 hi，并已知任何两个人的身高都不同。

如下排队的方式：

第一个人直接插入空的当前队形中。
对从第二个人开始的每个人，如果他比上一个进入队形的人高，那么将他插入当前队形的最右边。反之将他插入当前队形的最左边。

当 n 个人全部插入当前队形后便获得最终排出的队形。

给出一个理想队形，返回有多少种方式可以获得理想的队形。

答案对 19650827 取模

数据规模：

1 <= n <= 1000
1000 <= hi <= 2000

测试链接

P3205【HNOI2010】合唱队

思路

区间 dp：基于两侧端点讨论的可能性展开

dp[l][r][0]：形成 l~r 的状况的方法数，同时要求 l 位置是最后进入队形的
dp[l][r][1]：形成 l~r 的状况的方法数，同时要求 r 位置是最后进入队形的

[a, b, ..., c, d]
 l  l+1    r-1 r

最后进入队形的是 a
1. 上一个进入队形的是 b
  - a < b：dp[l+1][r][0]
  - a > b：0，不可能形成这种队列
2. 上一个进入队形的是 d
  - …
最后进入队形的是 d
- …

2 种情况相加就是形成 l~r 的状况的方法数

空间压缩：每个格子只依赖下、左俩个格子，从下往上滚动数组、从左往右递推

答案

package main
 
import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)
 
const (
	MAXN = 1001
	MOD  = 19650827
)
 
var (
	n   int
	arr = [MAXN]int{}
	dp  = [MAXN][2]int{}
)
 
func main() {
	// s := `4
	// 1701 1702 1703 1704`
	// in := bufio.NewScanner(strings.NewReader(s))
	in := bufio.NewScanner(os.Stdin)
	in.Split(bufio.ScanWords)
	out := bufio.NewWriterSize(os.Stdout, 4096)
	for in.Scan() {
		n, _ = strconv.Atoi(in.Text())
		for i := 0; i < n; i++ {
			in.Scan()
			arr[i], _ = strconv.Atoi(in.Text())
		}
		if n == 1 {
			fmt.Fprintln(out, 1)
		} else {
			fmt.Fprintln(out, compute2())
		}
	}
	out.Flush()
}
 
// 严格位置依赖的动态规划
func compute1() int {
	dp := make([][][2]int, n)
	for i := range dp {
		dp[i] = make([][2]int, n)
		// 初始化：只有一个人
		dp[i][i][0] = 1
		dp[i][i][1] = 1
		// 初始化：有两个人
		if i+1 < n {
			if arr[i] < arr[i+1] {
				dp[i][i+1][0] = 1
				dp[i][i+1][1] = 1
			}
		}
	}
	for l := n - 3; l >= 0; l-- {
		for r := l + 2; r < n; r++ {
			// 当前 l 进入队形，上一个是 l+1 进入队形
			if arr[l] < arr[l+1] {
				dp[l][r][0] = (dp[l][r][0] + dp[l+1][r][0]) % MOD
			}
			// 当前 l 进入队形，上一个是 r 进入队形
			if arr[l] < arr[r] {
				dp[l][r][0] = (dp[l][r][0] + dp[l+1][r][1]) % MOD
			}
			// 当前 r 进入队形，上一个是 l 进入队形
			if arr[r] > arr[l] {
				dp[l][r][1] = (dp[l][r][1] + dp[l][r-1][0]) % MOD
			}
			// 当前 r 进入队形，上一个是 r-1 进入队形
			if arr[r] > arr[r-1] {
				dp[l][r][1] = (dp[l][r][1] + dp[l][r-1][1]) % MOD
			}
		}
	}
 
	return (dp[0][n-1][0] + dp[0][n-1][1]) % MOD
}
 
// 空间压缩
func compute2() int {
	// 初始化 dp[n-2][n-1]
	if arr[n-2] < arr[n-1] {
		dp[n-1][0] = 1
		dp[n-1][1] = 1
	}
	// 从 n-3 行开始推
	for l := n - 3; l >= 0; l-- {
		// 初始化每行最左位置
		if arr[l] < arr[l+1] {
			dp[l+1][0] = 1
			dp[l+1][1] = 1
		} else {
			dp[l+1][0] = 0
			dp[l+1][1] = 0
		}
		for r := l + 2; r < n; r++ {
			a, b := 0, 0
			// 当前 l 进入队形，上一个是 l+1 进入队形
			if arr[l] < arr[l+1] {
				a = (a + dp[r][0]) % MOD
			}
			// 当前 l 进入队形，上一个是 r 进入队形
			if arr[l] < arr[r] {
				a = (a + dp[r][1]) % MOD
			}
			// 当前 r 进入队形，上一个是 l 进入队形
			if arr[r] > arr[l] {
				b = (b + dp[r-1][0]) % MOD
			}
			// 当前 r 进入队形，上一个是 r-1 进入队形
			if arr[r] > arr[r-1] {
				b = (b + dp[r-1][1]) % MOD
			}
			dp[r][0] = a
			dp[r][1] = b
		}
	}
	return (dp[n-1][0] + dp[n-1][1]) % MOD
}

题目4.移除盒子

题目描述

给出一些不同颜色的盒子 boxes ，盒子的颜色由不同的正数表示。

你将经过若干轮操作去去掉盒子，直到所有的盒子都去掉为止。每一轮你可以移除具有相同颜色的连续 k 个盒子（k >= 1），这样一轮之后你将得到 k * k 个积分。

返回你能获得的最大积分和。

示例 1：

输入：boxes = [1,3,2,2,2,3,4,3,1]

输出：23

解释：

[1, 3, 2, 2, 2, 3, 4, 3, 1]

----> [1, 3, 3, 4, 3, 1] (3*3=9 分)

----> [1, 3, 3, 3, 1] (1*1=1 分)

----> [1, 1] (3*3=9 分)

----> [] (2*2=4 分)

提示：

1 <= boxes.length <= 100
1 <= boxes[i] <= 100

测试链接

546.移除盒子

思路

区间 dp：基于范围上划分点的可能性展开

三维动态规划 dp[l][r][k]：boxes[l:r+1] 范围上要去消除，前面跟着 k 个连续的和 boxes[l] 颜色一样的盒子，这种情况下，返回最大得分

记忆化搜索

var (
	arr   []int
	cache [][][]int
)
 
func removeBoxes(boxes []int) int {
	arr = boxes
	n := len(arr)
	cache = make([][][]int, n)
	for i := range cache {
		cache[i] = make([][]int, n)
		for j := range cache[i] {
			cache[i][j] = make([]int, n)
		}
	}
	return f(0, n-1, 0)
}
 
// boxes[l:r+1] 范围上要去消除，前面跟着 k 个连续的和 boxes[l] 颜色一样的盒子
// 这种情况下，返回最大得分
func f(l, r, k int) int {
	if l > r {
		return 0
	}
	if cache[l][r][k] > 0 {
		return cache[l][r][k]
	}
	// boxes[l:s+1] 颜色都一样，boxes[s+1] 就不是同一种颜色了
	s := l
	for s+1 <= r && arr[l] == arr[s+1] {
		s++
	}
	// cnt 是总前缀数量：之前的相同前缀（k 个） + l~s 颜色相同的部分（s+1-l 个）
	cnt := k + s + 1 - l
	// 可能性 1：前缀先消
	ans := cnt*cnt + f(s+1, r, 0)
	// 可能性 2：讨论前缀跟着哪个之后的相同颜色，一起消掉
	for m := s + 2; m <= r; m++ {
		// arr[l] == arr[m] 是必须条件
		// arr[m-1] != arr[m] 是剪枝条件，避免不必要的调用
		if arr[l] == arr[m] && arr[m-1] != arr[m] {
			ans = max(ans, f(s+1, m-1, 0)+f(m, r, cnt))
		}
	}
	cache[l][r][k] = ans
	return ans
}

复杂度

时间复杂度： $O (n^{4})$
- $O (n^{3})$ ：动态规划表的大小
- $O (n)$ ：每个格子的枚举代价
空间复杂度： $O (n^{3})$

题目5.合并石头的最低成本

题目描述

有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

每次移动需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1。

示例 1：

输入：stones = [3,2,4,1], K = 2

输出：20

解释：从 [3, 2, 4, 1] 开始。

合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。

合并 [4, 1]，成本为 5，剩下 [5, 5]。

合并 [5, 5]，成本为 10，剩下 [10]。

总成本 20，这是可能的最小值。

示例 2：

输入：stones = [3,2,4,1], K = 3

输出：-1

解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。

示例 3：

输入：stones = [3,5,1,2,6], K = 3

输出：25

解释：从 [3, 5, 1, 2, 6] 开始。

合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。

合并 [3, 8, 6]，成本为 17，剩下 [17]。

总成本 25，这是可能的最小值。

提示：

n == stones.length
1 <= n <= 30
1 <= stones[i] <= 100
2 <= k <= 30

测试链接

1000.合并石头的最低成本

思路

区间 dp：基于范围上划分点的可能性展开

优化策略来自于观察：

l~r 最终会变成几份其实是注定的，根本就无法改变

那么也就知道，满足 (n - 1) % (k - 1) == 0 的情况下，0~n-1 最终一定是 1 份，也无法改变

如果 l~r 最终一定是 1 份，那么要保证 l~m 最终一定是 1 份，m+1~r 最终一定是 k-1 份

如果 l~r 最终一定是 p 份（p>1），那么要保证 l~m 最终一定是 1 份，m+1~r 最终一定是 p-1 份

怎么保证 l~m 最终一定是 1 份？枚举行为中，m += k-1 保证

如果 l~r 最终一定是 1 份，就加上最后合并成 1 份的代价

如果 l~r 最终一定是 p 份（p>1），就不加代价，因为没有合并成 1 份

答案

func mergeStones(stones []int, k int) int {
	n := len(stones)
	// 无法把所有石头合并成一堆
	if (n-1)%(k-1) != 0 {
		return -1
	}
	// 前缀和
	// 多补了一个 0 位置，为了方便算 l~r 的累加和（合并成本）
	// l~r preSum[r+1] - preSum[l]
	preSum := make([]int, n+1)
	for i := 0; i < n; i++ {
		preSum[i+1] = preSum[i] + stones[i]
	}
	// dp[l][r]：l~r 范围上的石头，合并到不能再合并（份数是确定的），最小代价是多少
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
	}
	// 初始化：l == r 已经是一堆了，代价为 0
	for l := n - 2; l >= 0; l-- {
		for r := l + 1; r < n; r++ {
			ans := math.MaxInt
			for m := l; m < r; m += k - 1 {
				ans = min(ans, dp[l][m]+dp[m+1][r])
			}
			if (r-l)%(k-1) == 0 {
				// 最终一定能划分成 1 份，那么就再加合并代价
				ans += preSum[r+1] - preSum[l]
			}
			dp[l][r] = ans
		}
	}
	return dp[0][n-1]
}

复杂度

时间复杂度： $O (n^{3})$
- $O (n^{2})$ ：动态规划表的大小
- $O (n)$ ：每个格子的枚举代价
空间复杂度： $O (n^{2})$
- 每个格子依赖很多位置格子，所以不能用滚动数组进行空间压缩

题目6.统计不同回文子序列

题目描述

给你一个字符串 s ，返回 s 中不同的非空回文子序列个数。由于答案可能很大，请返回对 10^9 + 7 取余的结果。

字符串的子序列可以经由字符串删除 0 个或多个字符获得。

如果一个序列与它反转后的序列一致，那么它是回文序列。

如果存在某个 i , 满足 ai != bi ，则两个序列 a1, a2, ... 和 b1, b2, ... 不同。

示例 1：

输入：s = 'bccb'

输出：6

解释：6 个不同的非空回文子字符序列分别为：'b', 'c', 'bb', 'cc', 'bcb', 'bccb'。

注意：'bcb' 虽然出现两次但仅计数一次。

提示：

1 <= s.length <= 1000
s[i] 仅包含 'a', 'b', 'c' 或 'd'

测试链接

730.统计不同回文子序列

思路

区间 dp：基于两侧端点讨论的可能性展开

dp[l][r]：s[l:r+1] 范围上有多少种不同的非空回文子序列

s[l] != s[r]：dp[l][r-1] + dp[l+1][r] - dp[l+1][r-1]
- 不要 s[l] 的数量 + 不要 s[r] 的数量 - 算重的既不要 s[l] 也不要 s[r] 的数量
s[l] == s[r]：不妨设这个相同的字符是 a
1. l~r 内部无 a：dp[l+1][r-1] * 2 + 2
  - *2：l+1~r-1 的回文串加左右两侧的 a 构成的新回文串数量 + 不加左右两侧的 a 的原始回文串数量
  - +2：a、aa 两种回文串情况
2. l~r 内部有一个 a：dp[l+1][r-1] * 2 + 1
  - 相对于 l~r 内部无 a 的情况少了一种 a 回文串的情况
3. l~r 内部 a 多于一个：dp[l+1][r-1] * 2 - dp[i+1][j-1]
  - 其中 i 是 l~r 内部最左侧 a 的下标，j 是 l~r 内部最右侧 a 的下标
  - i~j 的情况在 l~r 中多算了一遍，要减去

如何快速得出某个范围内有几个某字符、内部最左侧和内部最右侧的下标是哪里？

数据预处理：

left[i]：i 位置的左边和 s[i] 字符相等且最近的位置在哪，不存在就是 -1
right[i]：i 位置的右边和 s[i] 字符相等且最近的位置在哪，不存在就是 n

答案

const (
	MOD = 1e9 + 7
)
 
func countPalindromicSubsequences(s string) int {
	n := len(s)
	// 数据预处理
	// left[i]：i 位置的左边和 s[i] 字符相等且最近的位置在哪，不存在就是 -1
	// 数据保证 s[i] 仅包含 a, b, c, d
	last := [4]int{-1, -1, -1, -1}
	left := make([]int, n)
	for i := 0; i < n; i++ {
		left[i] = last[s[i]-'a']
		last[s[i]-'a'] = i
	}
	// right[i]：i 位置的右边和 s[i] 字符相等且最近的位置在哪，不存在就是 n
	last = [4]int{n, n, n, n}
	right := make([]int, n)
	for i := n - 1; i >= 0; i-- {
		right[i] = last[s[i]-'a']
		last[s[i]-'a'] = i
	}
 
	// dp[l][r]：s[l:r+1] 范围上有多少种不同的非空回文子序列
	// 如果 l>r，认为是无效范围 dp[i][j] = 0
	dp := make([][]int, n)
	for i := range dp {
		dp[i] = make([]int, n)
		// 初始化：只有一个数就是回文串
		dp[i][i] = 1
	}
	for l := n - 2; l >= 0; l-- {
		for r := l + 1; r < n; r++ {
			if s[l] != s[r] {
				// 同余原理：因为要取模，所以只要发生减操作就 + MOD
				dp[l][r] = dp[l+1][r] + dp[l][r-1] - dp[l+1][r-1] + MOD
			} else {
				i := right[l]
				j := left[r]
				if i > j { // 或： i == r，或：l == j
					// l~r 内部无 s[l]
					dp[l][r] = dp[l+1][r-1]<<1 + 2
				} else if i == j {
					// l~r 内部有一个 s[l]
					dp[l][r] = dp[l+1][r-1]<<1 + 1
				} else {
					// l~r 内部 s[l] 多于一个
					// 同余原理：因为要取模，所以只要发生减操作就 + MOD
					dp[l][r] = dp[l+1][r-1]<<1 - dp[i+1][j-1] + MOD
				}
			}
			dp[l][r] %= MOD
		}
	}
 
	return dp[0][n-1]
}

复杂度

时间复杂度： $O (n^{2})$
- $O (n^{2})$ ：动态规划表的大小
- $O (1)$ ：归功于数据预处理，每个格子的枚举是常数操作
空间复杂度： $O (n^{2})$
- 依赖的格子规律性较差，难以做空间压缩

My-Notes

全部文章

059.区间dp-下

区间 dp

题目1.括号区间匹配

题目描述

测试链接

思路

记忆化搜索

位置依赖

题目2.奇怪的打印机

题目描述

测试链接

思路

答案

题目3.合唱队

题目描述

测试链接

思路

答案

题目4.移除盒子

题目描述

测试链接

思路

记忆化搜索

复杂度

题目5.合并石头的最低成本

题目描述

测试链接

思路

答案

复杂度

题目6.统计不同回文子序列

题目描述

测试链接

思路

答案

复杂度

目录

关系图谱