动态规划

理论基础

动态规划，英文：Dynamic Programming，简称DP，如果某一问题有很多重叠子问题，使用动态规划是最有效的

动态规划中每一个状态一定是由上一个状态推导出来的，这一点就区分于贪心，贪心没有状态推导，而是从局部直接选最优的

对于动态规划问题，拆解为如下五步曲，这五步都搞清楚了，才能说把动态规划真的掌握了

dp数组以及下标的含义
递推公式
dp数组如何初始化
遍历顺序
举例推导（打印）dp数组

代码通过不了，自己先思考这三个问题：

这道题目我举例推导状态转移公式了么？
我打印dp数组的日志了么？
打印出来了dp数组和我想的一样么？

如果这灵魂三问自己都做到了，基本上这道题目也就解决了，或者更清晰的知道自己究竟是哪一点不明白，是状态转移不明白，还是实现代码不知道该怎么写，还是不理解遍历dp数组的顺序。

斐波那契数

509. 斐波那契数 - 力扣（LeetCode）

给定n，0 ≤ n ≤ 30，求斐波那契数，F(0) = 0，F(1) = 1，F(n) = F(n-1) + F(n-2)

先用简单题来加深对解题方法论的理解

确定dp[i]含义：第i个斐波那契数的值
递推公式：dp[i] = dp[i-1] + dp[i-2]
初始化：dp[0] = 0，dp[1] = 1
遍历顺序：从前往后
打印dp[i]：0 1 1 2 3 5 8 13 21 34 55

本题所求值的状态只依赖于前两个状态，所以可以压缩为两个变量保存状态即可，不需要记录整个序列

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func fib(n int) int {
    if n <= 1 {
        return n
    }
    dp := [2]int{0, 1} // 初始化
    for i := 2; i <= n; i++ {
        sum := dp[0] + dp[1] // 更新状态
        dp[0] = dp[1]        // 保存状态
        dp[1] = sum          // 保存状态
    }
    return dp[1]
}

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

本题也可以用递归来解

1
2
3
4
5
6


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

时间复杂度：$O(2^n)$
空间复杂度：$O(n)$，算上了编程语言中实现递归的系统栈所占空间

爬楼梯

70. 爬楼梯 - 力扣（LeetCode）

给定n作为台阶数，每次可以爬1阶或2阶，返回可以登顶的方法数

1阶：1种；2阶：2种；3阶：3种；4阶：5种

当前阶有几种方法到达依赖于它的前两个状态，这是一种递推的关系，所以可以用动态规划的思路来解决

dp[i]：到达第i个台阶的方法数
递推公式：dp[i] = dp[i-1] + dp[i-2]
初始化：dp[1] = 1，dp[2] = 2
遍历顺序：从前往后
打印dp[i]：1 2 3 5

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

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

本题和上一题斐波那契数一样，也可以优化空间只保存两个状态

进阶：爬楼梯:每次至多可爬m阶(1 ≤ m＜n)

使用最小花费爬楼梯

746. 使用最小花费爬楼梯 - 力扣（LeetCode）

给定一个整数数组，下标i表示从第i个台阶向上爬需要支付的费用，每次可以爬一阶或两阶，返回爬到顶部的最小花费；可以从前两个元素中任一个元素开始爬；顶部：最后一阶的下一个

dp[i]：爬到第i阶的最小总花费
递推公式：dp[i] = min(cost[i-1] + dp[i-1]，cost[i-2] + dp[i-2])
初始化：dp[0] = 0，dp[1] = 0
遍历顺序：从前往后

1
2
3
4
5
6
7
8


func minCostClimbingStairs(cost []int) int {
	dp := make([]int, len(cost)+1)
	dp[0], dp[1] = 0, 0
	for i := 2; i <= len(cost); i++ {
		dp[i] = min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2])
	}
	return dp[len(cost)]
}

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

本题也可以优化空间只保存两个状态

不同路径

62. 不同路径 - 力扣（LeetCode）

给定一个m排n列的网格，一次只能向下或向右走一格，问从左上角走到右下角有多少条不同的路径

起始处是下标00

dp[i][j]：从起点到下标ij的路径数
递推公式：dp[i][j] = dp[i][j-1] + dp[i-1][j]
初始化：dp[i][0] = 1 , dp[0][j] = 1
遍历顺序：从左往右，从上往下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1 // 每排第一个初始化为1（第一列初始化为1）
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1 // 每列第一个初始化为1（第一排初始化为1）
    }
    for i := 1; i < m; i++ { // 排
        for j := 1; j < n; j++ { // 列
            dp[i][j] = dp[i][j-1] + dp[i-1][j] // 取决于上一个和前一个
        }
    }
    return dp[m-1][n-1]
}

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

可以优化空间，用一维数组（也可以理解是滚动数组）就可以了

不同路径II

63. 不同路径 II - 力扣（LeetCode）

给定一个二维数组，表示网格及其中的障碍物，每次只能向右或向下走一格，问从左上走到右下有多少条不同的路径数

dp[i][j]：从起点到下标ij的路径数
递推公式：该点无障碍dp[i][j] = dp[i][j-1] + dp[i-1][j]；该点有障碍dp[i][j] = 0
初始化：第一排无障碍时dp[i][0] = 1，遇到障碍时后面全为0 ；第一列无障碍时dp[0][j] = 1，遇到障碍时下面全为0
遍历顺序：从左往右，从上往下

注意：首行首列初始化时一旦遇到障碍物，后面都不可达，全置0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func uniquePathsWithObstacles(obstacleGrid [][]int) int {
    m, n := len(obstacleGrid), len(obstacleGrid[0])
    dp := make([][]int, m)
    for i := range obstacleGrid {
        dp[i] = make([]int, n) // 初始化全部元素为0
    }
    // 初始化, 如果是障碍物, 后面就都是0, 不用循环了
    for i := 0; i < m && obstacleGrid[i][0] == 0; i++ { // 初始化列
        dp[i][0] = 1 // 每排第一个初始化为1（第一列初始化为1）
    }
    for j := 0; j < n && obstacleGrid[0][j] == 0; j++ { // 初始化排
        dp[0][j] = 1 // 每列第一个初始化为1（第一排初始化为1）
    }
    for i := 1; i < m; i++ { // 排
        for j := 1; j < n; j++ { // 列
            if obstacleGrid[i][j] != 1{
                dp[i][j] = dp[i][j-1] + dp[i-1][j] // 该点无障碍
            }	
        }
    }
    return dp[m-1][n-1]
}

时间复杂度：$O(n × m)$，n、m 分别为obstacleGrid 长度和宽度
空间复杂度：$O(n × m)$

Go语言中copy函数的源切片类型为引用类型时，拷贝的是引用；如果想 copy 多维切片中的每一维的元素，那么需要将目标切片每一维进行初始化再从源切片拷贝。注意是两步：先初始化，再拷贝

整数拆分

343. 整数拆分 - 力扣（LeetCode）

给定一个整数，将该整数拆分为多个整数的和并使这些整数的乘积最大化，返回该最大乘积

dp[i]：对i拆分，得到的最大乘积
递推公式：dp[i] = max(max(j × (i - j)，j × dp[i - j])，dp[i])
初始化：dp[0] = 0，dp[1] = 0，dp[2] = 1
遍历顺序：从前到后

注意：

拆分成两个数的乘积：j × (i - j)；拆分成三个数及三个数以上的乘积：j × dp[i-j]
最大乘积一定是在拆分成m个近似相同的数的集合里，所以内层循环可以在j<=i/2时终止
外层循环定好要求哪个数的最大乘积，内层循环从1开始拆分为两个数的乘积和三个及三个数以上的最大乘积进行比较，比较出两者中大的以后还要和本次外循环中之前的内循环得到的最大乘积比较，不断更新dp[i]，直到内层循环结束

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func integerBreak(n int) int {
    dp := make([]int, n+1)
    dp[0] = 0
    dp[1] = 0
    dp[2] = 1
    for i := 3; i <= n; i++ {
        for j := 1; j <= i/2; j++ {
            dp[i] = max(max(j*(i-j), j*dp[i-j]), dp[i])
        }
    }
    return dp[n]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

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

不同的二叉搜索树

96. 不同的二叉搜索树 - 力扣（LeetCode）

给定一个整数作为节点数，问能构成几种不同的二叉树

分析递推关系：

三个节点种类数 =（左0个节点种类数×右边两个节点种类数）+（左1个节点种类数×右1个节点种类数）+（左2个节点种类数×右0个节点种类数）；左/右两个节点种类数 = 两个节点时的种类数；左/右1个节点种类数 = 一个节点时种类数

两个节点种类数 = （左0个节点种类数×右1个节点种类数）+ （左1个节点种类数×右0个节点种类数）；左/右1个节点种类数 = 一个节点时种类数

一个节点种类数 = （左0个节点种类数×右0个节点种类数）；左/右0个节点种类数 = 0个节点时种类数

dp[i]：i个节点能构成的二叉树种类数
递推公式：dp[i] = Σ(dp[j] * dp[i-j-1]）
初始化：dp[0] = 1
遍历顺序：从小到大

注意：dp[0] = 1 =>1×任何数都不改变原数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func numTrees(n int) int {
    dp := make([]int, n+1)
    dp[0] = 1
    for i := 1; i <= n; i++ { // 定节点数
        for j := 0; j < i; j++ { // 求种类数
            dp[i] += dp[j] * dp[i-j-1]
        }
    }
    return dp[n]
}

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

01背包问题

46. 携带研究材料 - 卡码网（KamaCoder）

n种物品，每种物品有重量和价值，背包容量为w，每种物品只能用一次，求解装哪些物品使价值总和最大

二维dp数组解法：

dp[i][j]：任选物品0到i放进容量为j包的最大价值
递推公式：dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight(i)]+value(i))
初始化：第一列dp[i][0] = 0；第一排可以满足物品0的重量之前dp[0][j] = 0，可以满足物品0的重量之后dp[0][j] = value[i]
遍历顺序：从左到右，从上到下

不装i：dp[i-1][j]、装i：dp[i-1][j-weight(i)]+value(i)

i：第几排；j：第几列；dp[i-1][j]是由上一个元素得到，dp[i-1][j-weight(i)]是由左上方某个元素得到

	背包容量0	背包容量1	背包容量2	背包容量3	背包容量4
物品0	初始化	初始化	初始化	初始化	初始化
物品1	初始化	起始处
物品2	初始化				最大值

注意：

因为容量0算一列，所以应定义w+1列
内层循环中先检查背包能否放下i物品，若放不下则赋值为不放物品i的价值dp[i-1][j]

 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
36
37
38
39
40
41
42
43
44
45
46
47
48


package main

import "fmt"

func zeroOneBag() int {
    // 获取输入数据
    var n, w int
    fmt.Scanln(&n, &w)
    weight := make([]int, n)
    value := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scanf("%d", &weight[i])
    }
    fmt.Scanln() // 读取换行符（卡码网中无需该句，GOLAND中需要该句）
    for i := 0; i < n; i++ {
        fmt.Scanf("%d", &value[i])
    }
    // 核心代码
    dp := make([][]int, n)
    for i := range dp {
        dp[i] = make([]int, w+1) // 初始化全部元素为0（n排w+1列）
    }
    for j := range dp[0] {
        if j >= weight[0] {
            dp[0][j] = value[0] // 初始化第一排元素可以满足物品0重量的为物品0的价值
        }
    }
    for i := 1; i < n; i++ { // 定物品
        for j := 1; j <= w; j++ { // 遍历背包重量
            if j-weight[i] < 0 {
                dp[i][j] = dp[i-1][j] // 放不下物品i
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weight[i]]+value[i])
            }
        }
    }
    return dp[n-1][w]
}
func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

