算法笔记（四）从暴力递归到动态规划

---

layout: post
title: 算法笔记（四）从暴力递归到动态规划、背包问题
description: 算法笔记（四）从暴力递归到动态规划、背包问题
tag: 算法

---

机器人路径数

【题目】给定一个数N代表从1~N有N个位置，在起始位置1处只能往后走，结尾位置N处只能往前走，再给定机器人初始位置S和需要前往的位置E，如果规定必须在K步从S到达E，有多少种路径选择？

暴力递归

暴力递归的方法就是每次来到某个位置，尝试所有可以走的路，直至剩余步数为0.

int forceRecurRobotPath(int N, int E, int rest , int cur) {
	// 当恰好走，返回当前位置是否为E，是则找到一条路
	if (rest == 0) {
		return cur == E ? 1 : 0;
	}
	// 当来到1处只能往后走
	if (cur == 1) {
		return forceRecurRobotPath(N, E, rest - 1, cur + 1);
	}
	// 当来到N处只能往前走
	if (cur == N) {
		return forceRecurRobotPath(N, E, rest - 1, cur - 1);
	}
	// 中间位置既可以往前也可以往后
	return forceRecurRobotPath(N, E, rest - 1, cur + 1) + (N, E, rest - 1, cur - 1);
}

int robotPath1(int N, int E, int K, int S) {
	return forceRecurRobotPath(N, E, K, S);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

memo表记忆搜索

上边暴力递归只有两个可变参数rest和cur，
这样暴力递归会重复计算很多之前计算过的过程。那么一个改进的思路就是以空间换时间，记录下每个可变参数的组合的计算结果到表中，每次如果遇到表中已有组合即可直接调用，称为记忆化搜索版本递归

按照这种思路，写出带记忆搜索的递归：
构建一个二维数组memo表，将可变参数rest和cur的所有组合找到的可行路径数都记录下：
rest的取值范围为[0, K]，cur的取值范围为[1,N]
vector> memo(N + 1, vector(K + 1, -1));

// 带备忘录的递归
int memoRecurRobotPath(int N, int E, int rest, int cur, vector<vector<int>> memo) {
	if (memo[rest][cur] != -1) {
		return memo[rest][cur];
	}
	// 当恰好走完，返回当前位置是否为E，是则找到一条路
	if (rest == 0) {
		memo[rest][cur] = cur == E ? 1 : 0;
	}
	// 当来到1处只能往后走
	else if (cur == 1) {
		memo[rest][cur] = memoRecurRobotPath(N, E, rest - 1, cur + 1, memo);
	}
	// 当来到N处只能往前走
	else if (cur == N) {
		memo[rest][cur] = memoRecurRobotPath(N, E, rest - 1, cur - 1, memo);
	}
	else
	{
		// 中间位置既可以往前也可以往后
		memo[rest][cur] = memoRecurRobotPath(N, E, rest - 1, cur + 1, memo) + memoRecurRobotPath(N, E, rest - 1, cur - 1, memo);
	}
	return memo[rest][cur];
}
int robotPath2(int N, int E, int K, int S) {
	vector<vector<int>> memo(N + 1, vector<int>(K + 1, -1));
	return memoRecurRobotPath(N, E, K, S, memo);
}
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

动态规划

如果memo表结构数据之间有严格的依赖关系，那么可以将他改为动态规划的形式。
如下图，从递归过程上看，首先rest为0时，只有cur = 4（E），位置找到一种路径，红色框是出口位置。当cur来到1，它只能往后走，路径数依赖于f(rest - 1, cur + 1)，即它在memo表中右上方的结果，cur来到N，只能往前走，路径数依赖于f（rest-1，cur-1），即它在memo表中左上方的结果，而当cur在中间位置时，它依赖于f（rest-1，cur-1）+ f（rest-1，cur+1），左上+右上。由此，表中所有数据其实都可以由已经解计算出来，这是一种严格表结构。动态规划的过程就是，直接根据严格表的依赖关系，从表中已有解，一步一步得到全部的解，而所求必在表中。

动态规划版本：

int dpRobotPath(int N, int E, int K, int S) {
	vector<vector<int>> memo(K + 1, vector<int>(N + 1, -1));
	// rest = 0(when row = 0:) 先全赋值0, i = 0位置都-1，弃用
	for (int i = 1; i < N + 1; i++) {
		memo[0][i] = 0;
	}
	// 再将出口即终点处赋值为1
	memo[0][E] = 1;
	for (int rest = 1; rest <= K; rest++) {
		for (int cur = 1; cur <= N; cur++) {
			if (cur == 1) {
				memo[rest][cur] = memo[rest - 1][2];
			}
			else if(cur == N) {
				memo[rest][cur] = memo[rest - 1][N - 1];
			}
			else {
				memo[rest][cur] = memo[rest - 1][cur - 1] + memo[rest - 1][cur + 1];
			}
		}
	}
	return memo[K][S];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

组成目标最少需要几枚硬币

【题目】给定正数数组，每个值代表一个硬币的币值，给定目标值target，问最少需要几枚硬币可以组成target。

暴力递归

每个硬币选或不选两种可能，这就可以列出所有的硬币的选择组合，将所有可以达成target的组合进行对比，选取硬币最少的组合。

// 当前来到数组到index位置，前面已经选择完毕，目标还剩余rest，index位置硬币选与不选两种可能，返回满足rest需要的硬币数
// 初始时，rest = target， index为0，两个可变参数，arr为固定参数
int coinForceRecur(vector<int>& arr, int index, int rest) {
	// 若rest < 0，已经超出目标，无效解-1
	if (rest < 0) {
		return -1;
	}
	// 恰好rest = 0，满足目标，不再需要硬币
	if (rest == 0) {
		return 0;
	}
	// 遍历到数组结尾了，且rest > 0，已经没有硬币了，无效解 
	if (index == arr.size()) {
		return -1;
	}
	// rest > 0，且当前也有硬币，选(p1)与不选(p2)两种情况
	int p1 = coinForceRecur(arr, index + 1, rest);
	// p2的后续需要的硬币数
	int p2Next = coinForceRecur(arr, index + 1, rest - arr[index]);
	// 如果p1和p2后续都只能得无效解，直接返回-1
	if (p1 == -1 && p2Next == -1) {
		return -1;
	}
	// 否则如果p1得到无效解，那么返回p2的可能，该硬币选择故硬币数+1,再加p2的后续
	else if (p1 == -1) {
		return p2Next + 1;
	}
	// 否则两个都是有效解，返回硬币数较少者
	else {
		return min(p1, p2Next + 1);
	}
}

int minCoin1(vector<int> arr, int target) {
	return coinForceRecur(arr, 0, target);
}
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

memo

固定参数arr
可变参数index，范围[0，arr.size()]
可变参数rest，范围[0，target]

构建memo(arr.size() + 1, target + 1)

// memo
int coinMemoRecur(vector<int>& arr, int index, int rest, vector<vector<int>> &memo) {
	// 若rest < 0，已经超出目标，无效解-1
	if (rest < 0) {
		return -1;
	}
	if (memo[index][rest] != -2) {
		return memo[index][rest];
	}
	// 恰好rest = 0，满足目标，不再需要硬币
	if (rest == 0) {
		memo[index][rest] = 0;
	}
	// 遍历到数组结尾了，且rest > 0，已经没有硬币了，无效解 
	else if (index == arr.size()) {
		memo[index][rest] = -1;
	}
	// rest > 0，且当前也有硬币，选(p1)与不选(p2)两种情况
	else
	{
		int p1 = coinMemoRecur(arr, index + 1, rest, memo);
		// p2的后续需要的硬币数
		int p2Next = coinMemoRecur(arr, index + 1, rest - arr[index], memo);
		// 如果p1和p2后续都只能得无效解，直接返回-1
		if (p1 == -1 && p2Next == -1) {
			memo[index][rest] = -1;
		}
		// 否则如果p1得到无效解，那么返回p2的可能，该硬币选择故硬币数+1,再加p2的后续
		else if (p1 == -1) {
			memo[index][rest] = p2Next + 1;
		}
		// 否则两个都是有效解，返回硬币数较少者
		else {
			memo[index][rest] = min(p1, p2Next + 1);
		}
	}
	return memo[index][rest];
}

int minCoin2(vector<int> arr, int target) {
	vector<vector<int>> memo(arr.size() + 1, vector<int>(target + 1, -2));

	return coinMemoRecur(arr, 0, target, memo);
}
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

DP

• rest为0，对于每个index需要的coin数都是0
• index = arr.length()，对于每个rest都是 -1
• 中间每个元素都取决于它左下方值

int minCoinDP(vector<int> arr, int target) {
	vector<vector<int>> memo(arr.size() + 1, vector<int>(target + 1, -2));
	// rest为0，对于每个index需要的coin数都是0
	for (int row = 0; row < arr.size() + 1; row++) {
		memo[row][0] = 0;
	}
	// index = arr.length()，对于每个rest都是 -1
	for (int col = 1; col < target + 1; col++) {
		memo[arr.size()][col] = -1;
	}
	// 对于表中间的元素，每个元素的求取都依赖于表中左下方的值，
	// 故遍历顺序是从下往上，从左至右
	for (int index = arr.size() - 1; index >= 0; index++) {
		for (int rest = 1; rest <= target; rest++) {
		// rest > 0，且当前也有硬币，选(p1)与不选(p2)两种情况
			int p1 = memo[index + 1][rest];
			// p2的后续需要的硬币数
			int p2Next = -1;
			if (rest - arr[index] >= 0) {
				p2Next = memo[index + 1][rest - arr[index]];
			}
			// 如果p1和p2后续都只能得无效解，直接返回-1
			if (p1 == -1 && p2Next == -1) {
				memo[index][rest] = -1;
			}
			// 否则如果p1得到无效解，那么返回p2的可能，该硬币选择故硬币数+1,再加p2的后续
			else if (p1 == -1) {
				memo[index][rest] = p2Next + 1;
			}
			// 否则两个都是有效解，返回硬币数较少者
			else {
				memo[index][rest] = min(p1, p2Next + 1);
			}
		}
	}
	// 最终返回的值
	return memo[0][target];
}
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

小结

• 暴力递归是方法尝试的过程，总结所有可能的情况。
• memo表是根据可变参数的范围，将可变参数组合带来的解法记录下来，避免了暴力递归中的重复计算。
• DP方法是从memo表中总结而来，有严格表结构依赖关系的memo表都可以演变为DP解法，且有固定的转变步骤：
  • 确定可变参数范围，构memo表（维度，大小） 构建memo表
  • 在表中标出最终结果的位置终点位置
  • 将base case（可以直接得到结果）填入memo表。初始化memo表边界值
  • 整理memo表中的数据依赖关系（从递归过程来看），确定memo表中剩余元素的求解顺序与过程。由数据依赖关系确定memo表的遍历顺序与构造过程

俩聪明人玩牌DP版

暴力递归版：

/*
整型数组arr代表不同纸牌排成一线，两玩家A和B轮流取牌且只能取数组左右两头的牌
规定A先B后，谁拿的牌大谁获胜，返回获胜者的分数。A和B都是聪明人。
eg1：
arr = [1, 2, 100, 4]
A会先拿1以保证B拿不到100，最终，A得1 + 100， B得4 + 2
return 101
eg2：
arr = [1, 100, 2]
A得 2 + 1
B得 100
return 100
*/

//先手拿牌得分函数由f(arr, L, R)计算，后手由s(arr, L, R)计算。
//先手情况下，当牌只剩一张（L == R）return arr[L]
//否则决策是 arr[L] + s(arr, L + 1, R)或者 arr[R] + s(arr, L, R - 1)中的较大值
//
//后手函数s(arr, L, R)
//当L == R时，return 0；
//否则决策是
//f(arr, L + 1, R) 和f(arr, L, R - 1)中的较小值。
//因为是后手，所以别人一定在选择L和R时令自己的先手是最小的结果。

int redHand(vector<int>& arr, int L, int R);

// 黑方，后手函数
int blackHand(vector<int> &arr, int L, int R) {
	if (L == R) {
		return 0;
	}
	int Lscore = redHand(arr, L + 1, R);
	int Rscore = redHand(arr, L, R - 1);
	return min(Lscore, Rscore);
}

// 红方，先手函数
int redHand(vector<int>& arr, int L, int R) {
	if (L == R) {
		return arr[L];
	}
	int Lscore = L + blackHand(arr, L + 1, R);
	int Rscore = R + blackHand(arr, L, R - 1);
	return max(Lscore, Rscore);
}

int winnerScore(vector<int>& arr) {
	if (arr.size() < 1) {
		return 0;
	}
	int red = redHand(arr, 0, arr.size());
	int black = blackHand(arr, 0, arr.size());
	return  max(red, black);
}

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
49
50
51
52
53
54
55

DP版
固定参数arr
令N = arr.length()
可变参数就是范围的左边界L和右边界R
L∈[0~N-1]
右边界同理
L∈[0~N-1]
但同时需要保证L <= R
（范围圈定）
故memo表只取对角一半。
当L = R时，即对角线位置先手和后手的值都可直接得到（base case 初始化边界）

表中依赖关系，先手表某个位置的值依赖后手表对应位置（左边：（L，R-1）和下边：（L +1，R））取最大值，后手表依赖先手表中对应位置（左边：（L，R-1）和下边：（L +1，R））取最小值。

先手表次对角线由后手表对角线填，后手表同理，两张表交替求每条次对角线。

三维memo表DP问题：马踏棋盘

给定象棋棋盘，x∈[0,8]，y∈[0,9]
马初始停在(0,0)处，要想马走K步到达位置X（a，b），问路径有几种？

问题等价与从（a，b）出发走K步，到达（0,0）点有多少种路径数。
递归函数三个可变参数，当前位置坐标（x，y）以及剩余步数step。

暴力递归：

// 从x,y出发去往0，0位置，走step步，返回方法数
int horseRecur(int x, int y, int step) {
	// 如果当前位置越界，不可行解，返回0
	if (x < 0 || x > 8 || y <0 || y > 9) {
		return 0;
	}
	// 如果剩余步数为0，返回当前是否就是0,0位置
	if (step == 0) {
		return (x == 0 && y == 0) ? 1 : 0;
	}
	// 如果当前位置不越界，且还有剩余步数，递归马可能到达的8个位置
	return (horseRecur(x - 1, y - 2, step - 1) +
		horseRecur(x - 1, y + 2, step - 1) +
		horseRecur(x + 1, y - 2, step - 1) +
		horseRecur(x + 1, y - 2, step - 1) +
		horseRecur(x - 2, y - 1, step - 1) +
		horseRecur(x - 2, y + 1, step - 1) +
		horseRecur(x + 2, y - 1, step - 1) +
		horseRecur(x + 2, y + 1, step - 1));
}

int horseJump(int a, int b, int k) {
	return horseRecur(a, b, k);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

改动态规划：
范围圈定：
x∈[0,8]，y∈[0,9]
step∈[0,k]
终点标定：
从（0，0）到a，b改为等价问题从（a，b）到（0, 0），初始点在（a，b，k），终点为（0，0，0）。
边界值初始化
当step为0时，只有（0，0）为1，其余都是0。
memo表依赖关系
step，依赖step-1的8个可以走的点。
故假定构建三维memo表，step为高，从底层往上遍历。

// 动态规划版本
int horseDP(int x, int y, int step) {
	// 初始都为0
	vector<vector<vector<int> > > memo(step + 1, vector<vector<int> >(9, vector<int>(10, 0)));
	// 0层，(0,0)赋值1
	memo[0][0][0] = 1;
	// 自底层向上构建
	for (int h = 1; h <= step; h++) {
		for (int r = 0; r < 9; r++) {
			for (int c = 0; c < 10; c++) {
				memo[h][r][c] += getMemoValue(memo, h, r - 1, c + 2);
				memo[h][r][c] += getMemoValue(memo, h, r - 1, c - 2);
				memo[h][r][c] += getMemoValue(memo, h, r + 1, c + 2);
				memo[h][r][c] += getMemoValue(memo, h, r + 1, c - 2);
				memo[h][r][c] += getMemoValue(memo, h, r - 2, c + 1);
				memo[h][r][c] += getMemoValue(memo, h, r - 2, c - 1);
				memo[h][r][c] += getMemoValue(memo, h, r + 2, c + 1);
				memo[h][r][c] += getMemoValue(memo, h, r + 2, c - 1);
			}
		}
	}
	return memo[step][x][y];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

3维memo表DP问题：Bob的存活概率

【题目】给定[row，column]大小的格子，给定Bob的初始位置(a,b)，必须走k步，每一步随机一个方向上下左右走一格，如果越界则会死掉，问Bob的存活概率。

/*
【题目】给定[M，N]大小的格子，给定Bob的初始位置(row,col)，
必须走k步，每一步随机一个方向上下左右走一格，如果越界则会死掉，问Bob的存活概率。
*/

// M*N的区域，从(row, col)位置出发，走rest步，求生存方法数
long aliveRecur(int M, int N, int row, int col, int rest) {
	// 越界的情况
	if (row < 0 || row == M || col < 0 || col == N) {
		return 0;
	}
	// row，col没越界
	if (rest == 0) {
		return 1;
	}
	// 还没走完，也没越界
	long live = aliveRecur(M, N, row - 1, col, rest - 1);
	live += aliveRecur(M, N, row + 1, col, rest - 1);
	live += aliveRecur(M, N, row, col - 1, rest - 1);
	live += aliveRecur(M, N, row, col + 1, rest - 1);
	return live;
}

// 求最大公约数
long myGCD(long x, long y)
{
	while (y ^= x ^= y ^= x %= y);
	return x;
}
string aliveBob(int M, int N, int row, int col, int k) {
	long alive = aliveRecur(M, N, row, col, k);
	long all = pow(4, k);
	long gcd = myGCD(all, alive);
	return to_string(alive / gcd) + "/" + to_string(all / gcd);
}
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

改动态规划：
范围圈定：
row∈[0,M]，col∈[0,N]
step∈[0,k]
终点标定：
位置(row, col)， step = k
边界值初始化
当step为0时，在范围内的row和col都是1
memo表依赖关系
step，依赖step-1的4个可以走的点。
故假定构建三维memo表，step为高，从底层往上遍历。

int getBobVaule(vector<vector<vector<int>>>& memo, int h, int row, int col, int M, int N) {
	if (row < 0 || row == M || col < 0 || col == N) {
		return 0;
	}
	return memo[h][row][col];
}

string aliveBobDP(int M, int N, int x, int y, int k) {
	// 初始都为0
	vector<vector<vector<int> > > memo(k + 1, vector<vector<int> >(M, vector<int>(N, 0)));
	// step = 0 ，都是1
	for (int i = 0; i < M; i++) {
		for (int j = 0; j < N; j++) {
			memo[0][i][j] = 1;
		}
	}
	// step步的值依赖于step - 1步的值，step从1开始遍历，自下向上
	for (int rest = 1; rest < k + 1; rest++) {
		for (int row = 0; row < M; row++) {
			for (int col = 1; col < N; col++) {
				memo[rest][row][col] += getBobVaule(memo, rest - 1, row - 1, col, M, N);
				memo[rest][row][col] += getBobVaule(memo, rest - 1, row + 1, col, M, N);
				memo[rest][row][col] += getBobVaule(memo, rest - 1, row, col - 1, M, N);
				memo[rest][row][col] += getBobVaule(memo, rest - 1, row, col + 1, M, N);
			}
		}
	}
	long alive = memo[k][x][y];
	long all = pow(4, k);
	long gcd = myGCD(all, alive);
	return to_string(alive / gcd) + "/" + to_string(all / gcd);
}
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

memo表的斜率优化

【题目】给定正数数组arr，每个值代表可用的硬币币值，arr中无重复元素，不限每中币值硬币的数目，给定目标值target，问组成target的硬币方案数目。

暴力规划版，每种硬币决定要多少个，直至累计币值累加大于target。

/*
【题目】给定正数数组arr，每个值代表可用的硬币币值，arr中无重复元素
，不限每中币值硬币的数目，给定目标值target，问组成target的硬币方案数目。
*/

// 暴力递归
// arr中index前的硬币是否选择，选几个已经确定，当前来到index位置
// 剩余rest要达成，返回方法数
int uniqueCoinRecur(int index, vector<int> &arr, int rest) {
	if (index == arr.size()) {
		return rest == 0 ? 1 : 0;
	}
	int ways = 0;
	for (int num = 0; arr[index] * num <= rest; num++) {
		ways += uniqueCoinRecur(index + 1, arr, rest - arr[index] * num);
	}
	return ways;
}

int  uniqueCoinWays(vector<int> arr, int target) {
	return uniqueCoinRecur(0, arr, target);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

改动态规划：
范围圈定：
index∈[0,arr.size]，rest∈[0,target]
终点标定：
index = arr.size()，rest = 0
边界值初始化
当index = arr.size()，只有rest = 0是1，其他位置都是0
memo表依赖关系
index行依赖于index+1行的结果，故遍历顺序从下行到上行，且index行依赖于index+1行rest为当前index代表的币值的倍数的位置的数据。
？处的数据为下边币值倍数位置数据相加，×出的数据为它下边币值倍数位置数据相加。
这里就会总结出，其实index行的数据右边的值等于左边的值再加上它下边的值。
这边是斜率优化的情况，即不通过for循环枚举每个位置，按照先后关系得到所需要的值。

// 改为DP
int uniqueCoinDP(vector<int> arr, int target) {
	if (arr.size() < 1 || target < 0) {
		return 0;
	}
	// 初始都赋值为0
	vector<vector<int>> memo(arr.size() + 1, vector<int>(target + 1, 0));
	// index = arr.size() 时，只有rest = 0为1，其余为0，rest=0，都为1
	memo[arr.size()][0] = 1;
	// 自下行往上行构建memo表
	for (int index = arr.size() - 1; index >= 0; index--) {

		for (int rest = 0; rest <= target; rest++) {
			// 首先方法数 = 它下边行的值（当前index硬币数可以为0）
			memo[index][rest] = memo[index + 1][rest];
			// 其次假如当前index选择后，不会导致越界，方法数要再加上它前边一个数
			if (rest - arr[index] >= 0) {
				memo[index][rest] += memo[index][rest - arr[index]];
			}
		}
	}
	return memo[0][target];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

背包问题

01背包

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

每件物品只有取或者不取即0,1两种状态。

二维数组解法

1. 假定dp[i][j] 表示物品0-i任意取 ，放进容量为j的背包中所能装的最大重量。那么根据此定义，dp[n - 1][w]即为01背包题意所求。

2. 确定递推公式
   0 - i 每个物品都有两种选择，放或者不放，假定要推导dp[i][j]，第i个物品：
   • 不放：dp[i][j] = dp[i - 1][j]
   • 放置：dp[i][j] = dp[i - 1, j - weight[i]] + value[i]

选择使得dp[i][j]更大的方案，因此递推公式为：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

3. dp数组的初始化
   从递推公式来看，dp数组由其左上方的数据值推导而来，故初始化第一行与第一列的数据即可。第一列，容量为0，因此dp值必为0，第一行，背包容量j小于0号物品的重量weight[0]的dp值为0，大于等于weight[0]的dp值为value[0]

// 初始化
vector<vector<int>> dp(weight.size(), vector<int>(bagWeight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) dp[0][j] = value[0];
1
2
3

4. 确定遍历顺序
   dp[i][j]值由左上推导，按行或按列正序遍历都可以。即先遍历物品还是先遍历背包容量都可以。相对而言，先遍历物品容易理解。

5. 举例推导，做动态规划的题目，最好举例验证推导一下dp数组的求解过程。
   
   完整测试代码：

void zeroOneBag() {
	vector<int> weight = {1, 3, 4};
	vector<int> value = {15, 20, 30};
	int bagWeight = 4;

	vector<vector<int>> dp(weight.size(), vector<int>(bagWeight + 1, 0));
	for (int j = weight[0]; j <= bagWeight; ++j) {
		dp[0][j] = value[0];
	}
	for (int i = 1; i < weight.size(); ++i) {
		for (int j = 0; j <= bagWeight; ++j) {
			if (j < weight[i]) dp[i][j] = dp[i - 1][j]; // 如果放不下，只有不放
			else dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
		}
	}
	cout << dp[weight.size() - 1][bagWeight];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

一维滚动数组解法

从二维数组的解法中，可以发现当j 小于weight[i]时，直接是沿用了上一行的结果，即每一行的前边一部分都可以沿用上一行的结果，而后边部分是通过递归公式由上一行的结果推导而来。因此假如我们先遍历物品，且逆序遍历背包容量，即可由一维的滚动数组，代替二维数组状态变化记录。
一维数组的遍历：

for (int i = 0; i < weight.size(); ++i) {
	for (int j = bagWeight; j >= weight[i]; --j) {
		d[j] = max(dp[j], dp[j - weight[i]] + value[i]);
	}
}
1
2
3
4
5

二维时的递归公式：
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
演变为一维：
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
因为是逆序遍历，每个dp[j]首先是保存了上一行的结果，在上一行的结果基础上修改。

01背包的题目应用

01背包试图找到一种最优的组合，这种组合的特点是每个元素只能有两种状态，取或者不取，所有具备这种特征的题目都可以尝试使用01背包问题的模板进行解决，特别是01背包可以解决使用回溯求解组合时由于层数太深导致回溯方法超时的问题。

分割等和子集

416. 分割等和子集

起初，该题似乎可以用回溯求解nums的一个子集，假如该子集的累计和等于nums的累计和的一半，则说明找到了这样的一个子集。需要注意的是：回溯方法能够求解的问题规模要求回溯层数小于100层，而该题中nums.length的范围是1-200，因此回溯会超时。

考虑使用01背包
根据nums.length与nums[i]的范围，nums总和范围为200 * 100 = 20000；
我们只需要找到一种子集，使得总和为nums数组总和的一半，故容量设置为10001即可。

 bool canPartition(vector<int>& nums) {
	vector<int> dp(10001, 0);
	int sum = accumulate(nums.begin(), nums.end(), 0);
	if (sum & 1) return false; // 如果sum为奇数，必不可等分
	int target = sum >> 1; // 最终要找的组合，它的累计和是nums累计和的一半。
	for (int num : nums) {
		for (int j = target; j >= num; --j) dp[j] = max(dp[j], dp[j - num] + num);
	}
	return dp[target] == target;
}
1
2
3
4
5
6
7
8
9
10

最后一块石头的重量 II‘’

1049. 最后一块石头的重量 II

这道题本质上是要将stones数组分成累计和尽量相近的两堆，两堆的差值即为所求。参考上边等和子集的做法，取累计和的一半作为target容量，查看可以放进的最多的重量。在计算target的时候，target = sum / 2 因为是向下取整，所以sum - dp[target] 一定是大于等于dp[target]的。

    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(1501, 0);
        int sum = accumulate(stones.begin(), stones.end(), 0);
        int target = sum >> 1;
        for (int i = 0; i < stones.size(); ++i) {
            for (int j = target; j >= stones[i]; --j) {
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);
            }
        }
        return sum - dp[target] - dp[target];
    }
1
2
3
4
5
6
7
8
9
10
11

目标和

494.目标和

nums累计和为sum，假定加法总和为x，则sum-x为减法总和，x - (sum - x) = target
x = (target + sum) / 2

问题转换为装满容量为x的背包，最多有多少种方法。
这就变成一种求组合数的问题了，组合数可以使用01背包动态规划优化。

动规五部曲：
1、dp[j]的含义：
dp[j] 表示：填满j（包括j）这么大容积的包，有dp[j]种方法
2、确定递推公式
有哪些来源可以推出dp[j]呢？
事实上：只要搞到nums[i]），凑成dp[j]就有dp[j - nums[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[5]有多少方法呢，也就是把 所有的 dp[j - nums[i]] 累加起来。

所以求组合类问题的公式，都是类似这种：

dp[j] += dp[j - nums[i]]

这个公式在后面在讲解背包解决排列组合问题的时候还会用到！

3、dp数组初始化
dp[0] = 1，装满容量为0的背包也有一种方法。而其他的dp[j]都可由它递推得到。
4、遍历顺序，按照滚动数组的方式，nums外层循环，容量内层循环且逆序进行。
5、举例推导递推数组。

    int findTargetSumWays(vector<int>& nums, int target) {
		int sum = accumulate(nums.begin(), nums.end(), 0);
		if (abs(target) > sum) return 0;
		if ((target + sum) % 2) return 0; // 问题转为了x = (target + sum) / 2, 所以target + sum 必须为偶数才有解。
		int bagSize = (target + sum) >> 1;
		vector<int> dp(bagSize + 1, 0);
		dp[0] = 1;
		for (int num : nums) {
			for (int j = bagSize; j >= num; --j) {
				dp[j] += dp[j - num];
			}
		}
		return dp[bagSize];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14

一和零

474.一和零

本题中strs 数组里的元素就是物品，每个物品都是一个！

而m 和 n相当于是一个背包，两个维度的背包。

确定dp数组（dp table）以及下标的含义
dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

确定递推公式
dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。

dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。

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

此时可以回想一下01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。

这就是一个典型的01背包！ 只不过物品的重量有了两个维度而已。

    int findMaxForm(vector<string>& strs, int m, int n) {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
		for (string str : strs) { // 遍历物品
			int x = 0, y = 0;
			for (char c : str) {
				if (c == '0') ++x;
				else ++y;	
			}
			// 遍历两个维度的背包容量
			for (int i = m; i >= x; --i) {
				for (int j = n; j >= y; --j) {
					dp[i][j] = max(dp[i - x][j - y] + 1, dp[i][j]);
				}
			}
		}
		return dp[m][n];
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

完全背包

有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。

完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
01背包的核心代码：

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5

01背包内嵌的循环背包容量是从大到小遍历，为了保证每个物品仅被添加一次。

而完全背包的物品是可以添加多次的，所以背包容量要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}
1
2
3
4
5
6

完全背包与01背包代码实现上的不同之处也只在于遍历的顺序，01背包，背包容量从大到小遍历，完全背包，背包容量从小到大遍历。

完全背包的题目应用

零钱兑换 II

518. 零钱兑换 II

背包解决组合问题时的递推公式：
dp[j] += dp[j - coins[i]];

代码实现：

    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1);
        dp[0] = 1;
        for (int c : coins) {
            for (int j = c; j <= amount; ++j) dp[j] += dp[j - c];
        }
        return dp[amount];
    }
1
2
3
4
5
6
7
8

关于遍历顺序需要注意：
假如外层循环遍历物品，内层循环遍历背包：

for (int i = 0; i < coins.size(); i++) { // 遍历物品
    for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量
        dp[j] += dp[j - coins[i]];
    }
}
1
2
3
4
5

假设：coins[0] = 1, coins[1] = 5。
那么就是先把1加入计算，然后再把5加入计算，得到的方法数量只有{1, 5}这种情况。而不会出现{5, 1}的情况。
所有这种遍历顺序中dp[j]里边计算的是组合数
如果把两个for交换顺序，代码如下：

for (int j = 0; j <= amount; j++) { // 遍历背包容量
    for (int i = 0; i < coins.size(); i++) { // 遍历物品
        if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];
    }
}
1
2
3
4
5

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

此时dp[j]里算出来的就是排列数！

1、使用完全背包的思路求解组合排列问题，先遍历物品后遍历背包容量得到组合数，先遍历背包容量后遍历物品，得到排列数

2、应注意遍历的起始点，内层遍历背包容量时，从coins[i]开始遍历，因为小于coins[i]的容量放不下，沿用之前的结果。内层遍历物品时，遍历范围是所有物品，但要注意，仅在j - coins[i] >= 0， 即当前的容量可以放下该物品时，进行状态转移。

组合总和 Ⅳ

377. 组合总和

注意题目中说明了，顺序不同的序列被视为不同的组合，因此这里求解的实际上是排列数！！！