题目来自：Leetcode专项学习计划——动态规划（基础版），共 50 道题。
本文章只记录当前（2024.05.22）掌握得不好的题目，共 16 道，完整的题单请参考上面的链接。
删除并获得点数
740. 删除并获得点数
1
2
3
4
5
6
7
8
|
func main() {
nums := []int{2, 2, 3, 3, 3, 4}
r := deleteAndEarn(nums)
fmt.Println(r) // 3
}
func deleteAndEarn(nums []int) int {
// ......
}
|
分析
使用 sum 数组存放每个相同元素值的和，找到 nums 中的最大值 maxVal。
开辟空间为 maxVal+1 的 sum 数组，数组下标表示元素值，数组值表示该元素值的和。
这里使用数组而不是 map 的原因是，数组下标是自动有序的，不用再进行排序。
现在将问题转换为打家劫舍问题（不能选择 sum 数组中两个相邻的元素）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
func deleteAndEarn(nums []int) int {
maxVal := nums[0]
for i := 0; i < len(nums); i++ {
if nums[i] > maxVal {
maxVal = nums[i]
}
}
sum := make([]int, maxVal+1)
for _, num := range nums { // 这里的处理是很巧妙的
sum[num] += num
}
rob := func(sum []int) int { // 计算打家劫舍问题能获得的最大金额
dp := make([]int, len(sum)) // dp[i]表示考虑0到i位置，最大能获得的金额
dp[0], dp[1] = sum[0], max(sum[0], sum[1])
for i := 2; i < len(sum); i++ {
dp[i] = max(dp[i-2]+sum[i], dp[i-1])
}
return dp[len(sum)-1]
}
return rob(sum)
}
|
改进：
对上面方法的改进，dp 数组改为迭代变化的两个变量。
1
2
3
4
5
6
7
8
9
10
11
12
|
func deleteAndEarn(nums []int) int {
// 前面部分省略......
// 将dp数组改为迭代变化的变量
rob := func(sum []int) int {
first, second := sum[0], max(sum[0], sum[1])
for i := 2; i < len(sum); i++ {
first, second = second, max(first+sum[i], second) // 将first和second变量指针后移
}
return second
}
return rob(sum)
}
|
最大正方形
221. 最大正方形
1
2
3
4
5
6
7
8
9
10
11
12
|
func main() {
matrix := [][]byte{{'1', '0', '1', '0', '0'},
{'1', '0', '1', '1', '1'},
{'1', '1', '1', '1', '1'},
{'1', '0', '0', '1', '0'}}
//matrix := [][]byte{{'0', '1'}}
r := maximalSquare(matrix)
fmt.Println(r) // 4
}
func maximalSquare(matrix [][]byte) int {
//......
}
|
分析
参考了答案，这里的递推表达式是非常关键的。
参考：1277. 统计全为 1 的正方形子矩阵的官方题解
dp[i][j] 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
func maximalSquare(matrix [][]byte) int {
maxSide := 0 // 最大的正方形边长
m := len(matrix)
n := len(matrix[0])
dp := make([][]int, m)
// 初始化dp数组
for i := 0; i < m; i++ {
dp[i] = make([]int, n)
for j := 0; j < n; j++ {
if matrix[i][j] == '1' {
dp[i][j] = 1
maxSide = 1 // 当matrix数组中出现1时，maxSide更新为1
}
}
}
for i := 1; i < m; i++ {
for j := 1; j < n; j++ {
if matrix[i][j] == '1' {
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
maxSide = max(maxSide, dp[i][j])
}
}
}
return maxSide * maxSide
}
|
最长递增子序列的个数
本题过于复杂，暂时先跳过。
最长数对链
646. 最长数对链
1
2
3
4
5
6
7
8
|
func main() {
pairs := [][]int{{1, 2}, {7, 8}, {4, 5}}
r := findLongestChain(pairs)
fmt.Println(r) // 3
}
func findLongestChain(pairs [][]int) int {
// ......
}
|
分析
方法1：贪心算法
参考了官方题解：要挑选最长数对链的第一个数对时，最优的选择是挑选第二个数字最小的，这样能给挑选后续的数对留下更多的空间。
先按照 pairs 数组的第 1 维进行升序排列，题目已经说明 pairs 数组第 0 维的值小于第 1 维的值。
按照上面这样排序之后，只需要满足下一个数对的 1 位置值大于下一个数对的 0 位置值，就可以将 count++。
这样得到的 count 就是要求的最大数对数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func findLongestChain(pairs [][]int) int {
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][1] < pairs[j][1]
})
count := 0
// 这样写是不正确的，因为中间有些数对是不选择的，如：pairs = [[1,2], [2,3], [3,4]]
// 中间的[2,3]就是不选择的，就不能参与判断，我们应该只让选择的数对参与判断。
// 用一个变量cur来记录上一个已经选择数对1位置的值，而不是变量pairs数组的每一个位置。
//for i := 1; i < len(pairs); i++ {
// if pairs[i][0] > pairs[i-1][1] {
// count++
// }
//}
cur := math.MinInt
for _, p := range pairs {
if cur < p[0] {
cur = p[1] // 使用cur记录上一个数对1位置的值
count++
}
}
return count
}
|
方法2：动态规划
dp[i] 表示以 pairs[i] 结尾的最长数对链的长度。
使用 j 遍历 0 到 i-1 位置的所有元素，如果当前数对的左边界大于前一个数对的右边界，则可以组成数对链
即：dp[i]=max(dp[i], dp[j]+1)。
在计算 dp 数组值之前，需要对 pairs 数组按照左边界排序
初始化 dp 数组：每个数对本身至少可以形成一个长度为 1 的数对链，所以 dp[i]=1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func findLongestChain(pairs [][]int) int {
maxLen := 1
sort.Slice(pairs, func(i, j int) bool {
return pairs[i][0] < pairs[j][0]
})
dp := make([]int, len(pairs))
for i := range dp {
dp[i] = 1
}
for i := 0; i < len(pairs); i++ {
for j := 0; j < i; j++ { // j遍历0到i-1位置的元素
if pairs[i][0] > pairs[j][1] { // 如果当前数对的左边界大于前一个数对的右边界，则可以组成数对链
dp[i] = max(dp[i], dp[j]+1)
}
}
maxLen = max(maxLen, dp[i])
}
return maxLen
}
|
最长定差子序列
本题较为复杂，建议多加理解和练习。
1218. 最长定差子序列
1
2
3
4
5
6
7
8
9
|
func main() {
arr := []int{1, 3, 5, 8}
difference := 2
r := longestSubsequence(arr, difference)
fmt.Println(r) // 3
}
func longestSubsequence(arr []int, difference int) int {
// ......
}
|
分析
普通动态规划：
自己写的版本，时间复杂度为 $O(n^2)$。逻辑上是正确的，但存在测试用例运行超时，说明时间复杂度还需要进一步优化。
dp[i] 表示以 arr[i] 结尾的数组的最长定长子序列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func longestSubsequence(arr []int, difference int) int {
maxLen := 1
dp := make([]int, len(arr))
for i := range dp {
dp[i] = 1
}
for i := 1; i < len(arr); i++ {
for j := i - 1; j >= 0; j-- {
if arr[j] == arr[i]-difference { // 从右往左查找i位置左侧最近的一个arr[j]，但当数组很长且一直没有找到满足条件的元素时，运行时间就会很长。在Leetcode上提交，运行超时：测试用例通过了，但耗时太长。
dp[i] = max(dp[i], dp[j]+1)
maxLen = max(maxLen, dp[i])
break
}
}
}
fmt.Println(dp)
return maxLen
}
|
改进：map存放dp数组的值
参考了答案，使用 map 来对上面的方法进行改进。这里使用 map 来处理还是比较巧妙的，值得学习。
由于我们只需要找到左侧第 1 个符合条件的元素，所以我们使用 map 存放以 nums[i] 结尾的数组的最长定差子序列的长度。
1
2
3
4
5
6
7
8
9
|
func longestSubsequence(arr []int, difference int) int {
maxLen := 1
dp := make(map[int]int)
for _, num := range arr {
dp[num] = dp[num-difference] + 1
maxLen = max(maxLen, dp[num])
}
return maxLen
}
|
最长等差数列
1027. 最长等差数列
1
2
3
4
5
6
7
8
|
func main() {
nums := []int{9, 4, 7, 2, 10}
r := longestArithSeqLength(nums)
fmt.Println(r) // 3。最长等差数列为：[4,7,10]
}
func longestArithSeqLength(nums []int) int {
// ......
}
|
分析
本题和 最长定差子序列 差不多，不同的地方在于两个元素之间的差值不是固定的，而是变化的。
我们先获取 nums 数组的最小值 minVal 和最大值 maxVal，计算差值 diff=maxVal-minVal。
元素之间差值的范围就是 -diff 到 diff，我们需要遍历所有可能的差值。
也就是在 最长定差子序列 的基础上，多套一层循环，遍历不同的 diff 值。
普通动态规划代码：
这样写有 3 层 for 循环，会导致运行超时，还是需要和 最长定差子序列 一样，将里面的两层 for 循环改成 map 存放以 nums[i] 结尾的数组的最长等差数列的长度。
还需要注意的是，为了不让不同的 diff 之间互相影响，我们应该在遍历不同的 diff 时，重新初始化 dp 数组。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
func longestArithSeqLength(nums []int) int {
minVal, maxVal, maxLen := nums[0], nums[0], 1
for _, num := range nums[1:] {
if num < minVal {
minVal = num
} else if num > maxVal {
maxVal = num
}
}
for diff := minVal - maxVal; diff <= maxVal-minVal; diff++ {
dp := make([]int, len(nums)) // 当diff不同时，需要重新初始化dp数组，为了不被前一个diff的dp数组影响
for i := range dp {
dp[i] = 1
}
for i := 1; i < len(nums); i++ {
for j := i - 1; j >= 0; j-- {
if nums[j] == nums[i]-diff { // 从右往左查找i位置左侧最近的一个arr[j]
dp[i] = max(dp[i], dp[j]+1)
maxLen = max(maxLen, dp[i])
break
}
}
}
}
return maxLen
}
|
改进：map存放dp数组的值
和 最长定差子序列 一样，将里面的两层 for 循环改成 map 存放以 nums[i] 结尾的数组的最长等差数列的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func longestArithSeqLength(nums []int) int {
// 求最大值和最小值的代码和前面一样，略。
numDiff := maxVal - minVal
for diff := -numDiff; diff <= numDiff; diff++ {
// 在这里使用map对上面的方法进行改进
dp := make(map[int]int, maxVal+1) // 这里给出map的初始容量，防止频繁地扩容
for _, num := range nums {
dp[num] = dp[num-diff] + 1
maxLen = max(maxLen, dp[num])
}
}
return maxLen
}
|
俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题
1
2
3
4
5
6
7
8
|
func main() {
envelopes := [][]int{{5, 4}, {6, 7}, {2, 3}, {2, 4}}
r := maxEnvelopes(envelopes)
fmt.Println(r) // 3
}
func maxEnvelopes(envelopes [][]int) int {
// ......
}
|
分析
计算逻辑是正确的，但第 85 个测试用例运行超时了，说明时间复杂度过高。
本题的 $1 <= envelopes.length <= 10^5$，说明如果时间复杂度是 $O(n^2)$，肯定会运行超时。
本题需要考虑两个方面，下一个元素的 0 位置（w）和 1 位置（h）都必须大于前一个元素。
我们先按照 envelopes 数组 0 位置的元素（w）进行升序排列，我们要根据 w 选择最大递增子数组。
但存在 w 相同，但 h 不同的情况，如：[1,1], [1,2], [1,3], [1,4]，这时候我们应该如何确定我们的选择规则呢？
根据题目的要求，我们也需要根据 h 选择最大递增子数组。
由于上面的 4 种情况我们只能选择 1 种，所以为了不让选择的结果出现多个 w 相同，但 h 不同的情况，当 w 相同时，我们要让 envelopes 数组根据 h 降序排列（这样根据 h 选择的最大递增子数组长度就只能是 1 了）
排序完成后，我们就可以忽略 w 维度，只考虑 h 维度，选择 envelopes 数组的最大递增子数组了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
func maxEnvelopes(envelopes [][]int) int {
sort.Slice(envelopes, func(i, j int) bool {
if envelopes[i][0] != envelopes[j][0] {
return envelopes[i][0] < envelopes[j][0] // 按w升序
}
return envelopes[i][1] > envelopes[j][1] // 当w相同时，按h降序
})
maxLen := 1
dp := make([]int, len(envelopes))
for i := range dp {
dp[i] = 1
}
for i := 0; i < len(envelopes); i++ {
for j := 0; j < i; j++ {
if envelopes[j][1] < envelopes[i][1] {
dp[i] = max(dp[i], dp[j]+1)
maxLen = max(maxLen, dp[i])
}
}
}
return maxLen
}
|
对上面的方法进行优化，使用二分查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func maxEnvelopes(envelopes [][]int) int {
// 前面排序envelopes数组的代码相同，省略。
// 参考：https://leetcode.cn/problems/russian-doll-envelopes/solutions/633231/e-luo-si-tao-wa-xin-feng-wen-ti-by-leetc-wj68/
var dp []int // 使用dp记录当前符合条件的h值
for _, envelope := range envelopes {
h := envelope[1] // 新插入到数组的信封高度为h，对原dp数组进行二分查找
// 由题意可知，dp数组中的元素是单调递增的，使用sort.SearchInts(dp,h)查找h在原数组中应该插入的位置
// 如果返回值小于dp数组的长度，说明插入位置在dp数组的中间，更新该位置的值为h
// 如果返回值等于dp数组的长度，说明应该将h添加到dp数组的末尾
if i := sort.SearchInts(dp, h); i < len(dp) {
dp[i] = h
} else {
dp = append(dp, h)
}
}
return len(dp)
}
|
找出到每个位置为止最长的有效障碍赛跑路线
【困难】
1964. 找出到每个位置为止最长的有效障碍赛跑路线
1
2
3
4
5
6
7
8
9
|
func main() {
obstacles := []int{1, 2, 3, 2}
//obstacles := []int{5, 1, 5, 5, 1, 3, 4, 5, 1, 4} // [1,1,2,3,2,3,4,5,3,5]
r := longestObstacleCourseAtEachPosition(obstacles)
fmt.Println(r) // [1,2,3,3]
}
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
// ......
}
|
分析
普通 dp：超时
本题的 $1 <= n <= 10^5$，说明如果时间复杂度是 $O(n^2)$，肯定会运行超时。
必须包含最后一个障碍，后一个障碍的高度必须大于等于前一个障碍。dp[i] 表示到第 i 位置，最长障碍长度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
dp := make([]int, len(obstacles))
for i := range dp {
dp[i] = 1
}
for i := 1; i < len(obstacles); i++ {
for j := 0; j < i; j++ {
if obstacles[j] <= obstacles[i] {
dp[i] = max(dp[i], dp[j]+1)
}
}
}
return dp
}
|
改进：二分查找
参考：Golang + 贪心 + 二分。
理解得还不是很好，需要再多加理解和练习。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
func longestObstacleCourseAtEachPosition(obstacles []int) []int {
n := len(obstacles)
var ans = make([]int, n) // 最后返回的目标数组
var dp = make([]int, n+1) // 维护一个单调不减数组，dp[i]表示到i-1位置，能构成赛跑路线的数组障碍物值
length := 1 // dp数组的有效长度
ans[0] = 1
dp[1] = obstacles[0] // dp[0]是没有意义的，所以从下标1开始初始化
for i := 1; i < n; i++ {
fmt.Println("dp:", dp) // 这里可以打印出dp数组的值，可以看出dp数组是不断迭代变化的
if obstacles[i] >= dp[length] { // 遇到的元素大于等于dp数组的最后一个元素（有效范围内），将obstacles[i]添加到dp数组中
length++
dp[length] = obstacles[i]
ans[i] = length
} else {
l, r, pos := 1, length-1, 0
for l <= r {
middle := (l + r) / 2
if dp[middle] > obstacles[i] {
r = middle - 1
} else {
pos = middle // pos就是obstacles[i]应该插入的位置
l = middle + 1 // 当dp[middle]和obstacles[i]相等时，也要继续将l右移，因为我们要找到相等时的最后一个元素位置
}
}
ans[i] = pos + 1 // 长度为下标pos加1
if dp[pos+1] > obstacles[i] { // 如果应该插入位置的后一个位置的dp数组值大于插入的obstacles[i]，如果大于，则需要将该位置值更新为obstacles[i]的值，以保持dp数组的单调不减性质。
dp[pos+1] = obstacles[i]
}
}
}
return ans
}
|
让字符串成为回文串的最少插入次数
【困难】
1312. 让字符串成为回文串的最少插入次数
本题较简单，和【困难】的难度不匹配。
1
2
3
4
5
6
7
8
9
10
|
func main() {
s := "mbadm"
//s := "leetcode" // eee
//s := "zjveiiwvc" // viiv
r := minInsertions(s)
fmt.Println(r) // 2
}
func minInsertions(s string) int {
// ......
}
|
分析
本题求最少添加多少个字符可以让 s 变成回文字符串。
可以转换为最少删除多少个字符串可以让 s 变成回文字符串，因为添加字符的数量和删除字符的数量是相等的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
func minInsertions(s string) int {
dp := make([][]int, len(s))
for i := range dp {
dp[i] = make([]int, len(s))
for j := 0; j < len(s); j++ { // 初始化dp数组，当i==j时，dp数组值为0，否则，值为len(s)-1
if i == j {
dp[i][j] = 0
} else {
dp[i][j] = len(s) - 1
}
}
}
for i := len(s) - 1; i >= 0; i-- {
for j := i + 1; j < len(s); j++ {
if s[i] == s[j] {
if j == i+1 {
dp[i][j] = 0
} else {
dp[i][j] = dp[i+1][j-1]
}
} else {
dp[i][j] = min(dp[i+1][j]+1, dp[i][j-1]+1)
}
}
}
return dp[0][len(s)-1]
}
|
不同的二叉搜索树II
95. 不同的二叉搜索树 II
1
2
3
4
5
6
7
8
9
10
11
12
13
|
type TreeNode struct {
Val int
left *TreeNode
right *TreeNode
}
func main() {
n := 3
r := generateTrees(n)
fmt.Println(r)
}
func generateTrees(n int) []*TreeNode {
// ......
}
|
分析
本题需要构造出 n 个结点的所有 BST。
以 n=3 为例，可以有下面几种情况：
-
选第 0 个位置为根结点，则右侧有 2 个结点；
-
选第 1 个位置为根结点，则左侧有 1 个结点，右侧有 1 个结点；
-
选第 2 个位置为根结点，则左侧有 2 个结点，右侧有 0 个结点。
可以定义一个函数 genBST，参数为 start 和 end，表示需要生成 BST 的左右区间，返回值为生成的 BST 集合。
然后用 i 遍历 1到 n，每次选择 i 作为根结点，然后左右区间递归地调用 genBST 函数，最后组成所有的 BST 集合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func generateTrees(n int) []*TreeNode {
if n == 0 {
return nil
}
return genBST(1, n)
}
func genBST(start, end int) []*TreeNode {
if start > end {
return []*TreeNode{nil}
}
var allTree []*TreeNode
for i := start; i <= end; i++ {
leftTree := genBST(start, i-1) // 在i位置处分成两个部分，左右分别构造BST
rightTree := genBST(i+1, end)
for _, left := range leftTree {
for _, right := range rightTree {
curTree := &TreeNode{i, left, right}
allTree = append(allTree, curTree)
}
}
}
return allTree // 逐层向上返回
}
|
二叉树中的最大路径和
【困难】
124. 二叉树中的最大路径和
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func main() {
node1 := &TreeNode{15, nil, nil}
node2 := &TreeNode{7, nil, nil}
node3 := &TreeNode{20, node1, node2}
node4 := &TreeNode{9, nil, nil}
node5 := &TreeNode{-10, node4, node3}
// -10
// 9 20
// 15 7
r := maxPathSum(node5)
fmt.Println(r) // 42。选择的路径为：15->20->7。
}
func maxPathSum(root *TreeNode) int {
// ......
}
|
分析
本题的最大路径可能有两种情况：
-
路径在同一个二叉树；
-
路径不在同一个二叉树。
我们计算每个子树的最大贡献，最大贡献 和 最大路径和 是不一样的。
最大贡献用于向上返回，用于上层结点进行计算，同时为了统计出 情况1 的最大值，我们维护一个全局变量maxSum，统计出 情况1 的最大路径和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
func maxPathSum(root *TreeNode) int {
maxSum := math.MinInt
var maxGain func(root *TreeNode) int
maxGain = func(root *TreeNode) int {
if root == nil {
return 0
}
leftGain := max(maxGain(root.Left), 0) // 小于0时，我们就不统计了
rightGain := max(maxGain(root.Right), 0)
maxSum = max(maxSum, leftGain+rightGain+root.Val) // 更新路径在同一个二叉树上时的最大路径和
return root.Val + max(leftGain, rightGain) // 向上返回贡献值，只能选择左孩子或者右孩子中的一个
}
maxGain(root)
return maxSum
}
|
解决智力问题
2140. 解决智力问题
1
2
3
4
5
6
7
8
9
10
|
func main() {
questions := [][]int{{3, 2}, {4, 3}, {4, 4}, {2, 5}} // 5
//questions := [][]int{{1, 1}, {2, 2}, {3, 3}, {4, 4}, {5, 5}} // 7
//questions := [][]int{{38, 1}, {60, 2}} // 60
r := mostPoints(questions)
fmt.Println(r) // 5
}
func mostPoints(questions [][]int) int64 {
// ......
}
|
分析
方法1：动态规划+双重循环
计算逻辑是正确的，但第 48 个测试用例超时。
本题的 $1 <= questions.length <= 10^5$，说明不能使用时间复杂度为 $O(n^2)$ 的算法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func mostPoints(questions [][]int) int64 {
// dp[i]表示考虑到i位置，最多能获得的分数
n := len(questions)
dp := make([]int, n)
for i := range dp {
dp[i] = questions[i][0]
}
maxScore := questions[0][0]
for i := 1; i < n; i++ {
for j := 0; j < i; j++ {
if i > j+questions[j][1] {
dp[i] = max(dp[i], dp[j]+questions[i][0])
}
maxScore = max(maxScore, dp[i])
}
}
fmt.Println(dp)
return int64(maxScore)
}
|
方法2：从后往前遍历dp数组
在 i 位置，我们可以选择 解决 和 不解决 第 i 道题。
这种选择会影响到后面 dp 数组的值，但不会影响前面 dp 数组的值。
如果我们从前往后递推 dp 数组，那么在 i 位置，就需要遍历 0 到 i-1 位置是否处于冷冻期，来计算 i 位置 dp 数组的值，就需要双重循环。
为了能让单层循环就能解决本题，我们可以反方向进行递推，从后往前依次计算 dp 数组。
dp 数组表示 解决第 i 道题目及以后的题目可以获得的最高分数。（和前面的定义方向相反）
在 i 位置，我们可以选择 解决 和 不解决 第 i 道题。
-
解决：questions[i][0] + dp[ i+questions[i][1]+1 ]；
-
不解决：dp[i+1]。
则：dp[i]=max(questions[i][0]+dp[i+questions[i][1]+1], dp[i+1])
这里还需要注意 i+questions[i][1]+1 下标范围不能超过 n-1。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func mostPoints(questions [][]int) int64 {
n := len(questions)
dp := make([]int, n)
dp[n-1] = questions[n-1][0]
for i := n - 2; i >= 0; i-- { // 从n-2位置开始
if i+questions[i][1]+1 > n-1 { // 超出n-1的范围，dp[i+questions[i][1]+1]的值置为0
dp[i] = max(questions[i][0], dp[i+1])
} else {
dp[i] = max(questions[i][0]+dp[i+questions[i][1]+1], dp[i+1])
}
}
return int64(dp[0])
}
|
统计构造好字符串的方案数
2466. 统计构造好字符串的方案数
1
2
3
4
5
6
7
8
9
|
func main() {
low, high, zero, one := 2, 3, 1, 2 // 5
//low, high, zero, one := 3, 3, 1, 1 // 8
r := countGoodStrings(low, high, zero, one)
fmt.Println(r) // 5。好字符串为"00"，"11"，"000"，"110"和"011"。
}
func countGoodStrings(low int, high int, zero int, one int) int {
// ......
}
|
分析
在每次操作时，可以选择添加 zero 次 0 或者 one 次 1。
dp[i] 表示长度为 i 的字符串的构造方案数。
参考了答案：爬楼梯换皮。发现本题和 爬楼梯 是差不多的，第 i 个位置，有两个可能性：
-
第 i-zero 位置添加 zero 个 0；
-
第 i-one 位置添加 one 个 1。
递推表达式为：dp[i]=dp[i-zero]+dp[i-one]。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func countGoodStrings(low int, high int, zero int, one int) int {
const mod int = 1e9 + 7
res := 0
dp := make([]int, high+1)
dp[0] = 1
for i := 1; i <= high; i++ {
//dp[i] = dp[i-zero] + dp[i-one] // 不能直接这样写，要注意下标的范围
if i >= zero {
dp[i] = dp[i-zero] % mod
}
if i >= one {
dp[i] = (dp[i] + dp[i-one]) % mod
}
if i >= low { // 统计长度大于low的字符串构造方案总和
res = (res + dp[i]) % mod
}
}
return res
}
|
解码方法
91. 解码方法
1
2
3
4
5
6
7
8
9
|
func main() {
s := "226"
//s := "301" // 0
r := numDecodings(s)
fmt.Println(r) // 3
}
func numDecodings(s string) int {
// ......
}
|
分析
本题整体来说比较简单，但需要注意能成功解码的条件。
dp[i] 表示到 i 位置，解码方法的数量。
在 i 位置，dp[i] 可以根据 dp[i-1] 和 dp[i-2] 推断计算出来。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
func numDecodings(s string) int {
if s[0] == '0' {
return 0
}
if len(s) == 1 {
return 1
}
mapping := make(map[string]bool) // 保存所有存在编码的字符串
for i := 1; i <= 26; i++ {
mapping[strconv.Itoa(i)] = true
}
dp := make([]int, len(s))
dp[0] = 1
if s[1] == '0' && !mapping[s[:2]] {
return 0
}
if mapping[s[0:2]] && mapping[s[1:2]] {
dp[1] = 2
} else {
dp[1] = 1
}
for i := 2; i < len(s); i++ {
if s[i] == '0' && !mapping[s[i-1:i+1]] { // 如果i位置为0，那么s[i-1:i+1]必须合法才能解码
return 0
}
if mapping[s[i-1:i+1]] && mapping[s[i:i+1]] { // 注意这里需要添加条件，检查i位置前面1位和2位的字符串是否合法
dp[i] = dp[i-2] + dp[i-1]
} else if mapping[s[i-1:i+1]] {
dp[i] = dp[i-2]
} else if mapping[s[i:i+1]] {
dp[i] = dp[i-1]
}
}
return dp[len(s)-1]
}
|
最低票价
983. 最低票价
1
2
3
4
5
6
7
8
9
|
func main() {
days := []int{1, 4, 6, 7, 8, 20}
costs := []int{2, 7, 15}
r := mincostTickets(days, costs)
fmt.Println(r) // 11。第1天买1天的，第4天买7天的，第20天买1天的，2+7+2=11。
}
func mincostTickets(days []int, costs []int) int {
// ......
}
|
分析
dp[i] 表示旅行到第 i 天（下标从 1 开始）时需要的最低票价。
这里需要使用到贪心算法的思想，如果第 i 天不是必须出行（也就是 i 不在 days 数组中），那么第 i 天就不需要买票，即：dp[i]=dp[i-1]。
如果 i 在 days 数组中，则我们可以根据第 i-1、i-7 和 i-30 天的票价推导出第 i 天的票价。
即：dp[i]=min(dp[i-1]+costs[0], dp[i-7]+costs[1], dp[i-30]+costs[2])。
最后，dp[len(dp)-1] 就是我们要求的目标值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func mincostTickets(days []int, costs []int) int {
dp := make([]int, days[len(days)-1]+1)
fmt.Println(len(dp))
dayIndex := 0 // 标记下一个必须出行日期的下标
for i := 1; i < len(dp); i++ {
if i != days[dayIndex] { // 第i天不用出行
dp[i] = dp[i-1]
} else {
//dp[i] = min(dp[i-1]+costs[0], dp[i-7]+costs[1], dp[i-30]+costs[2]) // 由于这里下标可能小于0，所以采用下面的写法
dp[i] = min(dp[max(0, i-1)]+costs[0],
dp[max(0, i-7)]+costs[1],
dp[max(0, i-30)]+costs[2])
dayIndex++
fmt.Println(dp)
}
}
return dp[len(dp)-1]
}
|
多米诺和托米诺平铺
790. 多米诺和托米诺平铺
1
2
3
4
5
6
7
8
9
10
|
func main() {
n := 3
r := numTilings(n)
fmt.Println(r) // 5
// index: 1 2 3 4 5 6 7
// result: 1 2 5 11 24 53 117
}
func numTilings(n int) int {
// ......
}
|
分析
参考了答案：多米诺和托米诺平铺——方法一：动态规划
考虑第 i 列的几种情况
在第i列，存在下面几种情况：
- 一个正方形都没有覆盖，标记为 dp[i][0]；
- 只有上方的正方形被覆盖，标记为 dp[i][1]；
- 只有下方的正方形被覆盖，标记为 dp[i][2]；
- 上下的正方形都被覆盖，标记为 dp[i][3]。
现在要根据 dp[i-1] 的不同情况，再添加上一个 多米诺形 或 托米诺形，让第 i 个位置可以达成 i 位置的每种情况。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
func numTilings(n int) int {
const mod int = 1e9 + 7
dp := make([][4]int, n+1)
dp[0][3] = 1 // 这里的初始值也很重要
for i := 1; i <= n; i++ {
// 递推表达式最好结合图形来计算。
dp[i][0] = dp[i-1][3] % mod
dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % mod
dp[i][2] = (dp[i-1][0] + dp[i-1][1]) % mod
dp[i][3] = (((dp[i-1][0]+dp[i-1][1])%mod+dp[i-1][2])%mod + dp[i-1][3]) % mod
}
return dp[n][3]
}
|
最后的【动态规划-多维】部分需要升级 Plus 会员才能解锁。
2024年05月22日，除会员专属的题目外，其他所有题目都已练习一遍。
除去 最长递增子序列的个数 过于复杂，暂时跳过外，其他题目都应该完全掌握。