func main() {
    fmt.Println(zeroOneBag())
}

一维dp数组解法：

观察二维数组的递推公式可以发现，本层依赖于上一层，因此可以在本层进行计算，再将结果覆盖到上一层，故此用一维数组即可实现状态转移和保存

dp[j]：背包容量为j时的可装的最大价值
递推公式：dp[j] = max(dp[j]，dp[j-weight(i)]+value(i))
初始化：dp[0] = 0
遍历顺序：倒序，从右往左

注意：

递推公式中等号右边的dp[j]是上一层的值代表不装i
遍历顺序之所以倒序，是因为内层循环中逐个更新dp[j]，每个dp[j]都依赖于上一层的dp[j]，也就是之前的dp[j]，如果正序的话前面保存的上一层dp[j]会被之前的循环更新值，导致本层后面的dp[j]无法使用上一层的dp[j]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func zeroOneBag() int {
    dp := make([]int, w+1)
    dp[0] = 0
    for i := 0; i < n; i++ { // 定物品
        for j := w; j >= weight[i]; j-- { // 倒序遍历背包重量
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
        }
    }
    return dp[w]
}
func max(i, j int) int {
    if i > j {
        return i
    }
    return j
}

分割等和子集

416. 分割等和子集 - 力扣（LeetCode）

给定一个只包含正整数的非空数组，判断能否分割为两个元素和相等的子集

将数组中元素看作物品重量和价值，数组中元素和的一半看作背包容量；当背包容量为元素和一半时，若物品刚好能装满该容量，则说明能分割；背包容量/价值总和=元素和；由于重量=价值，所以当背包容量为元素和一半时，若所装物品价值和刚好等于元素和一半，则说明能分割

01背包问题：集合中每个元素只能使用一次

给定背包容量，能装满返回true，否则返回false

dp[j]：背包容量为j时的可装的最大价值
递推公式：dp[j] = max(dp[j]，dp[j-weight(i)]+value(i))
初始化：dp[0] = 0
遍历顺序：倒序，从右往左

注意：

