动态规划总结

动态规划

问题介绍

大致做法：大问题分解为小问题，存储子问题的解避免重复计算。

最优子结构：原问题的最优解是从子问题的最优解构造来的

重叠子问题：相同的问题会被多次计算

无后效性：问题的当前状态的最优解不受其未来状态的影响

存储子问题的解：通常使用表格（数组或者哈希表）来存储子问题的解

计算顺序：子问题间存在依赖性，要保证计算一个子问题前，其依赖的所有子问题已经解决

代码实际概念

状态：子问题的定义，通常用一个或者多个变量来表示

状态转移方程：描述如何从已知子问题的解来计算另一个子问题的解的公式

边界条件：子问题的基本情况，常用于递归算法的基准情况

动态规划表：通常是一个表格，用来存储子问题的解，避免重复计算

何时应用动态规划

  • 问题是否可以被分解为子问题？ 这意味着问题可以递归地解决。
  • 子问题之间是否存在重叠？ 如果是，每个子问题是否在整个过程中被多次计算？
  • 问题是否具有最优子结构？ 即你可以通过组合子问题的最优解来得到原问题的最优解。

经典问题

  1. 背包问题：求解如何在一个限定容量的背包中放入不同物品使得价值最大化。
  2. 最长公共子序列问题：找到两个字符串的最长公共子序列。
  3. 矩阵路径问题：求解从矩阵的一个角到另一个角的最短路径、最大路径等。
  4. 股票买卖问题：给定一段时间的股票价格，求最大利润。
  5. 编辑距离问题：最少的操作次数将一个字符串转换为另一个字符串。

问题通解

第一步、描述决策、定义状态、建立dp表、

​ 确定dp表的下标含义和大小

第二步、思考子问题条件（利用反推）推导状态转移方程、

​ 子问题可以简单粗暴由原问题更改为中间值i

​ 思考子问题由什么条件来，进而推导状态转移方程

第三步、确定边界条件（初始条件）

第四步、确定状态转移顺序——

​ 备忘录法，自顶向下，递归；

​ dp数组法，自底向上，递归消除；

​ 是否可能覆盖需要的数据

第五步、举例推导dp数组

个人思考

确定使用动态规划要看最优子结构，也就是每一步的决策都能依赖于前面部分解的结果，站在第i步看能够发现i的结果依赖于先前的哪些结果，能够发现问题能够被分解为子问题，子问题存在对子问题的子问题的依赖结构。即先前决策影响后续决策且依赖关系确定的题目都用动态规划。

确定状态是什么也很重要，对状态的定义一定要自己想清楚，dp表往往就是问题要求的答案。

在确定状态的定义和dp表的建立后（也就是第二步），从某个i条件开始思考，先反推什么条件会推导到i条件，确定下来什么条件能够推导到i条件后就可以依据最优情况构建状态转移方程了。

下标：由于数组第0位是有数据的，而正常数数的时候是从1开始的，所以处理下标的时候要小心，思考问题时从正常数数的角度出发即可，所以在定义dp表（经常看到dp表大小为(n+1)*(cap+1)，0那位都不care）、状态转移方程的时候都是从正常数数出发开始计算的，初始化dp表的时候可能需要稍微考虑一下0那一位

背包问题-价值最大化，硬币问题-统计方案数量

经典题目

基础问题

斐波那契数

思路

这道题目已经把所有需要的条件都给我们了。

  1. 首先定义状态，建立dp表

    dp[i]表示第i个斐波那契数的数值

  2. 定义子问题，推导递推公式

    dp[i]由dp[i-1]和dp[i-2]转移而来，题目已经给出**dp[i] = dp[i - 1] + dp[i - 2]**

  3. 确定边界条件

    题目已经给出，dp[0]=0,dp[1]=1

  4. 确定转移顺序

    dp[i]由dp[i-1]和dp[i-2]转移而来，转移顺序为从前往后

  5. 空间优化

    发现dp[i]只依赖于前两次计算出来的dp[i-1]和dp[i-2]，先前的计算结果都不需要，因此可以用两个变量来承接

代码

dp表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func fib(n int) int {
	//先把0和1处理了，省的后续动态规划初始化越界
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	//创建dp表
	dp := make([]int, n+1)
	//临界条件
	dp[0], dp[1] = 0, 1
	//状态转移
	for i := 2; i <= n; i++ {
		dp[i] = dp[i-1] + dp[i-2]
	}
	return dp[n]
}

空间优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// F(0) = 0，F(1) = 1
// F(n) = F(n - 1) + F(n - 2)，其中 n > 2
func fib(n int) int {
	//临界情况
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	//计算F[2]及以后的斐波那契数
	a, b := 0, 1
	for i := 2; i <= n; i++ {
		a, b = b, a+b
	}
	return b
}

递归，没有记忆就、状态，重复计算

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

爬楼梯

思路

  1. 建立dp表

    dp[i]表示爬到第i台阶的方法数

  2. 推导状态转移方程

    要爬到第i级台阶，可以从i-2和i-1爬上来，方法数应该取两者累和，dp[i]=dp[i-2]+dp[i-1]

  3. 确定边界条件

    跳上第一、二个台阶的方法数，dp[1]=1,dp[2]=2

  4. 确定状态转移顺序

    从0开始往后

  5. 空间优化

    发现dp[i]只依赖于前两次计算出来的dp[i-1]和dp[i-2]，先前的计算结果都不需要，因此可以用两个变量来承接

代码

