动态规划

理论基础

动态规划，英文：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


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]
}

时间复杂度: $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]：以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]+1)
初始化：dp[0][0] = 0, dp[0][j] = j, dp[i][0] = i
遍历顺序：从左到右，从上到下

注意：

删除和添加是互为逆向的操作
两个元素不相：在添加、删除和替换操作中选一个最小的
由于是第一层循环是从word1的下标1开始遍历，所以当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]
}

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

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

 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++
    }
}

最长递增子序列的个数

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
}