当元素和为奇数时，直接返回false
最后的dp[j]：背包容量为元素一半时，所能装的最大价值，由于重量=价值，所以理论最大价值=最大重量，能装满就返回true，否则返回false

 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 canPartition(nums []int) bool {
    sum := 0 // 背包容量
    for i := range nums {
        sum += nums[i]
    }
    if sum%2 == 1 {
        return false // 元素和为奇数
    }
    dp := make([]int, sum/2+1) // 包容量 = 元素和一半
    dp[0] = 0
    for i := 0; i < len(nums); i++ { // 遍历物品
        for j := sum / 2; j >= nums[i]; j-- { // 倒序遍历背包容量
            dp[j] = max(dp[j], dp[j-nums[i]]+nums[i]) // 更新dp
            if j == sum/2 && dp[j] == sum/2 {
                return true // 包中价值 = 元素和一半 => 能分割
            }
        }
    }
    return false
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间复杂度：$O(n^2)$
空间复杂度：$O(n)$，虽然dp数组大小为一个常数，但是大常数

最后一块石头的重量II

1049. 最后一块石头的重量 II - 力扣（LeetCode）

给定一个整数数组，每个元素代表石头重量；每次取出两个石头粉碎，小石头会被粉碎掉，大石头新重量要减去小石头，若俩石头重量一样，则都被粉碎；重复此步骤；最后返回剩下的最后一块石头的最小重量，若不剩下石头，则返回0

将石头尽可能的分成重量相似的两堆，相撞后所剩的就是最小值

看作01背包问题：集合中每个元素只能使用一次，元素=重量=价值；背包容量=元素和一半时，所能装的最大价值就是一个堆；另一堆=元素和-元素和一半时所能装的最大价值；两堆相减所得即为所求相撞后所剩最小值

给定背包容量，求所能装的最大重量

dp[j]：背包容量为j时的可装的最大价值
递推公式：dp[j] = max(dp[j]，dp[j-weight(i)]+value(i))
初始化：dp[0] = 0
遍历顺序：倒序，从右往左

最后的dp[j]：背包容量为元素一半时，所能装的最大价值，由于重量=价值，所以理论最大价值=最大重量，也就是能装的最大重量（不一定装满）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func lastStoneWeightII(stones []int) int {
    sum := 0
    for i := range stones {
        sum += stones[i]
    }
    target := sum / 2
    dp := make([]int, target+1)
    for i := 0; i < len(stones); i++ { // 遍历物品
        for j := target; j >= stones[i]; j-- { // 倒序遍历包容量
            dp[j] = max(dp[j], dp[j-stones[i]]+stones[i])
        }
    }
    anther := sum - dp[target]
    return int(math.Abs(float64(anther) - float64(dp[target])))
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间复杂度：$O(m × n)$ , m是石头总重量（准确的说是总重量的一半），n为石头块数
空间复杂度：$O(m)$

目标和

494. 目标和 - 力扣（LeetCode）

给定一个非负整数数组和一个整数，可以给每个元素前加+或-，使数组元素和为给定整数，返回可以通过上述方法构造的表达式的数目

按回溯算法的组合总和写的话会超时，因为时间复杂度是指数级别的

分出两个集合：正数一个集合，负数一个集合；

正数集合和+负数集合和绝对值=数组和 => 负数集合和绝对值=数组和-正数集合和
正数集合和-负数集合和绝对值=target => 正数集合和-(数组和-正数集合和)=target
正数集合和 = (target+数组和)/2

在给定集合中挑出哪些元素可以使其和为正数组和，有多少种这样的组合就输出多少

若target+数组和为奇数，则说明无法构造出表达式，直接返回0

看作01背包问题：集合中每个元素只能使用一次，元素=重量=价值；当背包容量=(target+数组和)/2时，装满该包有多少种方法

dp[j]：背包容量为j时可以装满该包的方法数
递推公式：dp[j] += dp[j-weight[i]]
初始化：dp[0] = 1
遍历顺序：倒序，从右往左

注意：

dp[j] = dp[j-weight[i]]的含义：假设已经装了物品i，那么就有dp[j-weight(i)]种方法装满容量为j的背包：已经求出了有dp[j-weight(i)]种方法来装满容量为j-weight(i)的包了，现在再加上一个物品i，仍是dp[j-weight(i)]种方法装满容量为j的背包（dp[j] = dp[j-weight[i]]）
dp += dp[j-weight[i]]：例如：dp[j]，j 为5，
- 已经有一个1（nums[i]）的话，有 dp[4]种方法凑成容量为5的背包。
- 已经有一个2（nums[i]）的话，有 dp[3]种方法凑成容量为5的背包。
- 已经有一个3（nums[i]）的话，有 dp[2]中方法凑成容量为5的背包
- 已经有一个4（nums[i]）的话，有 dp[1]中方法凑成容量为5的背包
- 已经有一个5 （nums[i]）的话，有 dp[0]中方法凑成容量为5的背包
dp[0] = 1：若给定数组为[0]，target=0，由于0取正负都可以，所以最终输出2
若target+数组和为负数，则说明无法构造出该正数和，直接返回0

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func findTargetSumWays(nums []int, target int) int {
    sum := 0
    for i := range nums {
        sum += nums[i] // 求数组和
    }
    if (sum + target) % 2 == 1 || (sum + target) < 0 {
        return 0 // 无法构造出表达式
    }
    w := (sum + target) / 2 // 背包容量
    dp := make([]int, w+1)
    dp[0] = 1
    for i := 0; i < len(nums); i++ { // 定物品
        for j := w; j >= nums[i]; j-- { // 遍历背包容量
            dp[j] += dp[j-nums[i]]
        }
    }
    return dp[w]
}

时间复杂度：$O(n × m)$，n为正数个数，m为背包容量
空间复杂度：$O(m)$，m为背包容量

一和零

474. 一和零 - 力扣（LeetCode）

给定一个字符串数组和两个整数m、n，字符串数组中元素只含01，求该数组的子集的最大长度，要求子集中含0的个数不能超过给定m，子集中含1的个数不能超过给定n

将m和n理解为形容一种容器，装满这个容器最多需要多少个元素，就输出多少；这个容器最多有m个0，n个1；这个容器就可以看作一个背包，这个背包有mn两个维度，数组中每个元素都看作物品，问装满这个背包最多有多少个物品

01背包：每个物品只能使用一次

定义二维dp数组：背包有两个维度，问满足这两个维度装满该背包最多有多少个物品

元素=重量：每个元素的重量：x个0，y个1

dp[i][j]：装满背包容量i和j最多可以背的物品个数
递推公式：dp[i][j] = max(dp[i][j], dp[i-x][j-y]+1)
初始化：dp[0][0] = 0
遍历顺序：倒序，从右往左

注意：

dp[i-x][j-y]+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
26
27
28


func findMaxForm(strs []string, m int, n int) int {
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    for _, str := range strs { // 定物品
        count0, count1 := 0, 0
        for _, char := range str { // 统计元素中01个数
            if char == '0' {
                count0++
            } else {
                count1++
            }
        }
        for i := m; i >= count0; i-- { // 遍历背包重量维度0
            for j := n; j >= count1; j-- { // 遍历背包重量维度1
                dp[i][j] = max(dp[i][j], dp[i-count0][j-count1]+1)
            }
        }
    }
    return dp[m][n]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间复杂度: $O(kmn)$，k 为strs的长度
空间复杂度: $O(mn)$

完全背包问题

52. 携带研究材料 - 卡码网（KamaCoder）

n种物品，每种物品有重量和价值，背包容量为w，每种物品有无限件，可以放入背包多次，求解装哪些物品使价值总和最大

由于每个物品可以被多次选入，所以内层遍历背包容量时正序遍历，从左往右

dp[j]：背包容量为j时的可装的最大价值
递推公式：dp[j] = max(dp[j]，dp[j-weight(i)]+value(i))
初始化：dp[0] = 0
遍历顺序：正序，从左往右

 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


package main

import "fmt"

func completeBag() int {
    // 获取数据
    var n, w int
    fmt.Scanln(&n, &w)
    weight := make([]int, n)
    value := make([]int, n)
    for i := 0; i < n; i++ {
        fmt.Scanln(&weight[i], &value[i])
    }
    // 核心代码
    dp := make([]int, w+1)
    for i := 0; i < n; i++ { // 定物品
        for j := weight[i]; j <= w; j++ { // 遍历背包容量
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
        }
    }
    return dp[w]
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

func main() {
    fmt.Println(completeBag())
}

零钱兑换II

518. 零钱兑换 II - 力扣（LeetCode）

给定一个整数和整数数组，数组中每个元素可以重复选择，问用数组中元素凑成给定整数的组合数

完全背包问题：元素可以重复选，元素=重量；背包容量=给定整数；问装满该包有多少种方法

dp[j]：背包容量为j时可以装满该包的方法
递推公式：dp[j] += dp[j-weight[i]]
初始化：dp[0] = 1
遍历顺序：正序，从左往右

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func change(amount int, coins []int) int {
    dp := make([]int, amount+1)
    dp[0] = 1
    for i := 0; i < len(coins); i++ { // 定物品
        for j := coins[i]; j <= amount; j++ { // 遍历背包容量
            dp[j] += dp[j-coins[i]]
        }
    }
    return dp[amount]
}

时间复杂度: $O(mn)$，其中 m 是amount，n 是 coins 的长度
空间复杂度: $O(m)$

组合总和IV

377. 组合总和 Ⅳ - 力扣（LeetCode）

给定一个整数和整数数组，数组中每个元素可以重复选择，问用数组中元素凑成给定整数的组合数

顺序不同的序列视作不同组合，其实就是求排列数

完全背包问题：元素可以重复选，元素=重量；背包容量=给定整数；问装满该包有多少种方法

先遍历物品再遍历背包得到的是组合数；先遍历背包再遍历物品得到的是排列数

dp[j]：背包容量为j时可以装满该包的排列数
递推公式：dp[i] += dp[i-weight[j]]
初始化：dp[0] = 1
遍历顺序：正序，从上往下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func combinationSum4(nums []int, target int) int {
    dp := make([]int, target+1)
    dp[0] = 1
    for j := 0; j <= target; j++ { // 定背包容量
        for i := 0; i < len(nums); i++ { // 遍历物品
            if j >= nums[i] {
                dp[j] += dp[j-nums[i]]
            } 
        }
    }
    return dp[target]
}

时间复杂度: $O(target * n)$，其中 n 为 nums 的长度
空间复杂度: $O(target)$

爬楼梯（进阶版）

57. 爬楼梯 - 卡码网（KamaCoder）

给定两个整数nm，表示需要 n 阶到达楼顶，每次至多可爬m (1 <= m < n)个台阶，问有多少种不同的方法可以爬到楼顶

完全背包：楼顶阶数=背包容量，阶数=物品重量，阶数可以重复使用

dp[j]：背包容量为j时可以装满该包的排列数
递推公式：dp[j] += dp[j-weight[i]]
初始化：dp[0] = 1
遍历顺序：正序，从上往下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func completeBag() int {
    dp := make([]int, n+1)
    dp[0] = 1
    for j := 0; j <= n; j++ { // 定背包容量
        for i := 1; i <= m; i++ { // 遍历物品
            if j >= i {
                dp[j] += dp[j-i]
            }
        }
    }
    return dp[n]
}

时间复杂度: $O(n * m)$
空间复杂度: $O(n)$

零钱兑换

322. 零钱兑换 - 力扣（LeetCode）

给定一个整数数组和整数，返回用数组中元素刚好凑成整数所需的最少个数，每个元素可以重复选，若凑不成则返回-1

完全背包：每个元素可以重复选，元素=重量，背包容量=给定整数

dp[j]：背包容量为j时刚好装满背包的最少物品个数
递推公式：dp[j] = min(dp[j]，dp[j-weigth(i)]+1)
初始化：dp[0] = 0；其余初始化为int的最大值
遍历顺序：正序，从左到右

注意：

内层遍历背包容量时，若遇到dp[j-weigth(i)] = int的最大值，则直接进入下次循环，防止最大值+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 coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = math.MaxInt32
    }
    // 定物品
    for i := 0; i < len(coins); i++ { 
        // 遍历背包容量
        for j := coins[i]; j <= amount; j++ { 
            if dp[j-coins[i]] != math.MaxInt32 {
                dp[j] = min(dp[j], dp[j-coins[i]]+1)
            }      
        }
    }
    if dp[amount] == math.MaxInt32 {
        return -1
    }
    return dp[amount]
}
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

时间复杂度: $O(n * amount)$，其中 n 为 coins 的长度
空间复杂度: $O(amount)$

完全平方数

279. 完全平方数 - 力扣（LeetCode）

给定一个整数 n，返回和为 n 所需的最少完全平方数的数量。完全平方数是一个整数，其值等于另一个整数的平方

完全背包：每个元素可以重复选，元素=重量，背包容量=给定整数

完全平方数用i×i表示

dp[j]：背包容量为j时刚好装满背包的最少元素个数
递推公式：dp[j] = min(dp[j]，dp[j-i×i]+1)
初始化：dp[0] = 0；其余初始化为int的最大值
遍历顺序：正序，从左到右

注意：

内层遍历背包容量时，若遇到dp[j-i×i] = int的最大值，则直接进入下次循环，防止最大值+1=最小值
外层遍历物品时，用i*i表示完全平方数，从1开始循环，由于是由完全平方数和组成给定整数，所以完全平方数一定小于等于给定整数，即当完全平方数>背包容量时结束循环

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func numSquares(n int) int {
    dp := make([]int, n+1)
    for i := 1; i <= n; i++ {
        dp[i] = math.MaxInt16
    }
    for i := 1; i*i <= n; i++ { // 定物品
        for j := i * i; j <= n; j++ { // 遍历背包容量
            if dp[j-i*i] != math.MaxInt16 {
                dp[j] = min(dp[j], dp[j-i*i]+1)
            }
        }
    }
    return dp[n]
}
1 2 3 4 5 6 7 8 9 10 11 12 
      1 2 3 4 2 2 4  5  3
                1 2  3  4

时间复杂度: $O(n * √n)$
空间复杂度: $O(n)$

单词拆分

139. 单词拆分 - 力扣（LeetCode）

给定一个字符串和字符串数组，如果可以用数组中元素拼接出给定字符串则返回true，否则返回false，每个元素可以重复使用

完全背包：每个元素可以重复使用，元素=物品=重量，背包容量=给定字符串

对所选元素有顺序要求，顺序不对也拼接不出给定字符串，所以是求排列数

dp[j]：字符串长度为j时能否被数组中元素组成
递推公式：if(dp[j]=true && (j，i))
初始化：dp[0] = true
遍历顺序：先定背包容量再遍历元素，从上往下

注意：

if(dp[j]=true && (j，i))：[0,j]匹配成功且字典中有[j,i]
内层循环的j是子串的起始位置，j应该小于i背包容量即最终位置
从给定字符串切割出(j,i)子串后，再遍历给定数组看是否有该子串
为了减小时间复杂度，可以将给定字符串数组存储为真正的字典，切割出子串后就不用遍历数组匹配了
内层循环中匹配成功时说明当前最终位置的字符串[0,i]已经成功用字典匹配，可以直接进入下一外层循环增加背包容量

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func wordBreak(s string, wordDict []string) bool {
    wordDictMap := make(map[string]bool)
    for _, v := range wordDict { // 加入map方便查找
        wordDictMap[v] = true
    }
    w := len(s)
    dp := make([]bool, w+1)
    dp[0] = true
    // 遍历背包容量(定尾)
    for i := 1; i <= w; i++ { 
        // 正序遍历物品(定子串起始位置)
        for j := 0; j < i; j++ { 
            // [0,j-1]能被组成且字典中有[j,i]
            if dp[j] && wordDictMap[s[j:i]] { 
                // [0,i-1]能被组成
                dp[i] = true 
                // 当前最终位置的字符串能被组成,直接更新尾
                break        
            }
        }
    }
    return dp[w]
}

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

写法二：dp[i]表示[0,i]是否能被字典组成

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func wordBreak(s string, wordDict []string) bool {
    // 将字典存入map
    mp := make(map[string]bool)
    for _, v := range wordDict {
        mp[v] = true
    }
    // 初始化dp
    dp := make([]bool, len(s))
    // 定尾
    for i := 0; i < len(s); i++ {
        // 定首
        for j := 0; j <= i; j++ {
            // 判断[j,i]是否在字典中且[0,i]未匹配成功过
            if mp[s[j:i+1]] && !dp[i] {
                dp[i] = j == 0 || dp[j-1]
            }
        }
    }
    return dp[len(s)-1]
}

多重背包问题

56. 携带矿石资源 - 卡码网（KamaCoder）

n种物品，每种物品有重量、价值和个数，背包容量为w，每种物品有个数限制，求解装哪些物品使价值总和最大

将同一物品的多个数量分为多行，即转换为01背包问题，物品有几个就在在01背包里面遍历几遍

dp[j]：背包容量为j时能装的最大价值
递推公式：dp[j] = max(dp[j]，dp[j-weight[i]]+value[i])
初始化：dp[0]=0
遍历顺序：先定物品再遍历背包容量，从右往左

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func multipleBag() int {
    dp := make([]int, w+1)
    for i := 0; i < n; i++ { // 遍历物品
        for j := w; j >= weight[i]; j-- { // 倒序遍历容量
            for k := 1; k <= count[i] && j >= k*weight[i]; k++ { // 遍历物品个数
                dp[j] = max(dp[j], dp[j - k*weight[i]] + k*value[i])
            }
        }
    }
    return dp[w]
}

时间复杂度：$O(m × n × k)$，m：物品种类个数，n背包容量，k单类物品数量

打家劫舍

198. 打家劫舍 - 力扣（LeetCode）

给定一个整数数组，每个元素表示金额，不能取相邻两个元素，问能取出的最大金额

每个元素取不取只取决于前两个元素

dp[i]：[0，i]所能取出的最大金额
递推公式：dp[i]=max(dp[i-1]，dp[i-2]+nums[i])
初始化：dp[0]=nums[0]；dp[1]=max(nums[0]，nums[1])
遍历顺序：从小到大

注意：

dp[i-1]：不取i
dp[i-2]+nums[i]：取i

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


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

时间复杂度: $O(n)$
空间复杂度: $O(n)$

打家劫舍II

213. 打家劫舍 II - 力扣（LeetCode）

给定一个整数循环数组，每个元素表示金额，不能取相邻两个元素，问能取出的最大金额

将环形问题拆分为线性问题：环形数组中首尾元素不能同时取，所以可以将环形数组分为不考虑尾元素和不考虑首元素两种情况；不考虑尾元素的话相当于尾元素是一定不选的，所以是在去除尾元素的线性数组上求解；不考虑首元素的话相当于首元素是一定不选的，所以是在去除首元素的线性数组上求解，最后选取这两种情况的最大值即为在环形数组中可取的最大值

dp[i]：[0，i]所能取出的最大金额
递推公式：dp[i]=max(dp[i-1]，dp[i-2]+nums[i])
初始化：dp[0]=max(dp[len(nums)-2])；dp[1]=max(nums[0]，nums[1])
遍历顺序：从小到大

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func rob(nums []int) int {
    if len(nums) == 1 {
        return nums[0]
    }
    if len(nums) == 2 {
        return max(nums[0], nums[1])
    }
    dp1, dp2 := make([]int, len(nums)-1), make([]int, len(nums)-1)
    dp1[0], dp1[1], dp2[0], dp2[1] = nums[0], max(nums[0], nums[1]), nums[1], max(nums[1], nums[2])
    for i := 2; i < len(nums)-1; i++ {
        dp1[i] = max(dp1[i-1], dp1[i-2]+nums[i])   // 不考虑尾元素
        dp2[i] = max(dp2[i-1], dp2[i-2]+nums[i+1]) // 不考虑首元素
    }
    return max(dp1[len(dp1)-1], dp2[len(dp2)-1])
}

时间复杂度: $O(n)$
空间复杂度: $O(n)$

打家劫舍III

337. 打家劫舍 III - 力扣（LeetCode）

给定一个二叉树，收集节点值，不能收集直接相连的节点值，问一共能收集到的最大和

后序遍历从底向上，记录每个节点偷与不偷两种状态可获取的最大和，利用当前节点左右孩子的状态一层层往上推，最后将最优解集中在根节点

用一个长度为2的数组，记录当前节点偷与不偷所得到的的最大金钱，在递归的过程中，系统栈会保存每一层递归的参数

递归函数的参数和返回值：参数为当前节点，返回值是一个长度为2的数组（dp数组）

dp[0]：不偷该节点所得到的的最大金钱；dp[1]：偷该节点所得到的的最大金钱
终止条件：遇到空节点的话无论偷还是不偷都是0，返回

这也相当于dp数组的初始化
遍历顺序：后序遍历；通过递归左节点，得到左节点偷与不偷的金钱；通过递归右节点，得到右节点偷与不偷的金钱
单层递归逻辑：

如果是偷当前节点，那么左右孩子就不能偷，val1 = cur->val + leftDp[0] + rightDp[0]；

如果不偷当前节点，那么左右孩子就可以偷，至于到底偷不偷左右孩子一定是选一个最大的，所以：val2 = max(leftDp[0], leftDp[1]) + max(rightDp[0], rightDp[1])；

最后当前节点的状态就是{val2, val1}；即：{不偷当前节点得到的最大金钱，偷当前节点得到的最大金钱}

注意：最后递归结束返回根结点后，取下标0和下标1的最大值就是偷得的最大金钱

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rob(root *TreeNode) int {
    res := robtree(root)
    return max(res[0], res[1])
}
func robtree(cur *TreeNode) [2]int {
    if cur == nil { // 终止条件
        return [2]int{0, 0}
    }
    leftDp := robtree(cur.Left)                                         // 左
    RightDp := robtree(cur.Right)                                       // 右
    noRobCur := max(leftDp[0], leftDp[1]) + max(RightDp[0], RightDp[1]) // 不取当前节点:考虑取不取左右孩子
    robCur := cur.Val + leftDp[0] + RightDp[0]                          // 取当前节点
    return [2]int{noRobCur, robCur}
}

时间复杂度：$O(n)$，每个节点只遍历了一次
空间复杂度：$O(log n)$，算上递推系统栈的空间

买卖股票的最佳时机

121. 买卖股票的最佳时机 - 力扣（LeetCode）

给定一个数组，每个元素表示股票第i天的价格，不能同一天买入卖出，只能买卖一次，求最大利润，若不能获得正收益则返回0

dp[i][0]：第i天不持有股票手中的最大金额；dp[i][1]：第i天持有股票手中的最大金额
递推公式：
- dp[i][0]=max(dp[i-1][0], dp[i-1][1]+price[i])
- dp[i][1]=max(dp[i-1][1], -price[i])
初始化：dp[0][0]=0; dp[0][1]=-price[0]
遍历顺序：从前往后

注意：

持有是指手中有该股票，可能是今天买入的也可能是之前某天买入的；不持有是指该天或之前某天卖出该股票
dp[i][0]=max(dp[i-1][0], dp[i-1][1]+price[i])：第i天不持有分为两种情况；一种是和前一天一样本来就不持有；另一种是之前一直持有，但今天卖出所以不持有；取两种情况中的最大值
dp[i][1]=max(dp[i-1][1], -price[i])：第i天持有分为两种情况；一种是和前一天一样本来就持有；另一种是之前一直不持有；但今天买入所以持有；取两种情况中的最大值；由于只能买卖一次，所以买入时手中金额一定为0，故是-price[i]
初始金额为零；第一天买入的话就是负的元素值
最后返回最后一天不持有股票的最大金额即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func maxProfit(prices []int) int {
    length := len(prices)
    dp := make([][2]int, length)
    dp[0][1] = -prices[0]
    for i := 1; i < length; i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) // 不持有股票
        dp[i][1] = max(dp[i-1][1], -prices[i])           // 持有股票
    }
    return dp[length-1][0]
}

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