一维空间的dp表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func climbStairs(n int) int {
	//临界条件
	if n == 1 {
		return 1
	}
	if n == 2 {
		return 2
	}
	dp := make([]int, n+1)
	dp[1], dp[2] = 1, 2
	//状态转移
	for i := 3; i <= n; i++ {
		dp[i] = dp[i-2] + dp[i-1]
	}
	return dp[n]
}

空间优化，同时把n较小（1，2，3）的情况进行了合并

1
2
3
4
5
6
7
8
9
10
11
func climbStairs1(n int) int {
	//n=1,2,3时答案就是n
	if n < 4 {
		return n
	}
	a, b := 2, 3 //对应dp[2],dp[3]开始求解
	for i := 4; i <= n; i++ {
		a, b = b, a+b //dp[i-1],dp[i]=dp[i-1],dp[i-2]+dp[i-1]
	}
	return b
}

使用最小花费爬楼梯

思路

  1. 建立dp表

    dp[i]表示登上第i个台阶的最低花费，dp表长度为n+1，从0一直到n

  2. 推导状态转移方程

    登上第i个阶梯，可以由第i-2个阶梯支付第i-2个台阶的费用，爬2个阶梯；也可以由第i-1个阶梯，支付第[i-1]个阶梯的费用，爬1个阶梯。

    fp表的定义可得，两者应该取最小的，dp[i]=min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1])

  3. 确定边界条件

    可以选择从下标为 0 或 1 的元素作为初始阶梯，则dp[0]=0，dp[1]=0

  4. 确定转移顺序

    从0开始往后

  5. 空间优化

    发现dp[i]只依赖于前两次计算出来的dp[i-1]和dp[i-2]，先前的计算结果都不需要，因此可以用两个变量来承接

其实还有其他角度改变这道题的思路，如反向爬楼梯（从楼梯顶爬到0或1），逆序思想挺厉害的，有时候能够简化问题。

代码

按照题意实现的动态规划

1
2
3
4
5
6
7
8
9
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	dp := make([]int, n+1)
	dp[0], dp[1] = 0, 0
	for i := 2; i <= n; i++ {
		dp[i] = min(dp[i-2]+cost[i-2], dp[i-1]+cost[i-1])
	}
	return dp[n]
}

空间优化

1
2
3
4
5
6
7
8
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	a, b := 0, 0
	for i := 2; i <= n; i++ {
		a, b = b, min(a+cost[i-2], b+cost[i-1])
	}
	return b
}

反向爬楼梯，这题不太推荐

1
2
3
4
5
6
7
8
9
10
11
//支付费用了才能向上爬的做法
//逆序，从上往下
func minCostClimbingStairs(cost []int) int {
	n := len(cost)
	dp := make([]int, n+1)
	dp[n], dp[n-1] = 0, cost[n-1]
	for i := n - 2; i >= 0; i-- {
		dp[i] = min(dp[i+2], dp[i+1]) + cost[i]
	}
	return min(dp[0], dp[1])
}

不同路径

思路

dfs搜索，先略过

动态规划

  1. 确定dp表

    dp[i][j]表示从(0,0)出发到(i,j)的路径数，dp表大小为m*n，最终到达(m-1,n-1)。此处没有在左上方采用多添加一行和一列来简化初始条件的做法。

  2. 推导状态转移方程

    (i,j)可以由(i-1,j)和(i,j-1)走一步到达，路径数为两者之和，即dp[i][j]=dp[i-1][j]+dp[i][j-1]

  3. 确定临界条件

    要想到达首行的位置，只能从原点不断向右移动；同样要想到达首列的位置，只能从原点不断向下移动。所以首行和首列的位置只有一种到达路径，即dp[i][0]=1,dp[0][j]=1

  4. 确定状态转移顺序

    dp[i][j]是从其左方和上方推导而来，只要从左到右一层一层遍历即可

  5. 空间优化

    dp[i][j]只依赖于dp[i-1][j]和dp[i][j-1]，因此可以只用一维数组来承接每一层的计算结果。在计算新的一层时，上层的结果都还保留在数组中，也就是说dp[i-1][j]已经存在dp[j]了，根据状态转移方程，还差dp[i][j-1]，dp[i][j-1]刚好刚计算过是dp[j-1]，故dp[j]+=dp[j-1]。

    临界条件是计算第一层dp[i]=1

排列组合

C(m+n-2,m-1)秒了

代码

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func uniquePaths(m int, n int) int {
	//创建dp表
	dp := make([][]int, m)
	for i, _ := range dp {
		dp[i] = make([]int, n)
	}
	//临界
	for i := 0; i < m; i++ {
		dp[i][0] = 1
	}
	for j := 0; j < n; j++ {
		dp[0][j] = 1
	}
	//状态转移
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-1]
}

排列组合

1
2
3
4
//数学魔法，排列组合秒了
func uniquePaths1(m, n int) int {
	return int(new(big.Int).Binomial(int64(m+n-2), int64(n-1)).Int64())
}

不同路径2

多了障碍物，但是思路类似，数学用不了了，用动态规划

