动态规划

理论基础

动态规划，英文：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(2^N)

1
2
3
4
5
6


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

爬楼梯

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

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

进阶：爬楼梯:每次至多可爬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
 9
10
11
12
13


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

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

不同路径

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

不同路径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
遍历顺序：从左往右，从上往下

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

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
}

不同的二叉搜索树

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

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
}

最后一块石头的重量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
}

目标和

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[5]=dp[0]+dp[1]+dp[2]+dp[3]+dp[4]+dp[5]
dp[0] = 1：背包容量为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]
}

一和零

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
}

完全背包问题

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

组合总和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]
}

爬楼梯（进阶版）

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

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

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

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

零钱兑换

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


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
}

完全平方数

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=最小值
外层遍历物品时，物品=完全平方数，从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]
}

单词拆分

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

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

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

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

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

注意：

if((j，i) && dp[j]=true)：前提是j<i，当j到i之间的字符串能被数组中元素匹配，且之前的0到j之间的字符串也已经被成功匹配，则说明0到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


func wordBreak(s string, wordDict []string) bool {
    wordDictMap := make(map[string]bool)
    for _, v := range wordDict {
        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++ { // 遍历子串(定子串起始位置)
            if dp[j] && wordDictMap[s[j:i]] { // [0,j]匹配成功
                dp[i] = true // [j,i]匹配成功
                break        // 当前最终位置的字符串已经匹配成功
            }
        }
    }
    return dp[w]
}

多重背包问题

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

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

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

注意：

将同一物品的多个数量分为多行，即转换为01背包问题，每行的物品只能用一次
物品有几个就将内层循环遍历背包容量执行几次，也就是几个物品就是几排

 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 multipleBag() int {
    dp := make([]int, w+1)
    // AC:75%:潜在的数组或指针越界
    for i := 0; i < n; i++ { // 定物品
        for k := 1; k <= count[i]; k++ { // 该物品有几个就遍历几次背包容量
            for j := w; j >= weight[i]; j-- { // 遍历背包容量
                dp[j] = max(dp[j], dp[j-weight[i]]+value[i])
            }
        }
    }
    for i := 0; i < n; i++ { // 定物品
        for j := w; j >= weight[i]; j-- { // 遍历背包容量
            for k := 1; k <= count[i] && (j - k*weight[i]) >= 0; k++ {
                dp[j] = max(dp[j], dp[j-k*weight[i]] + k*value[i]);
            }
        }
    }
    return dp[w]
}
func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

打家劫舍

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])
遍历顺序：从小到大

注意：

i-2：i前面和i隔了一个元素的元素
取i：dp[i-2]+nums[i]
不取i：dp[i-1]，考虑i-1但不一定取i-1

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

打家劫舍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
16
17
18
19
20
21
22
23


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

打家劫舍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}
}

买卖股票的最佳时机

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天持有分为两种情况；一种是和前一天一样本来就持有；另一种是之前一直不持有；但今天买入所以持有；取两种情况中的最大值
初始金额为零；第一天买入的话就是负的元素值
最后返回最后一天不持有股票的最大金额即可

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

买卖股票的最佳时机 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]
}

买卖股票的最佳时机 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;
遍历顺序：从前往后

注意：

最后返回第二次不持有的最大金额：第二次不持有包含第一次不持有
初始化可以理解为第一天买入又卖出再买入再卖出

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

买卖股票的最佳时机 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][2*j-3]-prices[i]) // 第j次持有
            }
            dp[i][2*j-1] = max(dp[i-1][2*j-1], dp[i][2*j-2]+prices[i]) // 第j次不持有
        }
    }
    return dp[length-1][2*k-1]
}

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

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

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

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

最长递增子序列

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

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

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

注意：

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

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


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
}

最长连续递增序列

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
}

最长重复子数组

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就行；内外层遍历都从下标1开始；定义dp数组时要覆盖边界i和j；若用i和j结尾，dp[i][0]：要用第二个数组中第一个元素和第一个数组中所有元素进行比较，若一样则初始化为1，否则初始化为0，dp[0][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
}

最长公共子序列

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

不相交的线

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
}

判断子序列

392. 判断子序列 - 力扣（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
遍历顺序：从左到右，从上到下

注意：

最后求得的最长公共子序列长度若等于第一个字符串的长度，则返回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] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    return dp[len(s)][len(t)] == len(s)
}

双指针法：双指针指向两个字符串的开头，遍历第二个字符串时遇到与第一个字符相等的字符时，指针一后移一个，当指针一遍历完第一个字符串时直接返回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
}

不同的子序列

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

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

dp[i][j]：以i-1为尾的s中有以j-1为尾的个数
递推公式：
- 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[i][0] = 1; dp[0][j] = 0
遍历顺序：从左到右，从上到下

注意：

dp[i-1][j-1] + dp[i-1][j]：当两个元素相等时，就不用再考虑该元素，只需要考虑该元素前面的以i-2为尾的s中有多少个以j-2为尾的t；还要考虑另一种情况，该元素前面的以i-2为尾的s中有多少个以j-1为尾的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)]
}

两个字符串的删除操作

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

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

编辑距离

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，因此需要在循环前判断，当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)]
}

回文子串

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）长度为1一定是回文串；第二种情况是j和i是相邻的两个相同元素（j-i=1）长度为2一定是回文串；第三种情况是j和i中间还有其他元素，这需要进一步判断i的后一个元素与j的前一个元素是否是回文子串，若[i+1,j-1]是回文子串，则再加上s[i]=s[j]说明[i,j]也是回文子串
由递推公式看出，dp[i][j]由左下角状态推导得出
第二层循环j从i开始，确保j大于等于i
相当于第一层循环定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
}

最长回文子序列

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
遍历顺序：从下往上，从左往右

注意：

当两个元素相等时，在[i+1,j+1]最长回文子序列长度的基础上加上左右i和j两个元素
当两个元素不相等时，分为两种情况：考虑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]
}