买卖股票的最佳时机 II

122. 买卖股票的最佳时机 II - 力扣（LeetCode）

给定一个数组，每个元素表示股票第i天的价格，能同一天买入卖出，能买卖多次，求最大利润，若不能获得正收益则返回0

dp[i][0]：第i天不持有股票的最大金额；dp[i][1]：第i天持有股票的最大金额
递推公式：
- dp[i][0]=max(dp[i-1][0], dp[i-1][1]+price[i])；
- dp[i][1]=max(dp[i-1][1], dp[i-1][0]-price[i])
初始化：dp[0][0]=0; dp[0][1]=-price[0]
遍历顺序：从前往后

注意：

由于可以多次买卖，所以dp[i][1]=max(dp[i-1][1], dp[i-1][0]-price[i])中若该天买入股票，则用前一天不持有股票的最大金额减去买入该股票所需金额，因为多次买卖后手中现金不一定为0，可能会有之前买卖的利润

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func maxProfit(prices []int) int {
    length := len(prices)
    dp := make([][2]int, length)
    dp[0][1] = -prices[0]
    for i := 1; i < length; i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i]) // 不持有
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i]) // 持有
    }
    return dp[length-1][0]
}

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

买卖股票的最佳时机 III

123. 买卖股票的最佳时机 III - 力扣（LeetCode）

给定一个数组，每个元素表示股票第i天的价格，能同一天买入卖出，至多能买卖两次，求最大利润，若不能获得正收益则返回0

dp[i][0]：第一次持有；dp[i][1]：第一次不持有；

dp[i][2]：第二次持有；dp[i][3]：第二次不持有
递推公式：
- dp[i][0]=max(dp[i-1][0], -price[i])；
- dp[i][1]=max(dp[i-1][1], dp[i-1][0]+price[i])；
- dp[i][2]=max(dp[i-1][2], dp[i-1][1]-price[i])；
- dp[i][3]=max(dp[i-1][3], dp[i-1][2]+price[i])；
初始化：dp[0][0]=-price[0]; dp[0][1]=0; dp[0][2]=-price[0]; dp[0][3]=0;
遍历顺序：从前往后

注意：

最后返回第二次不持有的最大金额：第二次不持有包含第一次不持有
初始化可以理解为第一天买入又卖出再买入再卖出
一定是先买入持有，再卖出不持有，所以dp[i][0]为第一次持有

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func maxProfit(prices []int) int {
    length := len(prices)
    dp := make([][4]int, length)
    dp[0][0], dp[0][2] = -prices[0], -prices[0]
    for i := 1; i < length; i++ {
        dp[i][0] = max(dp[i-1][0], -prices[i])           // 第一次持有
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]) // 第一次不持有
        dp[i][2] = max(dp[i-1][2], dp[i-1][1]-prices[i]) // 第二次持有
        dp[i][3] = max(dp[i-1][3], dp[i-1][2]+prices[i]) // 第二次不持有
    }
    return dp[length-1][3]
}

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

买卖股票的最佳时机 IV

188. 买卖股票的最佳时机 IV - 力扣（LeetCode）

给定一个数组和整数k，每个元素表示股票第i天的价格，能同一天买入卖出，至多能买卖k次，求最大利润，若不能获得正收益则返回0

dp[i][0]：第一次持有；dp[i][1]：第一次不持有；

dp[i][2]：第二次持有；dp[i][3]：第二次不持有；

……；

dp[i][2k-2]：第k次持有；dp[i][2k-1]：第k次不持有
递推公式：
- dp[i][0]=max(dp[i-1][0], -price[i])；
- dp[i][1]=max(dp[i-1][1], dp[i-1][0]+price[i])；
- dp[i][2]=max(dp[i-1][2], dp[i-1][1]-price[i])；
- dp[i][3]=max(dp[i-1][3], dp[i-1][2]+price[i])；
- ……
- dp[i][2k-2]=max(dp[i-1][2k-2], dp[i-1][2k-3]-price[i])；
- dp[i][2k-1]=max(dp[i-1][2k-1], dp[i-1][2k-2]+price[i])；
初始化：
- dp[0][0]=-price[0]; dp[0][1]=0;
- dp[0][2]=-price[0]; dp[0][3]=0;

……
- dp[0][2k-2]=-price[0]; dp[0][2k-1]=0

遍历顺序：从前往后

注意：

外层循环给定数组；内层循环买卖次数
给定数组中每个元素都有2k-1个状态

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func maxProfit(k int, prices []int) int {
    length := len(prices)
    dp := make([][]int, length)
    for i := range dp {
        dp[i] = make([]int, 2*k)
    }
    for i := 1; i <= k; i++ {
        dp[0][2*i-2] = -prices[0]
    }
    for i := 1; i < length; i++ {
        for j := 1; j <= k; j++ {
            if j == 1 {
                dp[i][2*j-2] = max(dp[i-1][2*j-2], -prices[i]) // 第1次持有
            } else {
                dp[i][2*j-2] = max(dp[i-1][2*j-2], dp[i-1][2*j-3]-prices[i]) // 第j次持有
            }
            dp[i][2*j-1] = max(dp[i-1][2*j-1], dp[i-1][2*j-2]+prices[i]) // 第j次不持有
        }
    }
    return dp[length-1][2*k-1]
}

时间复杂度: $O(n * k)$，其中 n 为 prices 的长度
空间复杂度: $O(n * k)$

买卖股票的最佳时机含冷静期

309. 买卖股票的最佳时机含冷冻期 - 力扣（LeetCode）

给定一个数组和整数k，每个元素表示股票第i天的价格，能同一天买入卖出，能买卖多次，冷静期为一天(卖出后必须搁一天才能再次买入)，求最大利润，若不能获得正收益则返回0

dp[i][0]：第i天持有股票的最大金额；

dp[i][1]：第i天保持卖出股票的最大金额；

dp[i][2]：第i天卖出股票的最大金额；