思路

  1. 确定dp表

    dp[i][j]表示从(0,0)出发到(i,j)的路径数，dp表大小为m*n，最终到达(m-1,n-1)。此处没有在左上方采用多添加一行和一列来简化初始条件的做法。

  2. 推导状态转移方程

    当(i,j)不是1即没有阻挡时，(i,j)可以由(i-1,j)和(i,j-1)走一步到达，路径数为两者之和，即dp[i][j]=dp[i-1][j]+dp[i][j-1]

    当(i,j)是1，有阻挡时，永远不可能到达，dp[i][j]=0

  3. 确定临界条件

    要想到达首行的位置，只能从原点不断向右移动；同样要想到达首列的位置，只能从原点不断向下移动。所以首行没障碍的点dp[i][0]=1，有障碍的该点及后续的位置dp[i][0]=0。首列同理，没障碍的点dp[0][j]=1，有障碍的该点及后续的位置dp[0][j]=0

  4. 状态转移顺序

    dp[i][j]是从其左方和上方推导而来，只要从左到右一层一层遍历即可

  5. 空间优化

    dp[i][j]只依赖于dp[i-1][j]和dp[i][j-1]，因此可以只用一维数组来承接每一层的计算结果。在计算新的一层时，上层的结果都还保留在数组中，也就是说dp[i-1][j]已经存在dp[j]了，根据状态转移方程，还差dp[i][j-1]，dp[i][j-1]刚好刚计算过是dp[j-1]，故dp[j]+=dp[j-1]。

    临界条件是计算第一层时，无障碍dp[i]=1，有障碍后续dp[i]=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 uniquePathsWithObstacles(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	//dp表
	dp := make([][]int, m)
	for i, _ := range dp {
		dp[i] = make([]int, n)
	}
	//临界
	for i := 0; i < m&&obstacleGrid[i][0] == 0; i++ {
		dp[i][0] = 1
	}
	for j := 0; j < n&&obstacleGrid[0][j] == 0; j++ {
		dp[0][j] = 1
	}
	//状态转移
	for i := 1; i < m; i++ {
		for j := 1; j < n; j++ {
            //有障碍物的格子默认是0，直接继续循环
			if obstacleGrid[i][j] == 1 {
				continue
			} 
			dp[i][j] = dp[i-1][j] + dp[i][j-1]
		}
	}
	return dp[m-1][n-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
//空间优化，一行一行求解累和就消除了多一维度的dp表
func uniquePathsWithObstacles1(obstacleGrid [][]int) int {
	m, n := len(obstacleGrid), len(obstacleGrid[0])
	//dp表
	f := make([]int, n)
	//初始条件
	if obstacleGrid[0][0] == 0 {
		f[0] = 1
	}
	//状态转移
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			//该格子有障碍，无法走到该格子
			if obstacleGrid[i][j] == 1 {
				f[j] = 0
				continue
			}
            //该位置左边不是1,即左边一个格子没有障碍，确保能从左边走到(i,j)
			// if j > 0 && obstacleGrid[i][j-1] == 0 {
            //哪怕不满足obstacleGrid[i][j-1] == 0也可以，因为该情况下f[j-1]=0，f[j]加0仍然正确
			if j > 0 {
				//f[j]本来存的是上一行的内容，只需要加上已经计算过的左边一个的方法数即可
				f[j] += f[j-1]
			}
		}
	}
	return f[n-1]
}

整数拆分

从拆分的角度想，一个数被拆成i和j后，i和j仍然可以往下拆解，因此就形成了子问题，可以采用动态规划来实现

思路

动态规划

  1. 确定dp表

    dp[i]表示分拆数字i可以得到的最大乘积

  2. 推导状态转移方程

    一个数可以被拆分成两个数，也就是(i-j)*J，j能被继续拆分，取最大的就是(i-j)*dp[j]，为满足比较时的存储问题，故dp[i] = max(dp[i], (i - j) * j, dp[i - j] * j)

  3. 确定边界条件

    dp[0]和dp[1]其实都毫无意义，不纠结让它为0，只初始化dp[2]=1

  4. 确定转移顺序

    从小到大，j从1开始枚举到i-1，但可以根据数学规律优化为i/2，拆成m个近似数组的子数 相乘才是最大的，至少拆成两个数，j最差取一半。

贪心

以后再说

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//我搞不清楚是因为我没有想到拆分之间的依赖关系，陷入了暴力枚举+拆分成相近的数的思考困境
//应该直接想一个数被拆分一次后可以在此基础上再拆分，如此一想就形成了依赖关系
//dp[i]：数字i被拆分后得到的最大乘积
//状态转移：i被拆分为两个数和两个数以上都可以，拆分为两个数的乘积:j*(i-j)  拆分为两个数以上的乘积:j*dp[i-j]
//不断枚举j的值从1到i-1即可把所有拆分情况都考虑进去，i依赖于i-j
//状态转移方程：不断枚举j的值从1到i-1，dp[i]=max(dp[i],j*(i-j),j*dp[i-j])
//因为需要不断比较最大值和记录最大值到dp[i]，所以要把dp[i]纳入max比较
//临界条件为dp[2]=1
func integerBreak(n int) int {
	dp := make([]int, n+1)
	dp[2] = 1
	for i := 3; i < n+1; i++ {
		for j := 1; j <= i/2; j++ { //拆成m个近似数组的子数 相乘才是最大的，至少拆成两个数，j最差取一半
			dp[i] = max(dp[i], j*(i-j), j*dp[i-j])
		}
	}
	return dp[n]
}

背包问题

0-1背包

给定n个物品，第i个物品的重量为wgt[i-1]，价值为val[i-1]，和一个容量为cap的背包，每个物品只能选择一次，问在不超过背包容量下能放入物品的最大价值。

  1. 首先定义状态，建立dp表
1
2
dp[i][c]为考虑将前i件物品装进限重为c的背包可以获得的最大价值, 0<=i<=n, 0<=c<=cap
dp表大小为(n+1)*(cap+1)
  1. 定义子问题、推导状态转移方程
