048.从递归入手一维动态规划

前置知识：需要熟悉递归、同余原理

动态规划 §

本节课从基本递归入手，来了解一维动态规划

动态规划：用空间代替重复计算，包含一整套原理和技巧的总和，课程会用非常大的篇幅来全盘介绍

算法分为：知道怎么算的算法、知道怎么试的算法

• 比如之前的单源最短路径算法明确知道怎么算（Dijkstra 算法、A* 算法）
• 而动态规划属于是知道怎么试的算法，一步一步试而找到正确答案

什么时候使用动态规划 §

有些递归在展开计算时，总是重复调用同一个子问题的解，这种重复调用的递归变成动态规划很有收益

如果每次展开都是不同的解，或者重复调用的现象很少，那么没有改动态规划的必要

下节课 会举例，哪些递归没有必要改动态规划的必要

从递归入手动态规划 §

任何动态规划问题都一定对应着一个有重复调用行为的递归

所以任何动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法

题目 1 到 题目 4，都从递归入手，逐渐改出动态规划的实现

分析位置依赖（状态依赖）

递归的尝试策略就是动态规划的状态转移方程，完全一回事！

推荐从尝试入手，因为代码好写，并且一旦发现尝试错误，重新想别的递归代价轻！

动态规划视角分析问题 §

当熟悉了从递归到动态规划的转化过程，那么就可以纯粹用动态规划的视角来分析问题了

题目 5 到 题目 8，都是纯粹用动态规划的视角来分析、优化的

如果不熟悉这个过程，直接一上来就硬去理解状态转移方程，那么往往会步履维艰、邯郸学步、东施效颦（左神：这是多年教学看到的真实情况）

很多极为优异的想法、设计和优化，来自：天赋 and 努力

建议脚踏实地，真正做好从递归到动态规划的练习

接下来的几节课也都会从最基本递归入手，逐渐写出动态规划的版本

动态规划的大致过程 §

想出设计优良的递归尝试（方法、经验、固定套路很多），有关尝试展开顺序的说明：

• 记忆化搜索（从顶到底的动态规划，即：从复杂到简单），如果每个状态的计算枚举代价很低，往往到这里就可以了
• 严格位置依赖的动态规划（从底到顶的动态规划，即：从简单推到复杂），更多是为了下面说的进一步优化枚举做的准备
• 进一步优化空间（空间压缩），一维、二维、多维动态规划都存在这种优化
• 进一步优化枚举也就是优化时间（本节没有涉及，但是后续巨多内容和这有关）

解决一个问题，可能有很多尝试方法

众多的尝试方法中，可能若干的尝试方法有重复调用的情况，可以转化成动态规划

若干个可以转化成动态规划的方法中，又可能有优劣之分

判定哪个是最优的动态规划方法，依据来自题目具体参数的数据量

最优的动态规划方法实现后，后续又有一整套的优化技巧

本系列课程从【必备】到【扩展】到【挺难】都会讲动态规划，会把这一话题做全面的讲述

备注 §

重叠子问题？最优子结构？无后效性？

此时谈这些太早，【必备】阶段动态规划的大总结，将在动态规划专题结束时进行

题目1.斐波那契数 §

题目描述 §

斐波那契数（通常用 F(n) 表示）形成的序列称为 斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

• F(0) = 0，F(1) = 1
• F(n) = F(n - 1) + F(n - 2)，其中 n > 1

给定 n ，请计算 F(n)。

测试链接 §

509.斐波那契数

暴力递归 §

func fib(n int) int {
	if n <= 1 {
		return n
	}
	return fib(n-1) + fib(n-2)
}

• 时间复杂度：$O(2^n)$，每个节点都向下展开两个节点，最终展开到 $2^n$ 个节点
• 空间复杂度：$O(1)$，没有任何额外空间

慢的原因？太多重复计算，同样的参数之前计算过了，之后还要重新计算

记忆化搜索 §

一个显而易见的优化方式就是建立缓存：以参数为 key 以结果为 value 建立缓存。缓存中有就直接拿；缓存中没有就算，算完放到缓存中

var (
	cache []int
)
 