dp[i][3]：第i天是冷冻期的最大金额
递推公式：
- dp[i][0]=max(dp[i-1][0], dp[i-1][3]-price[i], dp[i-1][1]-price[i])；
- dp[i][1]=max(dp[i-1][1], dp[i-1][3])
- ``dp[i][2]=dp[i-1][0]+price[i]`
- dp[i][3]=dp[i-1][2]
初始化：dp[0][0]=-price[0]
遍历顺序：从前往后

注意：

持有股票=和前一天一样持有股票+前一天是冷冻期今天买入+前一天是保持卖出今天买入
保持卖出=和前一天一样保持卖出+前一天是冷冻期
卖出股票=前一天持有股票今天卖出
冷冻期=前一天卖出股票
不持有股票=保持卖出+卖出+冷冻期，最后返回不持有三种状态中的最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func maxProfit(prices []int) int {
    length := len(prices)
    dp := make([][4]int, length)
    dp[0][0] = -prices[0]
    for i := 1; i < length; i++ {
        // 第i天持有股票
        dp[i][0] = max(dp[i-1][0], dp[i-1][3]-prices[i], dp[i-1][1]-prices[i])
        // 第i天保持卖出
        dp[i][1] = max(dp[i-1][1], dp[i-1][3])
        // 第i天卖出股票
        dp[i][2] = dp[i-1][0] + prices[i]
        // 第i天是冷冻期
        dp[i][3] = dp[i-1][2]                                           
    }
    return max(dp[length-1][1], dp[length-1][2], dp[length-1][3])
}

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

买卖股票的最佳时机含手续费

714. 买卖股票的最佳时机含手续费 - 力扣（LeetCode）

给定一个数组和整数fee，每个元素表示股票第i天的价格，能同一天买入卖出，能买卖多次，手续费为fee(一次买入卖出全过程支付一次)，求最大利润，若不能获得正收益则返回0

dp[i][0]：第i天持有股票的最大金额；dp[i][1]：第i天不持有股票的最大金额
递推公式：
- dp[i][0]=max(dp[i-1][0], dp[i-1][1]-price[i])
- dp[i][1]=max(dp[i-1][1], dp[i-1][0]+price[i]-fee)
初始化：dp[0][0]=-price[0]
遍历顺序：从前往后

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


func maxProfit(prices []int, fee int) int {
    length := len(prices)
    dp := make([][2]int, length)
    dp[0][0] = -prices[0]
    for i := 1; i < length; i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1]-prices[i])     // 第i天持有
        dp[i][1] = max(dp[i-1][1], dp[i-1][0]+prices[i]-fee) // 第i天不持有
    }
    return dp[length-1][1]
}

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

最长递增子序列

300. 最长递增子序列 - 力扣（LeetCode）

给定一个整数数组，返回最长递增子序列的长度，选取的元素要递增，可以不连续，但要保持原数组顺序

dp[i]：以nums[i]为尾的最长递增子序列的长度
递推公式：dp[i]=max(dp[j]+1，dp[i])
初始化：dp[i]=1
遍历顺序：从小到大

注意：

两层for循环：外层定尾，从第二个元素开始遍历，每次初始化自身dp为1；内层定首，从头开始遍历到尾前一个
dp[i]=max(dp[j]+1，dp[i])：因为在i之前是用j遍历每个元素num[j]，都会与num[i]比较，若nums[j]<nums[i]，则dp[i]=max(dp[j]+1, dp[i])，这会得到一系列dp[i]，取其中最大的dp[i]
dp[i]=1：只算本身的话就是一个
最终结果是dp数组中的最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = 1
    res := 1
    // 定尾
    for i := 1; i < len(nums); i++ { 
        dp[i] = 1
        // 遍历首
        for j := 0; j < i; j++ { 
            if nums[j] < nums[i] {
                dp[i] = max(dp[j]+1, dp[i])
            }
        }
        if dp[i] > res {
            // 更新结果
            res = dp[i] 
        }
    }
    return res
}

时间复杂度: $O(n^2)$
空间复杂度: $O(n)$

最长连续递增序列

674. 最长连续递增序列 - 力扣（LeetCode）

给定一个整数数组，返回最长递增子序列的长度，选取的元素要递增，必须连续

dp[i]：以nums[i]为尾的最长递增子序列的长度
递推公式：dp[i]=dp[i-1]+1
初始化：dp[i]=1
遍历顺序：从小到大

dp[i]=dp[i-1]+1：由于要求连续递增子序列，所以只与前一个元素比较，当nums[i-1]<nums[i]时，dp[i]=dp[i-1]+1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func findLengthOfLCIS(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = 1
    res := 1
    for i := 1; i < len(nums); i++ {
        dp[i] = 1
        if nums[i-1] < nums[i] {
            dp[i] = dp[i-1] + 1
            if dp[i] > res {
                res = dp[i]
            }
        }
    }
    return res
}

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

最长重复子数组

718. 最长重复子数组 - 力扣（LeetCode）

给定两个数组，返回两个数组中公共最长子数组的长度，必须连续

dp[i][j]：以nums1[i-1]和nums2[j-1]为尾的公共最长子数组的长度
递推公式：dp[i][j] = dp[i-1][j-1] + 1
初始化：dp[i][0]=0; dp[0][j]=0
遍历顺序：从小往大

注意：

以i-1和j-1为尾：为了使第一行和第一列dp[i][0]、dp[0][j]没有意义，直接初始化为0；若用i和j结尾，则初始化dp[i][0]时要用第二个数组中第一个元素和第一个数组中所有元素进行比较，若一样则初始化为1，否则初始化为0，dp[0][j]同理
内外层遍历都从下标1开始；定义dp数组时要覆盖边界i和j
递推公式：当遍历两个数组时遇到nums1[i-1]=nums2[j-1]，说明两个数组中遇到相同元素，则dp[i][j] = dp[i-1][j-1] + 1在前一个元素的基础上加一
最终结果是dp数组中的最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func findLength(nums1 []int, nums2 []int) int {
    dp := make([][]int, len(nums1)+1)
    for i := range dp {
        dp[i] = make([]int, len(nums2)+1)
    }
    res := 0
    for i := 1; i <= len(nums1); i++ {
        for j := 1; j <= len(nums2); 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
}

时间复杂度：$O(n × m)$，n 为A长度，m为B长度
空间复杂度：$O(n × m)$

最长公共子序列

1143. 最长公共子序列 - 力扣（LeetCode）

给定两个字符串，返回最长公共子序列的长度，可以不连续

dp[i][j]：[0, i-1]nums1和[0, j-1]nums2中的最长公共子序列的长度
递推公式：
- if nums[i-1] == nums[j-1]
  - dp[i][j] = dp[i-1][j-1] + 1;
- else
  - dp[i][j] = max(dp[i-1][j], dp[i][j-1])
初始化：dp[i][0]=0; dp[0][j]=0
遍历顺序：从左到右，从上到下

注意：

dp[i][j] = dp[i-1][j-1] + 1：俩元素相等，在前一个基础上长度加一
dp[i][j] = max(dp[i-1][j], dp[i][j-1])是表示两数组中这俩元素不相等，则需要逻辑上删除一个元素，然后下一循环会继续向后比较（逻辑上是找到连续的序列）；至于删除两数组中哪个元素，则需要取一个现有长度最大值，保证当前找到的最长子序列长度状态的延续
dp[i][j] = dp[i-1][j-1] + 1 是从左上加一得到；dp[i][j] = max(dp[i-1][j], dp[i][j-1])是取上和左中的大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func longestCommonSubsequence(text1 string, text2 string) int {
    dp := make([][]int, len(text1)+1)
    for i := range dp {
        dp[i] = make([]int, len(text2)+1)
    }
    for i := 1; i <= len(text1); i++ {
        for j := 1; j <= len(text2); j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[len(text1)][len(text2)]
}

时间复杂度: $O(n * m)$，其中 n 和 m 分别为 text1 和 text2 的长度
空间复杂度: $O(n * m)$

不相交的线

1035. 不相交的线 - 力扣（LeetCode）

给定两个整数数组，相同数字间可以连线，要求线不能相交，每个数字只能属于一条连线，返回最大连线数

该问题也就是求最长公共子序列

和上一题一模一样

最大子数组和

53. 最大子数组和 - 力扣（LeetCode）

给定一个整数数组，找出一个连续子数组，返回其最大和

dp[i]：以nums[i]为尾的最大连续子数组的和
递推公式：dp[i] = max(dp[i-1]+nums[i]，nums[i])
初始化：dp[0] = nums[0]
遍历顺序：从前到后

注意：

dp[i-1]+nums[i]是直接延续前面的和，然后将当前元素加上去；nums[i]是从当前元素开始从头计算
最终结果是dp数组中的最大值

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


func maxSubArray(nums []int) int {
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    res := dp[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1]+nums[i], nums[i])
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}

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

判断子序列

392. 判断子序列 - 力扣（LeetCode）

给定两个字符串，判断第一个字符串是否是第二个字符串的子序列，不要求必须连续

暴力：两层遍历，第一层遍历第一个字符串；第二层遍历逐个比对并比较下标确定相对位置

动规：转化为求最长公共子序列长度是否与第一个字符串长度相同

dp[i][j]：[0, i-1]s和[0, j-1]t中的最长公共子序列的长度
递推公式：
- if s[i-1] == t[j-1]
  - dp[i][j] = dp[i-1][j-1] + 1;
- else
  - dp[i][j] = dp[i][j-1]
初始化：dp[i][0] = 0; dp[0][j] = 0
遍历顺序：从左到右，从上到下

注意：

dp[i][j] = dp[i][j-1]：不相等时，一定时逻辑删除t中一个字符
最后求得的最长公共子序列长度若等于第一个字符串的长度，则返回true

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


func isSubsequence(s string, t string) bool {
    dp := make([][]int, len(s)+1)
    for i := range dp {
        dp[i] = make([]int, len(t)+1)
    }
    for i := 1; i <= len(s); i++ {
        for j := 1; j <= len(t); j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = dp[i][j-1]
            }
        }
    }
    return dp[len(s)][len(t)] == len(s)
}

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

双指针法：双指针指向两个字符串的开头，遍历第二个字符串时遇到与第一个字符相等的字符时，指针一后移一个，当指针一遍历完第一个字符串时直接返回true

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


func isSubsequence(s string, t string) bool {
    if len(s) == 0 {
        return true
    }
    idx := 0
    for i := 0; i < len(t); i++ {
        if s[idx] == t[i] {
            idx++
            if idx == len(s) {
                return true
            }
        }
    }
    return false
}

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

不同的子序列

115. 不同的子序列 - 力扣（LeetCode）

给定两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数，可以不连续，结果需要对 10⁹ + 7 取模

dp[i][j]：以i-1为尾的s中有以j-1为尾的t的个数
递推公式：
- if s[i-1] == t[j-1]
  - dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
- else
  - dp[i][j] = dp[i-1][j]
初始化：dp[0][0] = 0; dp[i][0] = 1; dp[0][j] = 0
遍历顺序：从左到右，从上到下

注意：

dp[i][j] = dp[i-1][j-1] + dp[i-1][j]：当两个元素相等时，就不用再考虑该元素，只需要延续该元素前一个元素的s中有多少个以前一个元素为尾的t的状态；还要考虑另一种情况，该元素前面的以前一个元素为尾的s中有多少个以当前元素为尾的t
dp[i][j] = dp[i-1][j]：当两个元素不相等时，因为只考虑s中有多少个t，所以逻辑删除s中该元素
dp[i][0] = 1：t是空字符串

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func numDistinct(s string, t string) int {
    dp := make([][]int, len(s)+1)
    for i := range dp {
        dp[i] = make([]int, len(t)+1)
    }
    dp[0][0] = 1
    for i := 1; i <= len(s); i++ {
        dp[i][0] = 1
        for j := 1; j <= len(t); j++ {
            if s[i-1] == t[j-1] {
                dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
            } else {
                dp[i][j] = dp[i-1][j]
            }
        }
    }
    return dp[len(s)][len(t)]
}

时间复杂度: $O(n * m)$
空间复杂度: $O(n * m)$

两个字符串的删除操作

583. 两个字符串的删除操作 - 力扣（LeetCode）

给定两个单词 word1 和 word2 ，每步可以删除任意一个字符串中的一个字符，返回使得 word1 和 word2 相同所需的最小步数

dp[i][j]：以i-1为尾word1和以j-1为尾word2相同的最小步数
递推公式：
- if word1[i-1] == word2[j-1]
  - dp[i][j] = dp[i-1][j-1]
- else
  - dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+2)
初始化：dp[0][0] = 0, dp[0][j] = j, dp[i][0] = i
遍历顺序：从左到右，从上到下

注意：

当两个元素相同时：无需删除，直接延续前面的状态
当两个元素不同：需要删除元素，分为三种情况取最小步数，删word1步数加一或word2步数加一或两个同时删步数加二
dp[0][j] = j：word1为空字符串，需要删除word2中每个元素；dp[i][j] = i同理

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


func minDistance(word1 string, word2 string) int {
    dp := make([][]int, len(word1)+1)
    for i := range dp {
        dp[i] = make([]int, len(word2)+1)
    }
    for i := 1; i <= len(word1); i++ {
        dp[i][0] = i
        for j := 1; j <= len(word2); j++ {
            dp[0][j] = j
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+2)
            }
        }
    }
    return dp[len(word1)][len(word2)]
}

也可以用先求出最长公共子序列，然后用总长度减去子序列长度就是最少步数

时间复杂度: $O(n * m)$
空间复杂度: $O(n * m)$

编辑距离

72. 编辑距离 - 力扣（LeetCode）

给定两个单词 word1 和 word2，可以进行三种操作：插入、删除、替换一个字符，返回将 word1 转换成 word2 所使用的最少操作数

dp[i][j]：word1[0, i-1]和word2[0, j-1]相等的最少操作数
递推公式：
- if word1[i-1] == word2[j-1]
  - dp[i][j] = dp[i-1][j-1]
- else
  - dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
初始化：dp[0][0] = 0, dp[0][j] = j, dp[i][0] = i
遍历顺序：从左到右，从上到下

注意：

删除和添加是互为逆向的操作
两个元素不相等：在添加、删除和替换操作中选一个最小的
由于是第一层循环是从word1首开始遍历，所以当word1长度为0，word2有长度时，不会进入循环，无法执行一方为0时初始化为另一方长度的操作，导致最终结果为0，因此需要在循环前判断，当word1长度为0时，直接返回word2的长度

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func minDistance(word1 string, word2 string) int {
    dp := make([][]int, len(word1)+1)
    for i := range dp {
        dp[i] = make([]int, len(word2)+1)
    }
    if len(word1) == 0 {
        return len(word2)
    }
    for i := 1; i <= len(word1); i++ {
        dp[i][0] = i
        for j := 1; j <= len(word2); j++ {
            dp[0][j] = j
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(dp[i-1][j]+1, dp[i][j-1]+1, dp[i-1][j-1]+1)
            }
        }
    }
    return dp[len(word1)][len(word2)]
}

时间复杂度: $O(n * m)$
空间复杂度: $O(n * m)$

回文子串

647. 回文子串 - 力扣（LeetCode）

给定一个字符串 s ，不同开始位置或结束位置视作不同的子串，子字符串必须连续，返回这个字符串中回文子串的数目

dp[i][j]：[i, j]是否是回文子串
递推公式：
- if s[i] == s[j]
  - if j - i <= 1
    - dp[i][j] = true
  - else if dp[i+1][j-1] == true
    - dp[i][j] = true
初始化：dp[i][j]=false
遍历顺序：从下往上，从左往右

注意：

当两个元素相等时，有三种情况：一种是j和i是同一个元素（i=j => j-i=0 => j-i<1）一定是回文串；第二种情况是j和i是相邻的两个相同元素（j-i=1）一定是回文串；第三种情况是j和i中间还有其他元素，这需要进一步判断i的后一个元素与j的前一个元素是否是回文子串，若[i+1,j-1]是回文子串，则再加上s[i]=s[j]说明[i, j]也是回文子串
由递推公式看出，dp[i][j]由左下角状态推导得出
外循环定i，内层循环j从i出发不断向后遍历直到字符串尾，i从字符串尾一直走到字符串头然后结束循环
由于j从i开始，所以元素只存在于二维数组中右上角

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func countSubstrings(s string) int {
    dp := make([][]bool, len(s))
    for i := range dp {
        dp[i] = make([]bool, len(s))
    }
    res := 0
    for i := len(s) - 1; i >= 0; i-- {
        for j := i; j < len(s); j++ {
            if s[i] == s[j] {
                if j-i <= 1 {
                    dp[i][j] = true
                    res++
                } else if dp[i+1][j-1] {
                    dp[i][j] = true
                    res++
                }
            }
        }
    }
    return res
}

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

最长回文子序列

516. 最长回文子序列 - 力扣（LeetCode）

给定一个字符串 s ，子序列可以不连续，返回其中最长的回文子序列的长度。

dp[i][j]：[i,j]最长回文子序列的长度
递推公式：
- if s[i] == s[j]
  - dp[i][j] = dp[i+1][j-1] + 2
- else
  - dp[i][j] = max(dp[i+1][j], dp[i][j-1])
初始化：i和j是同一元素时，dp[i][i] = 1
遍历顺序：从下往上，从左往右

注意：

dp[i][j] = dp[i+1][j-1] + 2：当两个元素相等时，在[i+1,j-1]最长回文子序列长度的基础上加上左右i和j两个元素
dp[i][j] = max(dp[i+1][j], dp[i][j-1])：当两个元素不相等时，分为两种情况：考虑j和考虑i，dp[i][j]取一个大值状态保存下来
外层循环从尾开始到首，内层从i+1开始到尾
由于j从i+1开始遍历，所以元素存在于主对角线之上，需要用到主对角线保存的状态，因此主对角需要初始化长度为1
最终结果为dp[0][len(s)-1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func longestPalindromeSubseq(s string) int {
    dp := make([][]int, len(s))
    for i := range dp {
        dp[i] = make([]int, len(s))
    }
    for i := len(s) - 1; i >= 0; i-- {
        dp[i][i] = 1
        for j := i + 1; j < len(s); j++ {
            if s[i] == s[j] {
                dp[i][j] = dp[i+1][j-1] + 2
            } else {
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
            }
        }
    }
    return dp[0][len(s)-1]
}

时间复杂度: $O(n^2)$
空间复杂度: $O(n^2)$

三角形最小路径和

120. 三角形最小路径和 - 力扣（LeetCode）

给定一个二维数组表示三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。相邻的结点 在这里指的是下标与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。也就是说，如果正位于当前行的下标 i ，那么下一步可以移动到下一行的下标 i 或 i + 1

dp[i][j]：从第0层第0个元素到第i层第j个元素的最小路径和
递推公式：每行首、尾和中间元素三种情况分开讨论
- if j == 0
  - dp[i][j] = dp[i-1][j] + dp[i][j]
- else if j == len(dp[i])-1
  - dp[i][j] += dp[i-1][j-1]
- else
  - dp[i][j] = dp[i][j] + min(dp[i-1][j], dp[i-1][j-1])
初始化：dp[0][0] = triangle[0][0]
遍历顺序：从上到下，从左到右

注意：

遍历最后一行找出最小值即为最小路径和
可以直接用给定数组作为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
27
28
29
30


func minimumTotal(triangle [][]int) int {
    // 从第1行遍历三角形
    for i := 1; i < len(triangle); i++ {
        for j := 0; j < len(triangle[i]); j++ {
            // 判断是否为首元素或尾元素
            // 分为行首、行尾和行中三种情况
            if j == 0 {
                // 行首只能取上一行首元素
                triangle[i][j] += triangle[i-1][j]
            } else if j == len(triangle[i])-1 {
                // 行尾只能取上一行尾元素
                triangle[i][j] += triangle[i-1][j-1]
            } else {
                // 行中取上一行两个来源中的最小值
                triangle[i][j] += min(triangle[i-1][j], triangle[i-1][j-1])
            }
        }
    }
    // 结果初始化为dp数组最后一行首元素
    res := triangle[len(triangle)-1][0]
    // 遍历dp数组最后一行
    for i := 0; i < len(triangle[len(triangle)-1]); i++ {
        // 判断遍历元素是否小于目前最小值
        if triangle[len(triangle)-1][i] < res {
            // 更新结果
            res = triangle[len(triangle)-1][i]
        }
    }
    return res
}

最小路径和

64. 最小路径和 - 力扣（LeetCode）

给定一个二维数组表示网格，找出一条从左上角到右下角的路径，使得路径上的数字总和为最小，每次只能向下或者向右移动一步，返回最小路径和

dp[i][j]：到第i行第j列的最小路径和
递推公式：分为首行、首列和其他格三种情况讨论
- if i == 0
  - dp[i][j] += dp[i][j-1]
- else if j == 0
  - dp[i][j] += dp[i-1][j]
- else
  - dp[i][j] += min(dp[i-1][j], dp[i][j-1])
初始化：dp[0][0] = grid[0][0]
遍历顺序：从上到下，从左到右

注意：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


func minPathSum(grid [][]int) int {
    // 遍历网络
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            // 判断是否为首行首列格
            if i == 0 && j == 0 {
                // 跳过首行首列格
                continue
            }
            // 分为首行、首列和其他格三种情况
            if i == 0 {
                // 首行直接取前一个元素
                grid[i][j] += grid[i][j-1]
            } else if j == 0 {
                // 首列直接取上一个元素
                grid[i][j] += grid[i-1][j]
            } else {
                // 其他格取上左中的小值
                grid[i][j] += min(grid[i-1][j], grid[i][j-1])
            }
        }
    }
    // 返回最后一个元素
    return grid[len(grid)-1][len(grid[0])-1]
}

分割回文串 II

132. 分割回文串 II - 力扣（LeetCode）

给定一个字符串，要求将该字符串分割成一些子串，使每个子串都是回文串，返回符合要求的 最少分割次数

思路一：回溯（超时）本质为穷举

思路二：动规

递推「最小分割次数」思路：假设最后一个回文串的起始位置为j，

dp[i]：[0,i]分割为若干回文串的最小分割次数
递推公式：
- if [j,i] is 回文串
  - dp[i] = min(dp[i], dp[j-1]+1)，(j <= i)
初始化：dp[i] = MaxInt
遍历顺序：从左到右

注意：dp[i] = min(dp2[i], dp2[j-1]+1)是要找使分割次数最小的最后一个回文串

判断「任意一段子串是否回文」思路：对于小数据范围的串可以直接用双指针判断，但对于大数据范围的串不能每次都使用双指针去线性扫描一遍判断是否回文

dp[i][j]：[i,j]是否为回文
递推公式：
- if s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1])
  - dp[i][j] = true
初始化：dp[i][j] = false
遍历顺序：从底向上，从左到右；i从尾出发向前遍历，j从i+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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41


func minCut(s string) int {
    // dp1记录[i, j]是否为回文串
    dp1 := make([][]bool, len(s))
    // dp2记录[0, i]的最少分割次数
    dp2 := make([]int, len(s))
    // 初始化dp1
    for i := range dp1 {
        dp1[i] = make([]bool, len(s))
    }
    // 初始化dp2
    for i := range dp2 {
        dp2[i] = 2000
    }
    // 填充dp1
    for i := len(s) - 1; i >= 0; i-- {
        for j := i; j < len(s); j++ {
            // 两字符相等且为同一或相邻字符或夹的字符串为回文
            if s[i] == s[j] && (j-i <= 1 || dp1[i+1][j-1]) {
                dp1[i][j] = true
            }
        }
    }
    // 填充dp2
    for i := range s {
        // 判断[0, i]是否回文
        if dp1[0][i] {
            // [0, i]无需分割
            dp2[i] = 0
            // 遍历下一字符
            continue
        }
        // 找最后一个回文串的起始位置j
        for j := 0; j < len(s); j++ {
            // 判断[j, i]是否为回文串
            if dp1[j][i] {
                dp2[i] = min(dp2[i], dp2[j-1]+1)
            }
        }
    }
    return dp2[len(s)-1]
}

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

最长回文子串

5. 最长回文子串 - 力扣（LeetCode）

给定一个字符串，返回其中最长的回文子串

思路一：动规

dp[i][j]：[i,j]是否为回文
递推公式：
- if s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1])
  - dp[i][j] = true
初始化：dp[i][j] = false
遍历顺序：从底向上，从左到右；i从尾出发向前遍历，j从i出发向后遍历

注意：当s[i]与s[j]相等时，有如下三种情况

情况一：下标i与j相同，同一个字符例如a，当然是回文子串
情况二：下标i与j相差为1，例如aa，也是回文子串
情况三：下标i与j相差大于1的时候，例如cabac，此时s[i]与s[j]已经相同了，是不是回文就看dp[i + 1][j - 1]是否为true

 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 longestPalindrome(s string) string {
    // 记录最长回文子串起始位置和长度
    start, end, length := 0, 0, 0
    // 记录[i,j]是否为回文串
    dp := make([][]bool, len(s))
    for i := range dp {
        dp[i] = make([]bool, len(s))
    }
    // i从尾向前遍历
    for i := len(s) - 1; i >= 0; i-- {
        // j从i+1向后遍历
        for j := i; j < len(s); j++ {
            // 判断是否为回文串
            if s[i] == s[j] && (j-i <= 1 || dp[i+1][j-1]) {
                // 记录回文串状态
                dp[i][j] = true
                // 找最长回文串
                if dp[i][j] && j-i > length {
                    start, end, length = i, j, j-i
                }
            }
        }
    }
    return s[start : end+1]
}

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

思路二：双指针，中心扩散

遍历每一个下标，以这个下标为中心，利用「回文串」中心对称的特点，往两边扩散，看最多能扩散多远

在遍历中心点的时候，要注意中心点有两种情况，一个元素可以作为中心点，两个元素也可以作为中心点

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


var start, end, length int

func longestPalindrome(s string) string {
    // 记录最长回文子串起始位置和长度
    start, end, length = 0, 0, 0
    for i := range s {
        extend(s, i, i)
        extend(s, i, i+1)
    }
    return s[start : end+1]
}
func extend(s string, i, j int) {
    // 中心扩散找最长回文串
    for i >= 0 && j < len(s) && s[i] == s[j] {
        if j-i > length {
            start, end, length = i, j, j-i
        }
        i--
        j++
    }
}

时间复杂度：$O(n^2)$，枚举「中心位置」时间复杂度为 O(N)，从「中心位置」扩散得到「回文子串」的时间复杂度为 O(N)O(N2)
空间复杂度：$O(1)$

最长递增子序列的个数

673. 最长递增子序列的个数 - 力扣（LeetCode）

给定一个未排序的整数数组 nums ，返回最长递增子序列的个数。可以不连续

dp[i]：以nums[i]为尾的最长递增子序列的长度
- count[i]：以nums[i]为尾的最长递增子序列的个数
递推公式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


if nums[j] < nums[i] {
    // 判断找到的是否为更长的递增子序列
    if dp[j] + 1 > dp[i] {
        // 直接更新
        count[i] = count[j]
    } else if dp[j] + 1 == dp[i] {
        // 累加个数
        count[i] += count[j]
    }
    dp[i] = max(dp[i], dp[j] + 1)
}

初始化：dp[i] = 1
- count[i] = 1
遍历顺序：从前往后

注意：最后要遍历一遍dp[i]，把最长递增序列长度对应的count[i]累计下来就是个数

 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
36
37
38
39
40
41
42
43
44
45


func findNumberOfLIS(nums []int) int {
    if len(nums) == 1 {
        return len(nums)
    }
    // 记录以nums[i]结尾的最长递增子序列长度
    dp := make([]int, len(nums))
    // 记录以nums[i]结尾的最长递增子序列个数
    count := make([]int, len(nums))
    // 记录最长递增子序列的长度
    maxLength := 0
    // 统计结果
    res := 0
    // 初始化dp,count
    dp[0], count[0] = 1, 1
    // 定子序列尾
    for i := 1; i < len(nums); i++ {
        // 初始化dp,count
        dp[i], count[i] = 1, 1
        // 定子序列首
        for j := 0; j < i; j++ {
            // 判断是否为递增
            if nums[j] < nums[i] {
                // 判断是否找到更长递增子序列
                if dp[j]+1 > dp[i] {
                    count[i] = count[j]
                } else if dp[j]+1 == dp[i] {
                    count[i] += count[j]
                }
                dp[i] = max(dp[i], dp[j]+1)
            }
        }
        // 记录最长递增子序列的长度
        if dp[i] > maxLength {
            maxLength = dp[i]
        }
    }
    // 统计最长递增子序列的个数
    for i, v := range dp {
        // 找到符合最长递增子序列长度的子序列结尾i
        if v == maxLength {
            res += count[i]
        }
    }
    return res
}

附加

杨辉三角

118. 杨辉三角 - 力扣（LeetCode）

给定一个非负整数 *numRows，*生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。

dp[i][j]：杨辉三角的i行j列元素值
递推公式：dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
初始化：dp[i][0], dp[i][i] = 1, 1
遍历顺序：从左到右，从上到下

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


func generate(numRows int) [][]int {
    dp := make([][]int, numRows)
    for i := range dp {
        dp[i] = make([]int, i+1)
        dp[i][0], dp[i][i] = 1, 1
        for j := 1; j < i; j++ {
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j]
        }
    }
    return dp
}

乘积最大子数组

152. 乘积最大子数组 - 力扣（LeetCode）

给定一个整数数组 nums ，找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积

dpMax[i]：以nums[i]结尾的子数组的最大乘积；dpMin[i]：以nums[i]结尾的子数组的最小乘积
递推公式：
- if nums[i] >= 0
  - dpMax[i] = max(dpMax[i-1] * nums[i], nums[i])
  - dpMin[i] = min(dpMin[i-1] * nums[i], nums[i])
- else
  - dpMax[i] = max(dpMin[i-1] * nums[i], nums[i])
  - dpMin[i] = min(dpMax[i-1] * nums[i], nums[i])
初始化：dpMax[0], dpMin[0] = nums[0], nums[0]
遍历顺序：从左到右

注意：以nums[i]结尾，说明nums[i]是一定要选的，要么是续着前一个，要么是从当前开头

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


func maxProduct(nums []int) int {
    res := nums[0]
    // dpMax[i]: 以nums[i]结尾的子数组最大乘积
    // dpMin[i]: 以nums[i]结尾的子数组最小乘积
    dpMax, dpMin := make([]int, len(nums)), make([]int, len(nums))
    // 初始化
    dpMax[0], dpMin[0] = nums[0], nums[0]
    // 遍历nums
    for i := 1; i < len(nums); i++ {
        if nums[i] >= 0 {
            // max/min(续前一个元素,以当前为首重新开始)
            dpMax[i] = max(dpMax[i-1]*nums[i], nums[i])
            dpMin[i] = min(dpMin[i-1]*nums[i], nums[i])
        } else {
            // nums[i]为负数,交换最大值与最小值
            dpMax[i] = max(dpMin[i-1]*nums[i], nums[i])
            dpMin[i] = min(dpMax[i-1]*nums[i], nums[i])
        }
        // 记录最大值
        res = max(dpMax[i], res)
    }
    return res
}

时间复杂度：O(N)，这里 N 表示数组的长度；
空间复杂度：O(N)，使用了两个状态数组，每一个数组的规模是 N

因为每一个状态只与前一个状态有关，可以使用「滚动变量」技巧，使用常数个变量完成这道问题

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


func maxProduct(nums []int) int {
    res := nums[0]
    // 前一元素为尾的最大/小值,当前元素为尾的最大/小值
    preMax, preMin, curMax, curMin := nums[0], nums[0], 0, 0
    // 遍历nums
    for i := 1; i < len(nums); i++ {
        if nums[i] >= 0 {
            // max/min(续前一个元素,以当前为首重新开始)
            curMax = max(preMax*nums[i], nums[i])
            curMin = min(preMin*nums[i], nums[i])
        } else {
            // nums[i]为负数,交换最大值与最小值
            curMax = max(preMin*nums[i], nums[i])
            curMin = min(preMax*nums[i], nums[i])
        }
        // 更新pre
        preMax, preMin = curMax, curMin
        // 记录最大值
        res = max(curMax, res)
    }
    return res
}

时间复杂度：O(N)，这里 N 表示数组的长度；
空间复杂度：O(1)，使用了常数个变量

最长有效括号

32. 最长有效括号 - 力扣（LeetCode）

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

方法一：动态规划

dp[i]：以nums[i]结尾的最长有效括号长度
递推公式：
- if s[i]=')' && s[i−1]='('
  - dp[i] = dp[i−2] + 2
- else if s[i]=')' && s[i−1]=')' && s[i −dp[i−1]− 1]='('
  - dp[i] = dp[i−2] + 2 + dp[i−dp[i−1]−2]
初始化：全为0
遍历顺序：从左到右

注意：

有效的子串一定以)结尾且非首，因此首和以 ( 结尾的子串 dp 值必定为 0 ，只需要求解 ) 在 dp 数组中对应位置的值
从前往后遍历字符串求解 dp 值，每两个字符检查一次
若s[i]=')'且 s[i−1]='('，也就是字符串形如 ……()，可以推出：dp[i] = dp[i−2] + 2；之所以可以进行这样的转移，是因为当前最后的俩字符 () 是一个有效子字符串，并且将之前有效子字符串的长度增加了 2
若s[i]=')' 且 s[i−1]=')'，也就是字符串形如 ……))，若s[i−dp[i−1]−1]='('，那么说明当前 ) 有匹配的(，假设倒数第二个)有匹配的(，那么当前)匹配的(的位置一定在倒数第二个 ) 匹配的(的前面，最后把当前 ) 匹配的(前面的有效子串长度也加上，由此可以推出dp[i] = dp[i−2] + 2 + dp[i−dp[i−1]−2]
最后的答案即为 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
27
28
29
30
31


func longestValidParentheses(s string) int {
    res := 0
    // dp[i]: 以nums[i]结尾的最长有效括号子串长度
    dp := make([]int, len(s))
    // 遍历字符串
    for i := 1; i < len(s); i++ {
        // 判当前字符是否为右括号且非首(有效结尾一定是右括号)
        if s[i] == ')' {
            // 判前一个是否为左括号
            if s[i-1] == '(' {
                if i >= 2 {
                    // 在前前字符结尾的基础上+2(算上当前字符和前一字符)
                    dp[i] = dp[i-2] + 2
                } else {
                    // 当前字符是第二个字符,直接置2
                    dp[i] = 2
                }
            } else if i >= dp[i-1]+1 && s[i-dp[i-1]-1] == '(' { // 判前一个字符也为一个有效子串右括号情况下当前字符是否有匹配的左括号
                if i >= dp[i-1]+2 {
                    // 在前一个字符基础上加2且加上前一字符有效串首前一字符作为尾的有效串长度
                    dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
                } else {
                    dp[i] = dp[i-1] + 2
                }
            }
        }
        // 更新记录的目前最大长度
        res = max(res, dp[i])
    }
    return res
}

时间复杂度： O(n)，其中 n 为字符串的长度。只需遍历整个字符串一次，即可将 dp 数组求出来
空间复杂度： O(n)，需要一个大小为 n 的 dp 数组

方法二：栈

遍历字符

若遇到( ，则入栈
若遇到 ) ，则先弹栈，表示匹配了当前右括号：
- 若栈为空，说明当前的右括号为没有被匹配的右括号，将其下标放入栈中
- 若栈不为空，当前右括号的下标减去栈顶元素即为「以该右括号为结尾的最长有效括号的长度」

起初的思路（行不通）

从左往右扫描，已扫描的左括号等待被匹配，用一个栈暂存起来
题目是求长度，存左括号的索引即可，没必要存符号本身
当扫描到右括号，它匹配最近一个左括号，栈顶被匹配而出栈，有效长度 = 当前索引-出栈的索引+1，并挑战一下全局的最大
如图，当遍历到索引为 6 的右括号时，此时栈中的左括号匹配光了，但左边有一整段长度为 6 的有效子串，没有被计算，让索引 6 减 0？不对，索引 0 已经出栈了。或许让 5 减 -1？

修改后的思路

在栈中预置-1作为“参照物”，并改变计算方式：当前索引 - 出栈后新的栈顶索引

当遍历到索引 5 的右括号，此时栈顶为 2，出栈，栈顶变为 -1，有效长度为 5 - (-1)。如果照之前那样，5 找不到 -1 减
现在有个问题：当遍历到索引 6 的右括号，它不是需要入栈的左括号，又没有左括号可匹配，怎么处理它？
它后面也可能出现这么一段有效长度，它要成为 -1 那样的“参照物”。它之前出现的有效长度都已计算，-1 的使命已经完成了，要被替代
所以照常让 -1 出栈。重点是，此时栈空了，让索引 6 入栈取代它

总结：两种索引会入栈

等待被匹配的左括号索引。
充当「参照物」的右括号索引。因为：当左括号匹配光时，栈需要留一个垫底的参照物，用于计算一段连续的有效长度

 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 longestValidParentheses(s string) int {
    res := 0
    stack := make([]int, 0)
    // -1入栈当参照物
    stack = append(stack, -1)
    // 遍历字符串
    for i, ch := range s {
        if ch == ')' {
            // 栈顶出栈
            stack = stack[:len(stack)-1]
            // 判栈非空
            if len(stack) != 0 {
                // 算有效子串长度 更新最大值
                res = max(res, i-stack[len(stack)-1])
            } else {
                // 更新参照物
                stack = append(stack, i)
            }
        } else {
            // 左括号入栈
            stack = append(stack, i)
        }
    }
    return res
}

时间复杂度： O(n)，n 是给定字符串的长度。只需要遍历字符串一次即可
空间复杂度： O(n)，栈的大小在最坏情况下会达到 n，因此空间复杂度为 O(n)

方法三：贪心

利用两个计数器left和right。首先，从左到右遍历字符串，对于遇到的每个 (，增加left计数器，对于遇到的每个 ) ，增加 right 计数器。每当 left 计数器与 right 计数器相等时，计算当前有效字符串的长度，并且更新目前为止找到的最长子字符串。当 right 计数器比 left 计数器大时，将 left 和 right 计数器同时变回 0

这样的做法贪心地考虑了以当前字符下标结尾的有效括号长度，每次当右括号数量多于左括号数量的时候之前的字符都扔掉不再考虑，重新从下一个字符开始计算，但这样会漏掉一种情况，就是遍历的时候左括号的数量始终大于右括号的数量，即 (() ，这种时候最长有效括号是求不出来的

解决的方法也很简单，只需要从右往左遍历用类似的方法计算即可，只是这个时候判断条件反了过来：

当 left 计数器比 right 计数器大时，将 left 和 right 计数器同时变回 0
当 left 计数器与 right 计数器相等时，计算当前有效字符串的长度，并且记录目前为止找到的最长子字符串

这样我们就能涵盖所有情况从而求解出答案

 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
36
37
38
39
40
41
42


func longestValidParentheses(s string) int {
    res := 0
    // 计数左右括号
    left, right := 0, 0
    // 正序遍历字符串
    for _, ch := range s {
        // 更新计数
        if ch == '(' {
            left++
        } else {
            right++
        }
        // 判相等
        if left == right {
            res = max(res, 2*left)
        }
        // 判右多于左
        if right > left {
            left, right = 0, 0
        }
    }
    // 重置计数
    left, right = 0, 0
    // 倒序遍历字符串
    for i := len(s) - 1; i >= 0; i-- {
        // 更新计数
        if s[i] == '(' {
            left++
        } else {
            right++
        }
        // 判相等
        if left == right {
            res = max(res, 2*left)
        }
        // 判左多于右
        if left > right {
            left, right = 0, 0
        }
    }
    return res
}

时间复杂度： O(n)，其中 n 为字符串长度。只要正反遍历两边字符串即可
空间复杂度： O(1)，只需要常数空间存放若干变量

最大正方形

221. 最大正方形 - 力扣（LeetCode）

在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积

dp[i][j]: 以[i, j]为右下角的只包含1的正方形的边长
递推公式：
- 如果该位置的值是 0，则 dp[i][j]=0，因为当前位置不可能在由 1 组成的正方形中；
- 如果该位置的值是 1，则 dp[i][j] 的值由其上方、左方和左上方的三个相邻位置的 dp 值决定。具体而言，当前位置的元素值等于三个相邻位置的元素中的最小值加 1，状态转移方程如下：dp[i][j]=min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
初始化：初始化为给定matrix
遍历顺序：从左往右，从上往下

注意：遍历第一排第一列时，若遇到1，则初始化maxEdge为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
26
27


func maximalSquare(matrix [][]byte) int {
    maxEdge := 0
    // dp[i][j]: 以[i, j]为右下角的只包含'1'的正方形边长
    dp := make([][]int, len(matrix))
    // 初始化dp
    for i := range dp {
        dp[i] = make([]int, len(matrix[0]))
        for j := range dp[i] {
            dp[i][j] = int(matrix[i][j] - '0')
            if dp[i][j] == 1 {
                maxEdge = 1
            }
        }
    }
    // 遍历矩阵
    for i := 1; i < len(matrix); i++ {
        for j := 1; j < len(matrix[0]); j++ {
            // 判当前位是否为1
            if dp[i][j] == 1 {
                // min(上, 左, 左上)+1
                dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                maxEdge = max(maxEdge, dp[i][j])
            }
        }
    }
    return maxEdge * maxEdge
}

时间复杂度：$O(mn)$
空间复杂度：$O(mn)$

戳气球

312. 戳气球 - 力扣（LeetCode）

有 n 个气球，编号为0 到 n - 1，每个气球上都标有一个数字，这些数字存在数组 nums 中。现在要求戳破所有的气球。戳破第 i 个气球，可以获得 nums[i - 1] * nums[i] * nums[i + 1] 枚硬币。这里的 i - 1 和 i + 1 代表和 i 相邻的两个气球的序号。如果 i - 1或 i + 1 超出了数组的边界，那么就当它是一个数字为 1 的气球。求所能获得硬币的最大数量

区间dp

dp[i][j]：戳破(i, j)内所有气球能拿到的最多金币
递推公式：dp[i][j] =max(dp[i][j], dp[i][k] + val[i]*val[k]*val[j] + dp[k][j])
初始化：全0
遍历顺序：小区间->大区间

注意：

为了防止下标越界，对nums两边加上题目中假设存在的nums[−1] = 1和 nums[n] = 1
假设k是区间内最后一个被戳破的气球，戳爆k时区间内只剩下i、k、j三个气球，此时得到的金币数量就是total = dp[i][k] + val[i]*val[k]*val[j] + dp[k][j]
在 (i, j) 开区间可以选的 k 是有多个的，所以需要在区间内枚举 k，从中选择使得 total 值最大的更新该区间可获取的最多金币数 dp[i][j]
(i, j) 开区间从只有三个数字的时计算，储存每个小区间可以得到金币的最大值，然后慢慢扩展到更大的区间，利用小区间里已经算好的数字来算更大的区间

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


func maxCoins(nums []int) int {
    // 首尾加1
    nums = append([]int{1}, append(nums, 1)...)
    // dp[i][j]: (i, j)区间内获得的最多金币
    dp := make([][]int, len(nums))
    for i := range dp {
        dp[i] = make([]int, len(nums))
    }
    // 定首 从倒数第三个开始
    for i := len(nums) - 3; i >= 0; i-- {
        // 定尾 初始长度为3
        for j := i + 2; j < len(nums); j++ {
            // (i, j)区间内枚举k(最后一个戳破的气球的索引)
            for k := i + 1; k < j; k++ {
                // 取该区间内最大值
                dp[i][j] = max(dp[i][j], dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j])
            }
        }
    }
    return dp[0][len(nums)-1]
}

正则表达式匹配

10. 正则表达式匹配 - 力扣（LeetCode）

给定一个字符串和一个正则表达式，判断该字符串是否能够完全匹配该正则表达式

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素

思路：

dp[i][j]：s的前i个字符是否匹配p的前j个字符，从1计
初始化：dp[0][0] = true，即两个空串可匹配

题解

 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
36
37
38


func isMatch(s string, p string) bool {
    // dp[i][j]: s的前i个字符是否匹配p的前j个字符，从1计
    dp := make([][]bool, len(s)+1)
    for i := range dp {
        dp[i] = make([]bool, len(p)+1)
    }
    // 初始化:两个空串可匹配
    dp[0][0] = true
    // 初始化当 s 为空时，p 的匹配情况
    for j := 2; j <= len(p); j++ {
        // 判模式字符是否为 '*'
        if p[j-1] == '*' {
            // 参考前两个字符的匹配情况(该字母+*之前的情况)
            dp[0][j] = dp[0][j-2]
        }
    }
    // 遍历字符串
    for i := 1; i <= len(s); i++ {
        // 遍历正则式
        for j := 1; j <= len(p); j++ {
            // 判俩字符是否相等或模式字符为.
            if s[i-1] == p[j-1] || p[j-1] == '.' {
                // 俩字符匹配成功 参考前一个字符匹配情况
                dp[i][j] = dp[i-1][j-1]
            } else if p[j-1] == '*' { // 如果模式字符为 '*'
                // 检查前一个字符是否匹配
                if s[i-1] == p[j-2] || p[j-2] == '.' {
                    // 让p[j-2](*前字符)重复0、1、>=2次
                    dp[i][j] = dp[i][j-2] || dp[i-1][j-2] || dp[i-1][j] // 继承不同情况的匹配结果
                } else {
                    // 浪费掉该字符+*
                    dp[i][j] = dp[i][j-2] // 直接继承左边的匹配情况
                }
            }
        }
    }
    return dp[len(s)][len(p)]
}

环形子数组的最大和

918. 环形子数组的最大和 - 力扣（LeetCode）

给定一个环形整数数组，返回最大子数组和

思路：dp+反向思考

最大子数组一共有两种情况：

第一种情况：首尾不相连，最大子数组不是环状的，直接求出最大子数组和
第二种情况：首尾相连，最大子数组一部分在首部，一部分在尾部；可以用数组总和-首尾不相连的最小子数组和反推出最大子数组和

归纳上面两种情况可得最大子数组和 = max(首尾不相连，首尾相连)

特殊情况：数组元素全部为负。第一种情况的最大子数组和会等于数组中的最大值；第二种情况的最小子数组和就是数组总和；最后求得最大子数组和为0，正确应该为第一种情况求得的数组中的最大值（最小负数）。所以多加一个case，判断第一种情况下求得的最大子数组和是否小于0，若小于，则直接返回该值。

 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 maxSubarraySumCircular(nums []int) int {
    // dp1[i]:以nums[i]结尾的最大子数组和
    // dp2[i]:以nums[i]结尾的最小子数组和
    dp1 := make([]int, len(nums))
    dp2 := make([]int, len(nums))
    dp1[0], dp2[0] = nums[0], nums[0]
    maxS, minS := nums[0], nums[0]
    total := nums[0]
    for i := 1; i < len(nums); i++ {
        // 统计数组总和
        total += nums[i]
        // max/min(在前一基础上加当前元素, 从当前元素重新开始)
        dp1[i] = max(dp1[i-1]+nums[i], nums[i])
        dp2[i] = min(dp2[i-1]+nums[i], nums[i])
        // 统计首尾不相连的最大/小子数组和
        maxS = max(maxS, dp1[i])
        minS = min(minS, dp2[i])
    }
    // 判是否全部元素为负
    if maxS < 0 {
        // 直接返回最小负数
        return maxS
    }
    // max(首尾不相连, 首尾相连)
    return max(maxS, total-minS)
}

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