1
2
3
4
5
6
子问题：[i][c]情况下(即考虑前i件物品、限重为c）背包能放入物品的最大价值
[i][c]状态如何来：因为是考虑第i件物品是否放入，且只能选一次，所以i是由i-1转移而来的
				不放入i，那就和前i-1件情况相同，dp[i][c] = dp[i-1][c];
				放入i，dp[i][c] = dp[i-1][c-wgt[i-1]] + val[i-1]
	为什么是c-wgt[i-1]？既然要放入就要转移到没放入之前，限重自然要更新到没放入之前。
状态转移方程：dp[i][c] = max(dp[i-1][c], dp[i-1][c-wgt[i-1]]+val[i-1])

小小的细节，数组不能越界

1
c < wgt[i-1]时不放入物品，dp[i][c] = dp[i-1][c]
  1. 确定边界条件、状态转移顺序
1
2
3
边界条件：不放入物品、背包容量为0： dp[0][c]=0 , dp[i][0]=0
状态转移顺序：不压缩空间的话怎么都行。一般来说按照默认升序，i从小到大，c从小到大
	i层空间压缩后，c使用逆序遍历：可能会覆盖先前的数据（根据状态转移方程，dp[i][c]是需要使用i-1层的数据。如果正序遍历，i-1层的一些数据会被i层覆盖）
  1. 空间优化
1
采用一维滚动数组来替代二维数组，根据dp表的记录，dp[c]=max(dp[c],dp[c-wgt[i-1]]+cal[i-1])，dp[c]来源于上一轮的dp[c]和上一轮的dp[c-wgt[i-1]]，因此遍历要保证不覆盖上一轮结果，所以容量的遍历要从后往前，外循环为物品，内循环为容量

实际代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func kbapsackDP(wgt, val []int, cap int) int {
	n := len(wgt)
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, cap+1)
	}
	for i := 1; i <= n; i++ {
		for c := 1; c <= cap; c++ {
			if c < wgt[i-1] {//装不下当前物品，动上个背包同等容量转移
				dp[i][c] = dp[i-1][c]
			} else {//有机会装下当前物品，从上一行的两个状态转移
				dp[i][c] = max(dp[i-1][c], dp[i-1][c-wgt[i-1]]+val[i-1])
			}
		}
	}
	return dp[n][cap]
}

空间优化代码

1
2
3
4
5
6
7
8
9
10
11
//压缩空间，把i那一维度压缩掉
func kbapsackDP1(wgt, val []int, cap int) int {
	n := len(wgt)
	dp := make([]int, cap+1)
	for i := 1; i <= n; i++ {
		for c := cap; c >= wgt[i-1]; c-- {//c < wgt[i-1]时维持现状不装入该物品，dp[c] 不用改变
			dp[c] = max(dp[c], dp[c-wgt[i-1]]+val[i-1])
		}
	}
	return dp[cap]
}

分割等和数组

问题可以转化为0-1背包，把要素对齐一下。

  • 背包容量为sum/2
  • 放入的物品的重量和价值都是元素的数值
  • 背包刚好装满说明找到了sum/2的子集
  • 每个物品不能重复放入

思路

  1. 确定dp表

    dp[j]表示背包容量为j能装的最大重量（价值），当dp[target]==target时背包装满了

  2. 推导状态转移方程

    01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。

    所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  3. 确定临界条件

    dp[0]=0。如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

  4. 确定状态转移顺序

    使用一维dp数组，物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历！

  5. 其余处理

    要先遍历求取数组总和sum

    sum%2==0才能分割成两个等和子集

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
func canPartition(nums []int) bool {
    //求sum
    sum:=0
    for _,v:=range nums {
        sum+=v
    }
    //验证sum至少是2的倍数
    if sum%2==1 {
        return false
    }
    //0-1背包
    target:=sum/2
    dp:=make([]int,target+1)
    for i:=0;i<len(nums);i++{//物品
        for j:=target;j>=nums[i];j--{//容量
            dp[j]=max(dp[j],dp[j-nums[i]]+nums[i])
        }
    }
    
    //填满了就刚刚好可分割
    if dp[target]==target{return true}
    return false
}

最后一块石头的重量2

不要陷入纠结过程的漩涡中，模拟太难了

还是和分割等和子集类似，将石头分成尽量一样大的两部分，这样对撞后剩下的石头最小

物品重量为stones[i]，价值也为stones[i]

背包最大容量为sum/2

思路

  1. 确定dp表

    dp[j]表示容量为j的背包可以装入的石头的总和，dp表的大小为target+1，target是sum/2，sum是所有石头重量总和

  2. 推导状态转移方程

    装入第i块石头和不装入第i块石头两种状态转移而来，要装入第i块石头，要考虑当前能装得下

    dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])

  3. 确定临界条件

    初始化dp[j]=0，就能保证dp[j]=max(dp[j],dp[j-stones[i]]+stones[i])的dp[j]正常计算

  4. 确定状态转移顺序

    石头从前到后，背包容量从后往前

  5. 最后返回结果是sum-dp[target]-dp[target]。target一定是sum一半向下取整，dp[target]<=target，因此sum-dp[target]>=sum/2,sum-dp[target]表示分出来的另一堆石头，和dp[target]相减得到对撞后剩余结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func lastStoneWeightII(stones []int) int {
	sum := 0
	for _, v := range stones {
		sum += v
	}
	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])
		}
	}
	return sum - dp[target] - dp[target]
}

目标和

思路

问题转化，把加和减的数分别看成集合，left-right=target，所有数的总和为sum，left+right=sum故left=(sum+target)/2，只要找出能构成left的组合的数量即可。