func fib(n int) int {
	if n <= 1 {
		return n
	}
	cache = make([]int, n+1)
	for i := range cache {
		cache[i] = -1
	}
	cache[0] = 0
	cache[1] = 1
	return f(n)
}
 
func f(n int) int {
	if cache[n] != -1 {
		return cache[n]
	}
	ans := f(n-1) + f(n-2)
	cache[n] = ans
	return ans
}

• 时间复杂度：$O(n)$，缓存表直接拿
• 空间复杂度：$O(n)$，缓存表空间

现在的过程是从顶到底进行展开，只是展开过的节点不再重复展开，而是直接从缓存表拿答案

这个叫：从顶到底的动态规划，也叫记忆化搜索

位置依赖 §

按照自然思维从 0 推到 n 就是从底到顶的动态规划，也叫位置依赖的动态规划

func fib(n int) int {
	if n <= 1 {
		return n
	}
	dp := make([]int, n+1)
	dp[0] = 0
	dp[1] = 1
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

上面的动态规划空间复杂度为 $O(n)$，dp[i] 只与 dp[i-1] 和 dp[i-2] 有关，完全没必要保留整个 dp 数组，可以将空间复杂度优化为 $O(1)$

这种优化方式称为：空间压缩、滚动数组

func fib(n int) int {
	if n <= 1 {
		return n
	}
	dp0 := 0
	dp1 := 1
	for i := 2; i <= n; i++ {
		dp0, dp1 = dp1, dp0+dp1
	}
	return dp1
}

• 时间复杂度：$O(n)$，从 0 推到 n，严格的 $O(n)$，比 记忆化搜索 常数要好
• 空间复杂度：$O(1)$，从 $O(n)$ 的 dp 数组优化为两个变量

矩阵快速幂 §

最优解是矩阵快速幂，时间复杂度可以做到 $O(lo{g}^n)$

将在后续课程讲解

题目2.最低票价 §

题目描述 §

在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行。在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出。每一项是一个从 1 到 365 的整数。

火车票有 三种不同的销售方式：

• 一张 为期一天 的通行证售价为 costs[0] 美元；
• 一张 为期七天 的通行证售价为 costs[1] 美元；
• 一张 为期三十天 的通行证售价为 costs[2] 美元。

通行证允许数天无限制的旅行。 例如，如果我们在第 2 天获得一张 为期 7 天 的通行证，那么我们可以连着旅行 7 天：第 2 天、第 3 天、第 4 天、第 5 天、第 6 天、第 7 天和第 8 天。

返回你想要完成在给定的列表 days 中列出的每一天的旅行所需要的最低消费。

提示：

• 1 <= days.length <= 365
• 1 <= days[i] <= 365
• days 按顺序严格递增
• costs.length == 3
• 1 <= costs[i] <= 1000

测试链接 §

983.最低票价

暴力递归 §

暴力尝试，时间复杂度：$O(3^n)$

var (
	theDays   []int
	theCosts  []int
	n         int
	durations = [3]int{1, 7, 30}
)
 
func mincostTickets(days []int, costs []int) int {
	theDays = days
	theCosts = costs
	n = len(days)
	return f(0)
}
 
// days[idx:] 最少花费是多少
func f(i int) int {
	if i == n {
		return 0
	}
	ans := math.MaxInt
	// 方案一二三依次尝试，取最少花费
	for k := 0; k < 3; k++ {
		j := i
		for j < n && theDays[i]+durations[k] > theDays[j] {
			j++
		}
		ans = min(ans, theCosts[k]+f(j))
	}
	return ans
}

记忆化搜索 §

暴力尝试改记忆化搜索，从顶到底的动态规划，时间复杂度：$O(n)$

var (
	cache     []int
	theDays   []int
	theCosts  []int
	n         int
	durations = [3]int{1, 7, 30}
)
 
func mincostTickets(days []int, costs []int) int {
	theDays = days
	theCosts = costs
	n = len(days)
	cache = make([]int, n)
	for i := range cache {
		cache[i] = math.MaxInt
	}
	return f(0)
}
 
// days[idx:] 最少花费是多少
func f(i int) int {
	if i == n {
		return 0
	}
	if cache[i] != math.MaxInt {
		return cache[i]
	}
	ans := math.MaxInt
	// 方案一二三依次尝试，取最少花费
	for k := 0; k < 3; k++ {
		j := i
		for j < n && theDays[i]+durations[k] > theDays[j] {
			j++
		}
		ans = min(ans, theCosts[k]+f(j))
	}
	cache[i] = ans
	return ans
}

位置依赖 §

严格位置依赖的动态规划，从底到顶的动态规划，时间复杂度：$O(n)$

var (
	durations = [3]int{1, 7, 30}
)
 
func mincostTickets(days []int, costs []int) int {
	n := len(days)
	// dp[i]: days[i:] 最少花费是多少
	dp := make([]int, n+1)
	for i := range dp {
		dp[i] = math.MaxInt
	}
	dp[n] = 0 // 越界位置
 
	for i := n - 1; i >= 0; i-- { // 前面的依赖后面的，从后往前遍历
		for k := 0; k < 3; k++ {
			j := i
			for j < n && days[i]+durations[k] > days[j] {
				j++
			}
			dp[i] = min(dp[i], costs[k]+dp[j])
		}
	}
	return dp[0]
}

题目3.解码方法 §

题目描述 §

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

• ‘A’ -> “1”
• ‘B’ -> “2”
• …
• ‘Z’ -> “26”

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

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

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

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数。

题目数据保证答案肯定是一个 32 位 的整数。

提示：

• 1 <= s.length <= 100
• s 只包含数字，并且可能包含前导零。

测试链接 §

91.解码方法

暴力递归 §

var (
	S string
	n int
)
 
func numDecodings(s string) int {
	S = s
	n = len(s)
	return f(0)
}
 
// s[i:] 有多少种有效的转化方案
func f(i int) int {
	if i == n {
		return 1 // 一种有效：之前做的决定
	}
	if S[i] == '0' {
		return 0 // 之前做的决定不对
	}
	ans := f(i + 1) // s[i] 必定有效，不用判断了
	if i+1 < n && int(S[i]-'0')*10+int(S[i+1]-'0') <= 26 {
		// 两位是有效的
		ans += f(i + 2)
	}
	return ans
}

记忆化搜索 §

var (
	cache []int
	S     string
	n     int
)
 
func numDecodings(s string) int {
	S = s
	n = len(s)
	cache = make([]int, n)
	for i := range cache {
		cache[i] = -1
	}
	return f(0)
}
 
// s[i:] 有多少种有效的转化方案
func f(i int) int {
	if i == n {
		return 1 // 一种有效：之前做的决定
	}
	if cache[i] != -1 {
		return cache[i]
	}
	ans := 0
	if S[i] == '0' {
		ans = 0 // 之前做的决定不对
	} else {
		ans = f(i + 1) // s[i] 必定有效，不用判断了
		if i+1 < n && int(S[i]-'0')*10+int(S[i+1]-'0') <= 26 {
			// 两位是有效的
			ans += f(i + 2)
		}
	}
	cache[i] = ans
	return ans
}

位置依赖 §

func numDecodings(s string) int {
	n := len(s)
	// dp[i]: s[i:] 有几种解码方法
	dp := make([]int, n+1)
	dp[n] = 1 // 越界位置
	// 一个状态依赖于后两个状态，所以要从后往前遍历
	for i := n - 1; i >= 0; i-- {
		if s[i] == '0' {
			dp[i] = 0
		} else {
			dp[i] = dp[i+1]
			if i+1 < n && int(s[i]-'0')*10+int(s[i+1]-'0') <= 26 {
				dp[i] += dp[i+2]
			}
		}
	}
	return dp[0]
}

空间压缩 §

一个状态只依赖于后两个状态，没必要保留整个 dp 数组，压缩成几个变量即可，可以理解为滚动数组

func numDecodings(s string) int {
	n := len(s)
	cur := 0      // dp[i]
	next := 1     // dp[i+1]
	nextNext := 0 // dp[i+2]
	for i := n - 1; i >= 0; i-- {
		if s[i] == '0' {
			cur = 0
		} else {
			cur = next
			if i+1 < n && int(s[i]-'0')*10+int(s[i+1]-'0') <= 26 {
				cur += nextNext
			}
		}
		// 从后往前走
		nextNext = next
		next = cur
	}
	return next
}

题目4.解码方法 II §

基本和 题目 3 一样，就是多了一些判断

题目描述 §

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

• ‘A’ -> “1”
• ‘B’ -> “2”
• …
• ‘Z’ -> “26”

要 解码 一条已编码的消息，所有的数字都必须分组，然后按原来的编码方案反向映射回字母（可能存在多种方式）。例如，"11106" 可以映射为：

• "AAJF" 对应分组 (1 1 10 6)
• "KJF" 对应分组 (11 10 6)

注意，像 (1 11 06) 这样的分组是无效的，因为 "06" 不可以映射为 'F' ，因为 "6" 与 "06" 不同。

除了 上面描述的数字字母映射方案，编码消息中可能包含 '*' 字符，可以表示从 '1' 到 '9' 的任一数字（不包括 '0'）。例如，编码字符串 "1*" 可以表示 "11"、"12"、"13"、"14"、"15"、"16"、"17"、"18" 或 "19" 中的任意一条消息。对 "1*" 进行解码，相当于解码该字符串可以表示的任何编码消息。

给你一个字符串 s ，由数字和 '*' 字符组成，返回 解码 该字符串的方法 数目 。

由于答案数目可能非常大，返回 10^9 + 7 的 模。

提示：

• 1 <= s.length <= 10^5
• s[i] 是 0 - 9 中的一位数字或字符 '*'

测试链接 §

639.解码方法 II

暴力递归 §

var (
	S string
	n int
)
 
func numDecodings(s string) int {
	S = s
	n = len(s)
	return f(0)
}
 
func f(i int) int {
	if i == n {
		return 1
	}
	if S[i] == '0' {
		return 0
	}
	ans := 0
	if S[i] == '*' {
		ans = 9 * f(i+1)
	} else {
		ans = f(i + 1)
	}
	if i+1 < n {
		if S[i] != '*' {
			if S[i+1] != '*' {
				if int(S[i]-'0')*10+int(S[i+1]-'0') <= 26 {
					ans += f(i + 2)
				}
			} else {
				if S[i] == '1' {
					ans += 9 * f(i+2)
				} else if S[i] == '2' {
					ans += 6 * f(i+2)
				}
			}
		} else {
			if S[i+1] != '*' {
				if S[i+1] <= '6' {
					ans += 2 * f(i+2)
				} else {
					ans += f(i + 2)
				}
			} else {
				// 11~26
				ans += 15 * f(i+2)
			}
		}
	}
 
	return ans
}

记忆化搜索 §

const (
	MOD = 1e9 + 7
)
 
var (
	cache []int
	S     string
	n     int
)
 
func numDecodings(s string) int {
	S = s
	n = len(s)
	cache = make([]int, n)
	for i := range cache {
		cache[i] = -1
	}
	return f(0)
}
 
func f(i int) int {
	if i == n {
		return 1
	}
	if cache[i] != -1 {
		return cache[i]
	}
	ans := 0
	if S[i] == '0' {
		ans = 0
	} else {
		if S[i] == '*' {
			ans = 9 * f(i+1)
		} else {
			ans = f(i + 1)
		}
		if i+1 < n {
			if S[i] != '*' {
				if S[i+1] != '*' {
					if int(S[i]-'0')*10+int(S[i+1]-'0') <= 26 {
						ans += f(i + 2)
					}
				} else {
					if S[i] == '1' {
						ans += 9 * f(i+2)
					} else if S[i] == '2' {
						ans += 6 * f(i+2)
					}
				}
			} else {
				if S[i+1] != '*' {
					if S[i+1] <= '6' {
						ans += 2 * f(i+2)
					} else {
						ans += f(i + 2)
					}
				} else {
					// 11~26
					ans += 15 * f(i+2)
				}
			}
		}
	}
	ans %= MOD
	cache[i] = ans
	return ans
}

位置依赖 §

const (
	MOD = 1e9 + 7
)
 
func numDecodings(s string) int {
	n := len(s)
	dp := make([]int, n+1)
	dp[n] = 1
	for i := n - 1; i >= 0; i-- {
		if s[i] == '0' {
			dp[i] = 0
		} else {
			if s[i] == '*' {
				dp[i] = 9 * dp[i+1]
			} else {
				dp[i] = dp[i+1]
			}
			if i+1 < n {
				if s[i] != '*' {
					if s[i+1] != '*' {
						if int(s[i]-'0')*10+int(s[i+1]-'0') <= 26 {
							dp[i] += dp[i+2]
						}
					} else {
						if s[i] == '1' {
							dp[i] += 9 * dp[i+2]
						} else if s[i] == '2' {
							dp[i] += 6 * dp[i+2]
						}
					}
				} else {
					if s[i+1] != '*' {
						if s[i+1] <= '6' {
							dp[i] += 2 * dp[i+2]
						} else {
							dp[i] += dp[i+2]
						}
					} else {
						// 11~26
						dp[i] += 15 * dp[i+2]
					}
				}
			}
			dp[i] %= MOD
		}
	}
	return dp[0]
}

空间压缩 §

const (
	MOD = 1e9 + 7
)
 
func numDecodings(s string) int {
	n := len(s)
	cur := 0      // dp[i]
	next := 1     // dp[i+1]
	nextNext := 0 // dp[i+2]
	for i := n - 1; i >= 0; i-- {
		if s[i] == '0' {
			cur = 0
		} else {
			if s[i] == '*' {
				cur = 9 * next
			} else {
				cur = next
			}
			if i+1 < n {
				if s[i] != '*' {
					if s[i+1] != '*' {
						if int(s[i]-'0')*10+int(s[i+1]-'0') <= 26 {
							cur += nextNext
						}
					} else {
						if s[i] == '1' {
							cur += 9 * nextNext
						} else if s[i] == '2' {
							cur += 6 * nextNext
						}
					}
				} else {
					if s[i+1] != '*' {
						if s[i+1] <= '6' {
							cur += 2 * nextNext
						} else {
							cur += nextNext
						}
					} else {
						// 11~26
						cur += 15 * nextNext
					}
				}
			}
			cur %= MOD
		}
		// 从后往前走
		nextNext = next
		next = cur
	}
	return next
}

题目5.丑数 II §

题目描述 §

给你一个整数 n，请你找出并返回第 n 个 丑数。

丑数 就是质因子只包含 2、3 和 5 的正整数。

示例 1：

输入：n = 10

输出：12

解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1

输出：1

解释：1 通常被视为丑数。

提示：

• 1 <= n <= 1690

测试链接 §

264.丑数 II

思路 §

第一个抽数是 1，从 1 开始，分别乘 2、乘 3、乘 5，得到 2、3、5，其中较小值是 2，所以 2 就是第二个丑数

然后对 1、2、3、5 分别乘 2、3、5，得到的数加上 1、2、3、5，其中大于第二个丑数 2 的 最小数就是第三个丑数

以此类推

可以定义三个指针代表乘 2、乘 3、乘 5，一直往后跳就可以了

答案 §

func nthUglyNumber(n int) int {
	// dp[i]: 第 i 个丑数是啥
	// dp[0] 不用
	dp := make([]int, n+1)
	dp[1] = 1
	p2, p3, p5 := 1, 1, 1 // 三个指针
	v2, v3, v5, cur := 0, 0, 0, 0
	for i := 2; i <= n; i++ {
		v2 = dp[p2] * 2
		v3 = dp[p3] * 3
		v5 = dp[p5] * 5
		cur = min(v2, v3, v5)
		// 哪个被选中，下一个丑数只会更大，就往后跳
		if cur == v2 {
			p2++
		}
		if cur == v3 {
			p3++
		}
		if cur == v5 {
			p5++
		}
		dp[i] = cur
	}
	return dp[n]
}

复杂度 §

• 时间间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题目6.最长有效括号 §

题目描述 §

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：

输入：s = "(()"

输出：2

解释：最长有效括号子串是 "()"

示例 2：

输入：s = ")()())"

输出：4

解释：最长有效括号子串是 "()()"

示例 3：

输入：s = ""

输出：0

提示：

• 0 <= s.length <= 3 * 10^4
• s[i] 为 '(' 或 ')'

测试链接 §

32.最长有效括号

思路 §

动态规划：子串必须以 i 位置的字符结尾的情况下，往左整体有效的最大长度

从左往右推，后面的答案可以利用到前面的答案

答案 §

最长有效括号

复杂度 §

• 时间间复杂度：$O(n)$
• 空间复杂度：$O(n)$

题目7.环绕字符串中唯一的子字符串 §

题目描述 §

定义字符串 base 为一个 "abcdefghijklmnopqrstuvwxyz" 无限环绕的字符串，所以 base 看起来是这样的：

• "...zabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcd....".

给你一个字符串 s，请你统计并返回 s 中有多少 不同 的 非空子串 也在 base 中出现。

示例 1：

输入：s = "a"

输出：1

解释：字符串 s 的子字符串 "a" 在 base 中出现。

示例 2：

输入：s = "cac"

输出：2

解释：字符串 s 有两个子字符串 ("a", "c") 在 base 中出现。

示例 3：

输入：s = "zab"

输出：6

解释：字符串 s 有六个子字符串 ("z", "a", "b", "za", "ab", "zab") 在 base 中出现。

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成

测试链接 §

467.环绕字符串中唯一的子字符串

思路 §

以 26 个小写英文字母建立 dp 表，而不是字符串 s 的结尾，很巧妙，直接就不用考虑去重了

答案 §

func findSubstringInWraproundString(s string) int {
	n := len(s)
	// dp[i]: s 中必须以 i+'a' 结尾的子串，最大延伸长度是多少
	dp := make([]int, 26) // 小写英文字母
	dp[s[0]-'a'] = 1
	cur, prev := 0, 0
	length := 1
	for i := 1; i < n; i++ {
		cur = int(s[i] - 'a')
		prev = int(s[i-1] - 'a')
		if prev == 25 && cur == 0 || prev+1 == cur {
			length++
		} else {
			length = 1
		}
		dp[cur] = max(dp[cur], length)
	}
	ans := 0
	// 最大延伸长度就是不同非空子串的个数（以结尾）
	// 如：ab，同非空子串（以结尾）：ab、b
	// 直接就不用考虑去重了，很巧妙
	for _, val := range dp {
		ans += val
	}
	return ans
}

复杂度 §

• 时间间复杂度：$O(n)$，$n$ 是字符串 s 的长度，字符串 base 长度为正无穷
• 空间复杂度：$O(n)$

题目8.不同的子序列 II §

题目描述 §

给定一个字符串 s，计算 s 的 不同非空子序列 的个数。因为结果可能很大，所以返回答案需要对 10^9 + 7 取余 。

字符串的 子序列 是经由原字符串删除一些（也可能不删除）字符但不改变剩余字符相对位置的一个新字符串。

• 例如，"ace" 是 "abcde" 的一个子序列，但 "aec" 不是。

示例 1：

输入：s = "abc"

输出：7

解释：7 个不同的子序列分别是 "a", "b", "c", "ab", "ac", "bc", 以及 "abc"。

示例 2：

输入：s = "aba"

输出：6

解释：6 个不同的子序列分别是 "a", "b", "ab", "ba", "aa" 以及 "aba"。

示例 3：

输入：s = "aaa"

输出：3

解释：3 个不同的子序列分别是 "a", "aa" 以及 "aaa"。

提示：

• 1 <= s.length <= 2000
• s 仅由小写英文字母组成

测试链接 §

940.不同的子序列 II

思路 §

答案 §

const (
	MOD = 1e9 + 7
)
 
func distinctSubseqII(s string) int {
	n := len(s)
	// 有多少个子序列是以 'a'-i 结尾的
	cnt := make([]int, 26)
	// 有多少个不同的子序列
	all := 1    // 一开始有一个空集子序列
	newAdd := 0 // 每遍历到一个位置，新增的子序列个数
	for i := 0; i < n; i++ {
		newAdd = (all - cnt[s[i]-'a'] + MOD) % MOD
		cnt[s[i]-'a'] = (cnt[s[i]-'a'] + newAdd) % MOD
		all = (all + newAdd) % MOD
	}
	return (all - 1 + MOD) % MOD // 减去空集
}

复杂度 §

• 时间间复杂度：$O(n)$
• 空间复杂度：$O(1)$