根据题意，left是正数，而且这里整形除以2必然关心取整问题，所以sum+target是奇数或负数时无解。

因此采用动态规划就转化为了背包容量为left，装满有多少种方法。注意是方法数，这道题会出现元素是0，特别恶心

回溯

动态规划

  1. 确定dp表

    dp[i][j]表示使用下标为0到i的nums[i]能够凑满容量j的背包的方法数，数组大小为len(nums)*(left+1)

  2. 推导状态转移方程

    j<nums[i]时装满背包dp[i][j]=dp[i-1][j]

    j>=nums[i]时装满背包，可以用nums[i]，也可以不用，dp[i][j]=dp[i-1][j-nums[i]]+dp[i-1][j]

  3. 确定临界条件

    nums[0]<left时dp[0][nums[0]]=1

    若有nums[i]=0，假设n为统计到nuns[i]时0的数量，dp[i][0]=2^n

    *题目允许0的出现，因此对于0放入背包非常灵活，即使是背包容量为0，可以放也可以不放0，它可以叠加到所有的装入情况中。就有出现物品重量为0时，有2的n次方中选择，n为这个物品及之前重量为0的物品的次数。

  4. 确定状态转移顺序

    i从1开始，j从1开始

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func findTargetSumWays(nums []int, target int) int {
	//统计总和
	sum := 0
	for _, v := range nums {
		sum += v
	}
	//无解
	if sum+target < 0 || (sum+target)%2 == 1 {
		return 0
	}
	//dp
	left := (sum + target) / 2
	dp := make([][]int, len(nums))
	for i, _ := range dp {
		dp[i] = make([]int, left+1)
	}
	//初始化
	if nums[0] <= left {
		dp[0][nums[0]] = 1
	}
	//对0特殊照顾
	zeroNumber := 0
	for i := 0; i < len(nums); i++ {
		if nums[i] == 0 {
			zeroNumber++
		}
		dp[i][0] = int(math.Pow(2, float64(zeroNumber)))
	}
	//状态转移
	for i := 1; i < len(dp); i++ {
		for j := 1; j <= left; j++ {
			if j < nums[i] {
				dp[i][j] = dp[i-1][j]
			} else {
				dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]
			}
		}
	}
	
	return dp[len(nums)-1][left]
}

一和零

这道题是0-1背包的变种，有两个背包，分别是装0和装1的背包，物品是字符串数组中的元素，我们要确定的是把字符串数组中的元素放入到背包中最多能放多少个。字符串元素–物品，m和n对应两个背包的容量。

实际上最简单的考量是建立dp[i][j][k]，物品一维，背包两维，不断考虑一个又一个物品是否放入背包。

思路

  1. 确定dp表

    dp[i][j]表示在i个0和j个1的情况下，考虑字符串数组中的所有元素，字符串数组的最大子集的大小（该子集中 最多 有i个0和j个1），dp表的大小为(m+1)*(n+1)。其实这里已经压缩了一维空间了，但是计算的时候不要忘记了背包问题的计算顺序是一件件地考虑物品能否放入。

  2. 推导状态转移方程

    遍历字符串数组，考虑是否将该元素放入到背包中

    对于字符串数组的当前元素，可以考虑将其放入背包，也可以不放入，这取决于当前元素有zeors个0和ones个1

    若放入背包，则考虑容量足够，方法数加1，dp[i][j]=dp[i-zeros][j-ones]+1

    若不放入背包，则dp[i][j]与先前一个字符串数组元素保持一致

    方法数应该取最大

    故dp[i][j]=max(dp[i][j],dp[i-zeros][j-ones]+1)

  3. 确定临界条件

    初始情况下没有字符串数组的元素纳入考虑，没有元素，dp表初始化为0

  4. 确定状态转移顺序

    0-1背包空间压缩后，需要从后往前遍历背包容量，所以i和j都要从后往前遍历，以确保在计算时不会覆盖所需的上一层的计算结果

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
func findMaxForm(strs []string, m int, n int) int {
	//建立dp表
	dp := make([][]int, m+1)
	for i, _ := range dp {
		dp[i] = make([]int, n+1)
	}
	//状态转移
	for _, s := range strs {
		zeros := strings.Count(s, "0")
		ones := len(s) - zeros
		for i := m; i >= zeros; i-- {
			for j := n; j >= ones; j-- {
				dp[i][j] = max(dp[i][j], dp[i-zeros][j-ones]+1)
			}
		}
	}
	return dp[m][n]
}

完全背包

给定n个物品，第i个物品的重量为wgt[i-1]，价值为val[i-1]，和一个容量为cap的背包，每个物品可以重复选取，问在不超过背包容量下能放入物品的最大价值。

分析其实和0-1背包类似，只需要小小地修改一下状态转移方程和条件。

  1. 首先定义状态，建立dp表
1
2
dp[i][c]为考虑将前i种物品装进限重为c的背包可以获得的最大价值, 0<=i<=n, 0<=c<=cap
dp表大小为(n+1)*(cap+1)
  1. 定义子问题、推导状态转移方程
1
2
3
4
5
6
子问题：[i][c]情况下(即考虑前i种物品、限重为c）背包能放入物品的最大价值
[i][c]状态如何来：不放入i，和i-1情况相同，dp[i][c] = dp[i-1][c];
				放入i，dp[i][c] = dp[i][c-wgt[i-1]] + val[i-1]
	为什么是i呢？这里考虑重复放，那么放置i时就要去看看前面已经放了i的。
	（存储子问题确保了不会有条件漏掉)
状态转移方程：dp[i][c] = max(dp[i-1][c], dp[i][c-wgt[i-1]]+val[i-1])

小小的细节，数组不能越界

1
c < wgt[i-1]时不放入物品，dp[i][c] = dp[i-1][c]
  1. 确定边界条件、状态转移顺序
1
2
3
边界条件：不放入物品、背包容量为0： dp[0][c]=0 , dp[i][0]=0
状态转移顺序：不压缩空间的话怎么都行。一般来说按照默认升序，i从小到大，c从小到大
	i层空间压缩后，c使用正序遍历：dp[i][c] = dp[i][c-wgt[i-1]] + val[i-1]使用先前计算过的数据，需要覆盖

  1. 空间优化

    可以使用一维滚动数组来优化空间，因为允许重复选择一个物品，所以c的遍历要从前往后来覆盖dp

实际代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func kbapsackDP(wgt, val []int, cap int) int {
	n := len(wgt)
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, cap+1)
	}
	for i := 1; i <= n; i++ {
		for c := 1; c <= cap; c++ {
			if c < wgt[i-1] {
				dp[i][c] = dp[i-1][c]
			} else {
				dp[i][c] = max(dp[i-1][c], dp[i][c-wgt[i-1]]+val[i-1])
			}
		}
	}
	return dp[n][cap]
}

空间优化代码

1
2
3
4
5
6
7
8
9
10
11
12
func kbapsackDP(wgt, val []int, cap int) int {
	n := len(wgt)
	dp := make([]int, cap+1)
	for i := 1; i <= n; i++ {
		for c := 1; c <= cap; c++ {
			if c >= wgt[i-1] {
				dp[c] = max(dp[c], dp[c-wgt[i-1]]+val[i-1])
			}
		}
	}
	return dp[cap]
}

硬币问题

给定n种硬币，第i种硬币的面值为coin[i-1],目标金额为amt，每种硬币可以重复选取，问能够凑出目标金额的最少硬币个数，如果无法凑出目标金额则返回-1

本题是要求最少硬币数量，硬币是组合数还是排列数都无所谓！所以两个for循环先后顺序怎样都可以！

  1. 首先定义状态，建立dp表
1
2
[i][a]表示使用i种硬币能够凑出金额amt，dp[i][a]表示使用的最少硬币个数
dp表大小为(n+1)*(amt+1)

  1. 定义子问题、推导状态转移方程

    目标变成了最少硬币个数，限制要刚刚好凑到金额，其他转移条件和多重背包类似

1
2
3
4
子问题：[i][a]情况下，使用前i种硬币能凑出amt的最少硬币个数
[i][a]状态如何来：不使用i硬币，dp[i][a]=dp[i-1][a]
				使用i硬币，dp[i][a]=dp[i][a-coins[i-1]]+1
状态转移方程：dp[i][a]=min(dp[i-1][a],dp[i][a-coins[i-1]]+1)

​ 小小的细节，数组不能越界

1
a < coins[i-1]时不放入物品，dp[i][a] = dp[i-1][a]
  1. 确定边界条件、状态转移顺序
1
2
3
使用0种硬币凑amt金额  dp[0][a]=inf
使用i种硬币凑0金额	  dp[i][0]=0	
空间压缩使用正序遍历amt

实际代码

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 coinChangeDP(coins []int, amt int) int {
	n := len(coins)
	//建立dp表
	dp := make([][]int, n+1)
	for i := 0; i < n+1; i++ {
		dp[i] = make([]int, amt+1)
	}
	//临界条件设置
	for a := 0; a <= amt; a++ {
		dp[0][a] = math.MaxInt
	}
	//状态转移
	for i := 1; i <= n; i++ {
		for a := 1; a <= amt; a++ {
			if a < coins[i-1] {
				dp[i][a] = dp[i-1][a]
			} else {
				dp[i][a] = min(dp[i-1][a], dp[i][a-coins[i-1]]+1)
			}
		}
	}
	//结果返回
	if dp[n][amt] < math.MaxInt {
		return dp[n][amt]
	} else {
		return -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 coinChangeDP1(coins []int, amt int) int {
	n := len(coins)
	//建立dp表
	dp := make([]int, amt+1)
	//临界条件设置
	for a := 1; a <= amt; a++ {
		dp[a] = math.MaxInt
	}
	//状态转移
	for i := 1; i <= n; i++ {
		for a := 1; a <= amt; a++ {
			if a >= coins[i-1] {
				dp[a] = min(dp[a], dp[a-coins[i-1]]+1)
			}
		}
	}
	//结果返回
	if dp[amt] < math.MaxInt {
		return dp[amt]
	} else {
		return -1
	}
}

给定n种硬币，第i种硬币的面值为coin[i-1],目标金额为amt，每种硬币可以重复选取，问在凑出目标金额的硬币组合数量

  1. 首先定义状态，建立dp表
1
2
[i][a]表示使用i种硬币能够凑出金额amt，dp[i][a]表示硬币组合数量
dp表大小为(n+1)*(amt+1)
  1. 定义子问题、推导状态转移方程
1
2
3
子问题：[i][a]情况下，使用前i种硬币能凑出amt的硬币组合数量
[i][a]状态如何来：当前状态组合数量等于不选当前硬币和选当前硬币两种决策的组合数量之和，
状态转移方程为`dp[i][a]=dp[i-1][a]+dp[i][a-coins[i-1]]`
  1. 确定边界条件、状态转移顺序
1
2
3
使用0种硬币凑amt金额  dp[0][a]=0
使用i种硬币凑0金额	  dp[i][0]=1	
空间压缩使用正序遍历amt

求取组合数，外循环硬币，内循环金额；若反过来则求取的是排列数。原因在于外循环是金额时，对同一金额，不断枚举各种硬币的情况，硬币之间的出现产生了顺序，并且得到了记录。

单词拆分

回溯

动态规划

思路

子序列问题

最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

  • 输入：nums = [10,9,2,5,3,7,101,18]
  • 输出：4
  • 解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

  • 输入：nums = [0,1,0,3,2,3]
  • 输出：4

示例 3：

  • 输入：nums = [7,7,7,7,7,7,7]
  • 输出：1

提示：

  • 1 <= nums.length <= 2500
  • -10^4 <= nums[i] <= 104

特点

首先明确子序列定义——”子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序”。也就是说子序列可以是不连续的，但又有顺序关系。这一点对后续搜索形成指导意义。

解决这类序列问题，很关键的是在dp状态的定义上下功夫，如果确认dp[i]为到i为止的最长严格递增子序列的长度，那么就很难进行状态的转移，对于一个新的子序列，很难确定计算如何转移。这个转移信息很难被记录，因为dp的定义不允许记录新的子序列的计算信息。那么就需要改变dp的定义，使得能够记录新的子序列，再多使用一个变量记录最长严格递增子序列的长度。

设置dp[i]表示以i结尾的子序列的最长严格递增子序列的长度，这样便于开启新的子序列时计算的转移。

思路

  1. 确定状态，确定dp表

    dp[i]表示以i结尾的子序列的最长严格递增子序列的长度，长度为n

  2. 定义子问题，推导递推公式

    因为子序列可以不连续，只要nums[i]够大，nums[i]可以加在任何一个前面已经求取过的子序列，所以dp[i]可能由j从0取到i-1的所有dp[j]转移而来。即位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值

    1
    2
    3
    if nums[i] > nums[j] {
    	dp[i] = max(dp[i], dp[j]+1)
    }

  3. 确定边界条件

    dp[i] = 1，每个数自己就是一个最长递增子序列

  4. 确定转移顺序

    从左往右遍历，i从0到n-1，j从0到i-1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func lengthOfLIS(nums []int) int {
    dp := make([]int, len(nums))
    maxAns := 1
    for i := 0; i < len(nums); i++ {
        dp[i] = 1
        for j := 0; j < i ;j ++ {
            if nums[i] > nums[j] {
	            dp[i] = max(dp[i], dp[j]+1)
            } 
        }
        maxAns = max(maxAns, dp[i])
    }
    return maxAns
}

最长连续递增子序列

与最长递增子序列的差别在于要求连续了，连续了就不用再来个for内循环去检查了，直接从dp[i-1]就能转移。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// dp[i] 表示以 i 结尾的子序列的最长连续递增序列长度
// if nums[i] > nums[i-1] { dp[i]=dp[i-1]+1 }
func findLengthOfLCIS(nums []int) int {
    dp := 1
    maxAns := 1
    for i := 1; i < len(nums); i++{
        if nums[i] > nums[i-1] { 
            dp = dp + 1 
        }else {
            dp = 1
        }
        maxAns = max(maxAns, dp)
    }
    return maxAns
}

最长重复子数组

给两个整数数组 A 和 B ，返回两个数组中公共的、长度最长的子数组的长度。

示例：

输入：

  • A: [1,2,3,2,1]
  • B: [3,2,1,4,7]
  • 输出：3
  • 解释：长度最长的公共子数组是 [3, 2, 1] 。

提示：

  • 1 <= len(A), len(B) <= 1000
  • 0 <= A[i], B[i] < 100

思路

因为强调连续性，dp状态转移时会因为非连续而与先前状态断开传递关系，所以设置dp表时注意以i/j结尾这个条件。

dp[i][j]表示nums1数组中以i结尾的子数组和nuns2数组中以j结尾的子数组，两者公共的、长度最长的子数组的长度

dp[i][j] = dp[i-1][j-1] + 1，比较的时候i和j至少从1开始，所以第一行和第一列需要提前初始化号，在初始化的时候比较麻烦

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
// dp[i][j]表示nums1数组中以i结尾的子数组和nuns2数组中以j结尾的子数组，两者公共的、长度最长的子数组的长度
// if  nums1[i] == nums2[j] { dp[i][j] = dp[i-1][j-1] + 1 }
// nums1[i] != nums2[j] { dp[i][j] = 0 }
func findLength(nums1 []int, nums2 []int) int {
    res := 0
    // dp数组
    dp := make([][]int, len(nums1))
    for i , _ := range dp {
        dp[i] = make([]int, len(nums2))
    } 
    // 初始化要解决第一行和第一列
    for i := 0; i < len(nums1); i++ {
        if nums1[i] == nums2[0] {
            dp[i][0] = 1
            res = 1
        }
    }    
    for i := 0; i < len(nums2); i++ {
        if nums2[i] == nums1[0] {
            dp[0][i] = 1
            res = 1 
        }
    } 
 
    for i := 1; i < len(nums1); i++ {
        for j := 1; j < len(nums2); j++{
            if nums1[i] == nums2[j] {
                dp[i][j] = dp[i-1][j-1] + 1
            }
            res = max(res, dp[i][j])
        }
    }
    return res
}

避免复杂初始化，那就把第一行第一列给空出来，将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
// dp[i][j]表示nums1数组中以i-1结尾的子数组和nuns2数组中以j-1结尾的子数组，两者公共的、长度最长的子数组的长度
// if  nums1[i-1] == nums2[j-1] { dp[i][j] = dp[i-1][j-1] + 1 }
// nums1[i-1] != nums2[j-1] { dp[i][j] = 0 }
// 改变dp定义，使得初始条件的处理更加简单，即dp[i][j]表示 i-1、j-1结尾的子数组，两者公共的、长度最长的子数组的长度，这样初始化只要设置dp[0][0] = 0 ，不用初始化一行一列

func findLength(nums1 []int, nums2 []int) int {
    res := 0
    // dp数组
    dp := make([][]int, len(nums1)+1)
    for i , _ := range dp {
        dp[i] = make([]int, len(nums2)+1)
    } 
    // 首行和首列无意义，初始化dp[0][0] = 0
    for i := 1; i < len(nums1)+1; i++ {
        for j := 1; j < len(nums2)+1; 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
}

空间优化，采用滚动数组，且我们发现dp[i][j] 只依赖于dp[i-1][j-1]，为了避免覆盖，内循环倒序，同时注意覆盖

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func findLength(nums1 []int, nums2 []int) int {
    res := 0
    // dp数组
    dp := make([]int, len(nums1)+1)
    // 首行和首列无意义，初始化dp[0] = 0
    for i := 1; i < len(nums1)+1; i++ {
        for j := len(nums2); j > 0; j--{
            if nums1[i-1] == nums2[j-1] {
                dp[j] = dp[j-1] + 1
            }else {//注意不相等要手动赋值0，见上述dp推导
                dp[j] = 0
            }
            if dp[j] > res {
                res = dp[j]
            }
        }
    }
    return res
}

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串：它是由原字符串在不改变字符的相对顺序的情况下删除某些字符（也可以不删除任何字符）后组成的新字符串。

例如，”ace” 是 “abcde” 的子序列，但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列，则返回 0。

示例 1:

  • 输入：text1 = “abcde”, text2 = “ace”
  • 输出：3
  • 解释：最长公共子序列是 “ace”，它的长度为 3。

示例 2:

  • 输入：text1 = “abc”, text2 = “abc”
  • 输出：3
  • 解释：最长公共子序列是 “abc”，它的长度为 3。

示例 3:

  • 输入：text1 = “abc”, text2 = “def”
  • 输出：0
  • 解释：两个字符串没有公共子序列，返回 0。

提示:

  • 1 <= text1.length <= 1000
  • 1 <= text2.length <= 1000 输入的字符串只含有小写英文字符。

思路

本题对连续性以及元素之间的关系都没有先前连续、单调要求那么高，只要求最长公共子序列，只要先前匹配上的字符，后续都能用得到，因此可以直接定义状态dp[i][j] 表示text1前i-1个字符、text2前j-1个字符，两者共同子序列的长度。

状态转移上，两字符相等，纳入最长公共子序列；两字符不相等，则分别考虑text上一位的重叠情况——看看text1[0, i - 2]与text2[0, j - 1]的最长公共子序列 和 text1[0, i - 1]与text2[0, j - 2]的最长公共子序列，取最大的。（这位不匹配，那上一位匹配吗

同样采取优化，i-1和j-1来减少初始化开销

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 可以正常地按照答案即状态来定义
// text1[i-1] == text2[j-1] , dp[i][j] = dp[i-1][j-1] + 1
// != , 从两个前序字符串转移而来，求最大
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)] 
 }

不相交的线

线不能相交，一开始去想怎么判断线不相交，然后就做不出来了。要学会转化问题，连成线不相交其实都是保证一个相对顺序，直接将不能相交转化为最长公共子序列，确保了顺序就不会出现连线相交。代码几乎一模一样。

最大子序和

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

思路

这道题的思路不难想，贪心也可以，动态规划特别直观，抓住连续以及最大和两个条件，直接给出套路.答案要另外使用个变量res来记录。

  1. 确定状态，确定dp表

    dp[i]表示以i结尾的连续子数组的最大和，长度为n

  2. 定义子问题，推导递推公式

    dp[i]只能从dp[i-1]和nums[i]两种情况进行转移： dp[i]= max(dp[i-1] + nums[i], nums[i] )

    • dp[i-1] + nums[i]，即nums[i]加入当前子数组
    • nums[i]，即nums[i]作为新的子数组开头开始计算

  3. 确定边界条件

    dp[0] = nums[0]

  4. 确定转移顺序

    从左往右遍历，i从0到n-1

  5. 空间压缩

    i只依赖于i-1，且依赖于左，使用一个滚动变量来替代就行

1
2
3
4
5
6
7
8
9
func maxSubArray(nums []int) int {
    dp := nums[0]
    res := nums[0]
    for i := 1; i < len(nums); i++{
        dp = max(dp + nums[i], nums[i])
        res = max(res, dp)
    }
    return res
}

判断子序列

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，”ace”是”abcde”的一个子序列，而”aec”不是）。

示例 1：

  • 输入：s = “abc”, t = “ahbgdc”
  • 输出：true

示例 2：

  • 输入：s = “axc”, t = “ahbgdc”
  • 输出：false

提示：

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4

两个字符串都只由小写字符组成

本题可以算是编辑距离的简化入门题，还是有点难想，涉及到删除的字符概念，即考虑是否使用当前字符来组成子序列。

动态规划

#LeetCode
动态规划总结
http://willxu0313.github.io/2025/01/25/算法题/动态规划/
作者
Will
发布于
2025年1月25日
许可协议