动态规划基础

博主： RearWaves
发布时间：2023 年 04 月 15 日
430 次浏览
2 条评论
1934字数
分类：算法设计

> **特别声明:** 本博客是我在学习[acwing网站](https://www.acwing.com/)中的算法课程中所记录的笔记, 部分资源来源于网络, 如果有侵权,请及时联系作者删除相关的部分.
> 
> 如果有错误可以私信作者(qq:**1351798781**)进行更改, 非常感谢.
> 
> 欢迎够买[正版ACwing课程](https://www.acwing.com/activity)(不是广告, ACwing没有打钱).

# 动态规划1

# 1 背包问题

## 1.1 01背包问题

特点: 每件物品最多用一次.

![Hongda_2022-11-19_20-46-44](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_20-46-44.png)

### [2. 01背包问题](https://www.acwing.com/problem/content/2/)

有 N 件物品和一个容量是 V 的背包. 每件物品只能使用一次. 第 i 件物品的体积是 v[i], 价值是 w[i].

求解将哪些物品装入背包, 可使这些物品的总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式: 第一行两个整数, N, V, 用空格隔开, 分别表示物品数量和背包容积. 接下来有 N 行, 每行两个整数表示第 i 件物品的体积和价值.

输出格式: 输出最大价值.

**方法一: 朴素版**

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N][N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	//f[0][0~m]已经被初始化为0
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			//不考虑第i个物品
			f[i][j] = f[i - 1][j];
			//考虑第i个物品时需判断容积是否足够
			if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
			//放前i-1个物品留有第i个物品的体积, 并把第i个物品的价值加上
		}
	}
	cout << f[n][m] << endl;
	return 0;
}
```

**方法二:优化版**

> 1. 计算f[i]时只用到了 f[i - 1] (使用滚动数组);
> 2. f[i]中的状态 f[i - 1] [j] 和 f[i - 1] [j - v[i]] 第二个 [] 均 <= j;

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	//f[0][0~m]已经被初始化为0
	for (int i = 1; i <= n; i++) {
		//倒叙枚举,放置f[j-v[i]]被覆盖掉
		for (int j = m; j >= v[i]; j--) {
			//不考虑第i个物品 f[j] = f[j];
			//考虑第i个物品 if (j >= v[i]) 
			f[j] = max(f[j], f[j - v[i]] + w[i]);
			//放前i-1个物品留有第i个物品的体积, 并把第i个物品的价值加上
		}
	}
	cout << f[m] << endl;
	return 0;
}
```

## 1.2 完全背包问题

特点: 每件物品有无限个.

![Hongda_2022-11-19_21-36-51](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_21-36-51.png)

### [3. 完全背包问题](https://www.acwing.com/problem/content/3/)

有 N 件物品和一个容量是 V 的背包. 每种物品都有无限件可用. 第 i 件物品的体积是 v[i], 价值是 w[i].

求解将哪些物品装入背包, 可使这些物品的总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式: 第一行两个整数, N, V, 用空格隔开, 分别表示物品数量和背包容积. 接下来有 N 行, 每行两个整数表示第 i 件物品的体积和价值.

输出格式: 输出最大价值.

**方法一:朴素版(会超时)**

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N][N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	//f[0][0~m]已经被初始化为0
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k * v[i] <= j; k++) {
				f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
			}
		}
	}
	cout << f[n][m] << endl;
	return 0;
}
```

**方法二:优化版**

![Hongda_2022-11-19_21-51-16](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_21-51-16.png)

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N][N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	//f[0][0~m]已经被初始化为0
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			if(j>=v[i]) f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
		}
	}
	cout << f[n][m] << endl;
	return 0;
}
```

**方法三:最终版**

![Hongda_2022-11-19_22-42-00](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_22-42-00.png)

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	//f[0][0~m]已经被初始化为0
	for (int i = 1; i <= n; i++) {
		for (int j = v[i]; j <= m; j++) {
			//f[j] = [j];
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}
```

## 1.3 多重背包问题

特点: 每件物品的数量不一样, 有优化版.

### [4. 多重背包问题 I](https://www.acwing.com/problem/content/4/)

有 N 件物品和一个容量是 V 的背包. 第 i 件物品最多有 s[i] 件,体积是 v[i], 价值是 w[i].

求解将哪些物品装入背包, 可使这些物品的总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式:第一行两个整数, N, V, 用空格隔开, 分别表示物品数量和背包容积. 接下来有 N 行, 每行三个整数分别表示第 i 种物品的体积、价值和数量.

输出格式:输出最大价值.

**方法一:朴素版**

```c++
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= m; j++) {
			for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
				f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);
			}
		}
	}
	cout << f[n][m] << endl;
	return 0;
}
```

### [5. 多重背包问题 II](https://www.acwing.com/problem/content/5/)

相比于上一个多重背包,数据范围:N:1000;V:2000;v[i],w[i],s[i]:2000.

优化后时间复杂度由O(NVS)降低为O(NVlogS).

![Hongda_2022-11-20_08-46-10](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-20_08-46-10.png)

**方法二:二进制优化**

```c++
const int N = 25000, M = 2010;
int n, m;
int v[N], w[N];
int f[N];
int main() {
	cin >> n >> m;
	int cnt = 0;	//当前记录的背包的索引
	for (int i = 1; i <= n; i++) {
		int a, b, s;
		cin >> a >> b >> s;
		int k = 1;
		//将背包组合成1个, 2个, 4个, 8个...c个
		while (k <= s) {
			cnt++;
			v[cnt] = a * k;		//组合后的体积
			w[cnt] = b * k;		//组合后的价值
			s -= k;
			k *= 2;
		}
		if (s > 0) {
			cnt++;
			v[cnt] = a * s;
			w[cnt] = b * s;
		}
	}
	n = cnt;	//将背包由n个拓展到cnt个
	//跑一便01背包
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= v[i]; j--) {
			f[j] = max(f[j], f[j - v[i]] + w[i]);
		}
	}
	cout << f[m] << endl;
	return 0;
}
```

## 1.4 分组背包问题

特点: N组, 每组里面物品有若干个, 每组里面最多选一个物品.

![Hongda_2022-11-20_09-44-39](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-20_09-44-39.png)

### [9. 分组背包问题](https://www.acwing.com/problem/content/9/)

有 N 组物品和一个容量是 V 的背包. 每组物品有若干个, 同一组内的物品最多只能选一个. 每件物品的体积是 v[i, j], 价值是 w[i, j], 其中 i 是组号, j 是组内编号.

求解将哪些物品装入背包, 可使物品总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式:第一行有两个整数 N, V, 用空格隔开, 分别表示物品组数和背包容量. 接下来有 N 组数据: 每组数据第一行有一个整数 S[i], 表示第 i 个物品组的物品数量; 每组数据接下来有 S[i] 行, 每行有两个整数分别表示第 i 个物品组的第 j 个物品的体积和价值;

输出格式:输出最大价值.

```c++
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		cin >> s[i];
		for (int j = 0; j < s[i]; j++)
			cin >> v[i][j] >> w[i][j];
	}
	for (int i = 1; i <= n; i++) {
		for (int j = m; j >= 0; j--) {
			for (int k = 0; k < s[i]; k++) {
				if (v[i][k] <= j)
					f[j] = max(f[j], f[j - v[i][k]] + w[i][k]);
					//f[i][j]=max(f[i-1][j],f[i-1][j-v[i][k]]+w[i][k]);
			}
		}
	}
	cout << f[m] << endl;
	return 0;
}
```

# 2 线性dp

时间复杂度: 状态数 X 计算每个状态的时间.

### [898. 数字三角形](https://www.acwing.com/problem/content/900/)

给定一个如下图所示的数字三角形, 从顶部出发, 在每一结点可以选择移动至其左下方的结点或移动至其右下方的结点, 一直走到底层, 要求找出一条路径, 使路径上的数字的和最大.

```
7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
```

![Hongda_2022-11-28_22-55-34](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-28_22-55-34.png)

```c++
const int N = 510, INF = 1e9;
int n;
int a[N][N];
int f[N][N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &a[i][j]);
	//因为有负数, 所以应该将两边也设为-INF
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= i + 1; j++)
			f[i][j] = -INF;
	f[1][1] = a[1][1];
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i; j++)
			f[i][j] = max(f[i - 1][j - 1] + a[i][j], f[i - 1][j] + a[i][j]);
	int res = -INF;
	for (int i = 1; i <= n; i++) res = max(res, f[n][i]);
	printf("%d\n", res);
	return 0;
}
```

倒序dp, 倒序不需要考虑边界问题.

```c++
const int N = 510;
int f[N][N];
int n;
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= i; j++) 
            cin >> f[i][j];
    for (int i = n; i >= 1; i--) 
        for (int j = i; j >= 1; j--) 
            f[i][j] = max(f[i + 1][j], f[i + 1][j + 1]) + f[i][j];
    cout << f[1][1] << endl;
}
```

### [895. 最长上升子序列](https://www.acwing.com/problem/content/897/)

给定一个长度为 N 的数列, 求数值严格单调递增的子序列的长度最长是多少.

![Hongda_2022-11-29_09-49-35](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-29_09-49-35.png)

```c++
const int N = 1010;
int n;
int a[N], f[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		f[i] = 1;	//只有a[i]一个数
		for (int j = 1; j < i; j++) {
			if (a[j] < a[i]) f[i] = max(f[i], f[j] + 1);
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++) res = max(res, f[i]);
	printf("%d\n", res);
	return 0;
}
```

如果要存储序列最长的结果, 只需要使用一个数组把每次转移的状态记录下来即可.

```c++
const int N = 1010;
int n;
int a[N], f[N], g[N];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	for (int i = 1; i <= n; i++) {
		f[i] = 1;	//只有a[i]一个数
		for (int j = 1; j < i; j++) 
			if (a[j] < a[i]) 
				if (f[i] < f[j] + 1) {
					f[i] = f[j] + 1;
					g[i] = j;
				}
	}
	int k = 1;
	for (int i = 1; i <= n; i++)
		if (f[k] < f[i]) k = i;
	printf("%d\n", f[k]);
	for (int i = 0, len = f[k]; i < len; i++) {
		printf("%d ", a[k]);
		k = g[k];
	}
	return 0;
}
```

### [896. 最长上升子序列 II](https://www.acwing.com/problem/content/898/)

给定一个长度为 N 的数列, 求数值严格单调递增的子序列的长度最长是多少.

**解题思路: **

思路: 首先数组a中存输入的数(原本的数), 开辟一个数组f用来存结果, 最终数组f的长度就是最终的答案; 假如数组f现在存了数, 当到了数组a的第i个位置时, 首先判断a[i] > f[cnt] ？

若是大于则直接将这个数添加到数组f中, 即f[++cnt] = a[i];这个操作时显然的.

当 a[i] <= f[cnt] 的时,我们就用a[i]去替代数组 f 中的第一个大于等于a[i]的数, 因为在整个过程中我们维护的数组 f 是一个递增的数组, 所以我们可以用二分查找在 logn 的时间复杂的的情况下直接找到对应的位置, 然后替换, 即f[l] = a[i].

我们用a[i]去替代f[i]的含义是: 以a[i]为最后一个数的严格单调递增序列,这个序列中数的个数为l个.

这样当我们遍历完整个数组a后就可以得到最终的结果.

时间复杂度分析: O(nlogn)

```c++
const int N = 1e5 + 10;
int n;
int a[N];
int q[N];
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    int len = 0;
    for (int i = 0; i < n; i++) {
        int l = 0, r = len;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (q[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len, r + 1);
        q[r + 1] = a[i];
    }
    printf("%d\n", len);
    return 0;
}
```

### [897. 最长公共子序列](https://www.acwing.com/problem/content/899/)

给定两个长度分别为 N 和 M 的字符串 A 和 B, 求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少.

**解题思路: **

![Hongda_2022-11-29_10-52-53](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-29_10-52-53.png)

集合划分: 以a[i],b[j]是否包含在子序列当中为依据, 因此可以分成四类:

1. a[i]不在, b[j]不在 `max=f[i−1][j−1]`
2. a[i]a[i]不在, b[j]b[j]在

看似是`max=f[i−1][j]` , 实际上无法用`f[i−1][j]`表示, 因为`f[i−1][j]`表示的是在a的前i-1个字母中出现, 并且在b的前j个字母中出现,此时b[j]不一定出现, 这与条件不完全相等, 条件给定是a[i]一定不在子序列中, b[j]一定在子序列当中, 但仍可以用`f[i−1][j]`来表示, 原因就在于条件给定的情况被包含在`f[i−1][j]`中, 即条件的情况是`f[i−1][j]`的子集, 而求的是max, 所以对结果不影响.

> 例如: 要求a, b, c的最大值可以这样求: max(max(a,b),max(b,c))虽然b被重复使用, 但仍能求出max, 求max只要保证不漏即可.

3. a[i]在, b[j]不在 原理同(2)
4. ]a[i]在, ]b[j]在 `max=f[i−1][j−1]+1`

实际上, 在计算时, 1包含在2和3的情况中, 所以1不用考虑

```c++
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
	scanf("%d%d", &n, &m);
	scanf("%s%s", a + 1, b + 1);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			f[i][j] = max(f[i - 1][j], f[i][j - 1]);
			if (a[i] == b[j]) f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
		}
	printf("%d\n", f[n][m]);
	return 0;
}
```

### [902. 最短编辑距离](https://www.acwing.com/problem/content/904/)

给定 n 个长度不超过 10 的字符串以及 m 次询问, 每次询问给出一个字符串和一个操作次数上限.

对于每次询问, 请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串.

每个对字符串进行的单个字符的插入、删除或替换算作一次操作.

![Hongda_2022-11-29_19-03-38](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-29_19-03-38.png)

状态计算:

1. 删除操作: 把a[i]删掉之后a[1~i]和b[1~j]匹配,所以之前要先做到a[1~(i-1)]和b[1~j]匹配,`f[i-1][j] + 1`.
2. 插入操作: 插入之后a[i]与b[j]完全匹配, 所以插入的就是b[j],那填之前a[1~i]和b[1~(j-1)]匹配,`f[i][j-1] + 1`.
3. 替换操作: 把a[i]改成b[j]之后想要a[1~i]与b[1~j]匹配,那么修改这一位之前, a[1~(i-1)]应该与b[1~(j-1)]匹配,`f[i-1][j-1] + 1`.但是如果本来a[i]与b[j]这一位上就相等, 那么不用改, 即`f[i-1][j-1] + 0`.

```c++
const int N = 1010;
int n, m;
char a[N], b[N];
int f[N][N];
int main() {
	scanf("%d%s", &n, a + 1);
	scanf("%d%s", &m, b + 1);
	//初始化f[0][i], 添加i个字母, 需要i步
	for (int i = 0; i <= m; i++) f[0][i] = i;
	//初始化f[i][0], 删除i个字母, 需要i步
	for (int i = 0; i <= n; i++) f[i][0] = i;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
			if (a[i] == b[j]) f[i][j] = min(f[i][j], f[i - 1][j - 1]);
			else f[i][j] = min(f[i][j], f[i - 1][j - 1] + 1);
		}
	printf("%d\n", f[n][m]);
	return 0;
}
```

### [899. 编辑距离](https://www.acwing.com/problem/content/901/)

给定 n 个长度不超过 10 的字符串以及 m 次询问, 每次询问给出一个字符串和一个操作次数上限.

对于每次询问, 请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串.

每个对字符串进行的单个字符的插入、删除或替换算作一次操作.

```c++
const int N = 15, M = 1010;
int n, m;
int f[N][N];
char str[M][N];
int edit_distance(char a[], char b[]) {
    int la = strlen(a + 1), lb = strlen(b + 1);
    for (int i = 0; i <= lb; i++) f[0][i] = i;
    for (int i = 0; i <= la; i++) f[i][0] = i;
    for (int i = 1; i <= la; i++)
        for (int j = 1; j <= lb; j++) {
            f[i][j] = min(f[i - 1][j] + 1, f[i][j - 1] + 1);
            f[i][j] = min(f[i][j], f[i - 1][j - 1] + (a[i] != b[j]));
        }
    return f[la][lb];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%s", str[i] + 1);
    while (m--) {
        char s[N];
        int limit;
        scanf("%s%d", s + 1, &limit);
        int res = 0;
        for (int i = 0; i < n; i++)
            if (edit_distance(str[i], s) <= limit)
                res++;
        printf("%d\n", res);
    }
    return 0;
}
```

# 3 区间dp

### [282. 石子合并](https://www.acwing.com/problem/content/284/)

设有 N 堆石子排成一排, 其编号为 1, 2, 3, …, N.

每堆石子有一定的质量, 可以用一个整数来描述, 现在要将这 NN 堆石子合并成为一堆.

每次只能合并相邻的两堆, 合并的代价为这两堆石子的质量之和, 合并后与这两堆石子相邻的石子将和新堆相邻, 合并时由于选择的顺序不同, 合并的总代价也不相同.

例如有 4 堆石子分别为 `1 3 5 2`,  我们可以先合并 1、2 堆, 代价为 4, 得到 `4 5 2`,  又合并 1, 2 堆, 代价为 9, 得到 `9 2` , 再合并得到 11, 总代价为 4+9+11=24;

如果第二步是先合并 2, 3 堆, 则代价为 7, 得到 `4 7`, 最后一次合并代价为 11, 总代价为 4+7+11=22.

问题是: 找出一种合理的方法, 使总的代价最小, 输出最小代价.

![捕获2.PNG](https://www.rearwaves.com/usr/assets/algorithm/dynamic/1606_bf26e786b8-捕获2.png)

基本结构: `f[i][j]`表示 区间 [i,j] 的答案

枚举中点 k; `f[i][j]=min(f[i][k]+f[k+1][j]+x[i,j])`,即[i, j]段合并可以理解为在中间一点分开, 先合并左边的[i, k],再合并右边的[k+1, j],最后将这两堆合并, 合并的体力为x[i,j].

注: x[i,j] 表示区间 [i,j] 的 x 数组的区间和.

因为区间和只有查询, 没有修改, 考虑前缀和来维护区间和

```c++
const int N = 310;
int n;
int s[N];
int f[N][N];
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &s[i]);
    
    for (int i = 1; i <= n; i++) s[i] += s[i - 1];
    
    for (int len = 2; len <= n; len++)
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            f[l][r] = 1e8;
            for (int k = l; k < r; k++)
                f[l][r] = min(f[l][r], f[l][k] + f[k + 1][r] + s[r] - s[l - 1]);
        }
    printf("%d\n", f[1][n]);
    return 0;
}
```

# 4 计数类dp

### [900. 整数划分](https://www.acwing.com/problem/content/902/)

一个正整数 n 可以表示成若干个正整数之和, 形如: n=n1+n2+…+nk, 其中 n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1.

我们将这样的一种表示称为正整数 n 的一种划分.

现在给定一个正整数 n, 请你求出 n 共有多少种不同的划分方法.

**方法一:完全背包**

`f[i][j]`表示只从1~i中选, 且总和等于j的方案数

![整数划分-优化前.jpg](https://www.rearwaves.com/usr/assets/algorithm/dynamic/42937_8ba34a42de-整数划分-优化前.jpg)

优化:

`f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2i] + ... + f[i-1][j-si]`

`f[i][j-i] =           f[i-1][j-i] + f[i-1][j-2i] + ... + f[i-1][j-si]`

替换: `f[i][j] = f[i-1][j] + f[i][j-1]`

优化一维: `f[j] = f[j] + f[j-i]`

```c++
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N];
int main() {
	cin >> n;
	f[0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = i; j <= n; j++)
			f[j] = (f[j] + f[j - i]) % mod;
	cout << f[n] << endl;
	return 0;
}
```

**方法二:计数类DP**

`f[i][j]`表示总和为i, 总个数为j的方案数

![计数类DP.jpg](https://www.rearwaves.com/usr/assets/algorithm/dynamic/42937_d5f9941cde-计数类DP.jpg)

```c++
const int N = 1010, mod = 1e9 + 7;
int n;
int f[N][N];
int main() {
	cin >> n;
	f[1][1] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j <= i; j++)
			f[i][j] = (f[i - 1][j - 1] + f[i - j][j]) % mod;
	int res = 0;
	for (int i = 1; i <= n; i++) res = (res + f[n][i]) % mod;
	cout << res << endl;
	return 0;
}
```

# 5 数位统计dp

### [338. 计数问题](https://www.acwing.com/problem/content/340/)

给定两个整数 a 和 b, 求 a 和 b 之间的所有数字中 0∼9 的出现次数.

例如, a=1024, b=1032, 则 a 和 b 之间共有 9 个数如下:

```
1024 1025 1026 1027 1028 1029 1030 1031 1032
```

其中 `0` 出现 10 次, `1` 出现 10 次, `2` 出现 7 次, `3` 出现 3 次等等…

**解题思路: **分类讨论

比如说我要找[1,abcdefg]中的数中1出现的个数, 就得先求1在每一个位置上出现的次数. 比如我要找第4位上出现的1的数有几个, 就是要找满足 1 <= xxx1yyy <= abcdefg.

1. xxx∈[000,abc-1] , yyy∈[000,999] , ans += abc*1000
   //如果前三位没填满, 则后三位就可以随便填.
2. xxx==abc , yyy∈?
   if(d<1)  yyy不存在, ans += 0;
   if(d==1) yyy∈[000,efg], ans += efg+1;
   if(d>1)  yyy∈[000,999], ans += 1000.
   //如果前三位填满了, 后三位怎么填取决于当前这一位

然后每一位上都是这么讨论的, 最后累加起来就是总共出现的次数, 这样就是求出来了[1,n]的. 然后如果我想求[l,r]的用一下前缀和就搞定了.

**特殊情况:**

1) x在第1位上出现的次数(不用考虑前半段):
   
   bcdefg∈[00000,bcdefg] , ans += bcdefg+1.

2. x在最后一位上出现的次数(不用考虑后半段):
   如果g<x,  那么不存在这样的数, ans += 0;
   如果g==x, 那么有一个这样的数, ans += 1;
   如果g>x,  yyyyyy∈[000000,abcdef] , ans += abcdef+1.

3) 如果我们枚举的数是0的话 :
   0不能在第一位 , 而且枚举到的这一位前面不能全是0, 即xxx∈[001,abc-1].

```c++
//求枚举到的数字前面位置组成的数字是多少
int get(vector<int> num, int l, int r) {
	int res = 0;
	for (int i = l; i >= r; i--)
		res = res * 10 + num[i];
	return res;
}
//求10的x次方
int power10(int x) {
	int res = 1;
	while (x--) res *= 10;
	return res;
}
// 求从1到数n中数i出现的次数
int count(int n, int x) {
	if (!n) return 0;
	vector<int> num;	//把n的每一位抠出来
	while (n) {
		num.push_back(n % 10);
		n /= 10;
	}
	n = num.size();	//n现在是传入数n的位数
	int res = 0;
	//从最高位开始枚举;当x==0时,从第二位开始枚举
	for (int i = n - 1 - !x; i >= 0; i--) {
		if (i < n - 1) {	//只有枚举的不是第一位时才有第一种情况
			res += get(num, n - 1, i + 1) * power10(i);
			if (!x) res -= power10(i);
		}
		if (num[i] == x) res += get(num, i - 1, 0) + 1;
		else if (num[i] > x) res += power10(i);
	}
	return res;
}
int main() {
	int a, b;
	while (cin >> a >> b, a || b) {
		if (a > b) swap(a, b);	//不一定小数在前面
		for (int i = 0; i < 10; i++)
			cout << count(b, i) - count(a - 1, i) << ' ';
		cout << endl;
	}
}
```

**其他写法: **

```c++
int get(int n) { // 求数n的位数
    int res = 0;
    while (n) res ++, n /= 10;
    return res;
}
int count(int n, int i) { // 求从1到数n中数i出现的次数
    int res = 0, dgt = get(n);
    for (int j = 1; j <= dgt; ++ j) {
    /* p为当前遍历位次(第j位)的数大小 <10^(右边的数的位数)>, Ps:从左往右(从高位到低位)
        l为第j位的左边的数, r为右边的数, dj为第j位上的数 */
        int p = pow(10, dgt - j), l = n / p / 10, r = n % p, dj = n / p % 10;

// ps:下文的xxx、yyy均只为使读者眼熟, 并不严格只是三位数啊~ 然后后续的...就代表省略的位数啦~
        /* 求要选的数在i的左边的数小于l的情况: 
(即视频中的xxx1yyy中的xxx的选法) --->
    1)、当i不为0时 xxx : 0...0 ~ l - 1, 即 l * (右边的数的位数) == l * p 种选法
    2)、当i为0时 由于不能有前导零 故xxx: 0....1 ~ l - 1, 
                    即 (l-1) * (右边的数的位数) == (l-1) * p 种选法 */
        if (i) res += l * p;
        else res += (l - 1) * p;

/* 求要选的数在i的左边的数等于l的情况: (即视频中的xxx == l 时)
    (即视频中的xxx1yyy中的yyy的选法)--->
                        1)、i > dj时 0种选法
                        2)、i == dj时 yyy : 0...0 ~ r 即 r + 1 种选法
                        3)、i < dj时 yyy : 0...0 ~ 9...9 即 10^(右边的数的位数) == p 种选法 */
        if (i == dj) res += r + 1;
        if (i < dj) res += p;
    }
    return res; // 返回结果
}
int main() {
    int a, b;
    while (cin >> a >> b, a) { // 输入处理, 直到输入为0停止
        if (a > b) swap(a, b); // 预处理-->让a为较小值, b为较大值
        for (int i = 0; i <= 9; ++ i) cout << count(b, i) - count(a - 1, i) << ' '; 
        // 输出每一位数字(0 ~ 9)分别在[a,b]中出现的次数<利用前缀和思想: [l,r]的和=s[r] - s[l - 1]>
        cout << endl; //换行
    }
    return 0; // 惯例: 结束快乐~
}
```

# 6 状态压缩DP

### [291. 蒙德里安的梦想](https://www.acwing.com/problem/content/293/)

求把 N×M 的棋盘分割成若干个 1×2 的长方形, 有多少种方案.

例如当 N=2, M=4 时, 共有 5 种方案. 当 N=2, M=3 时, 共有 3 种方案.

如下图所示:

![2411_1.jpg](https://www.rearwaves.com/usr/assets/algorithm/dynamic/19_4dd1644c20-2411_1.jpg)

输入格式: 每组测试用例占一行, 包含两个整数 N 和 M. 当输入用例 N=0, M=0 时, 表示输入终止, 且该用例无需处理.

**解题思路: **

摆放方块的时候, 先放横着的, 再放竖着的. 总方案数等于只放横着的小方块的合法方案数.

如何判断, 当前方案数是否合法？ 所有剩余位置能否填充满竖着的小方块. 可以按列来看, 每一列内部所有连续的空着的小方块需要是偶数个.

这是一道动态规划的题目, 并且是一道状态压缩的dp: 用一个N位的二进制数, 每一位表示一个物品, 0/1表示不同的状态. 因此可以用$0→2^N−1$(N二进制对应的十进制数)中的所有数来枚举全部的状态.

**状态表示: **`f[i][j]`表示已经将前 i-1 列摆好, 且从第i−1列, 伸出到第 i 列的状态是 j 的所有方案. 其中j是一个二进制数, 用来表示哪一行的小方块是横着放的, 其位数和棋盘的行数一致.

**状态转移:** 既然第 i 列固定了, 我们需要看第 i-2 列是怎么转移到到第 i-1 列的(看最后转移过来的状态). 假设此时对应的状态是k(第i-2列到第i-1列伸出来的二进制数, 比如00100), k也是一个二进制数, 1表示哪几行小方块是横着伸出来的, 0表示哪几行不是横着伸出来的.

它对应的方案数是 `f[i−1,k]`, 即前i-2列都已摆完, 且从第i-2列伸到第i-1列的状态为 k 的所有方案数.

k需要满足的条件: 首先k不能和j在同一行: 因为从i-1列到第i列是横着摆放的12的方块, 那么i-2列到i-1列就不能是横着摆放的, 否则就是1 3的方块了！这与题意矛盾. 所以k和j不能位于同一行.

既然不能同一行伸出来, 那么对应的代码为 `(k & j )==0`, 表示两个数相与, 如果有1位相同结果就不是0,  `(k & j )==0` 表示 k和j没有1位相同,  即没有1行有冲突.

既然从第i-1列到第i列横着摆的, 和第i-2列到第i-1列横着摆的都确定了, 那么第i-1列空着的格子就确定了, 这些空着的格子将来用作竖着放. 如果某一列有这些空着的位置, 那么该列所有连续的空着的位置长度必须是偶数.

总共m列, 我们假设列下标从0开始, 即第0列, 第1列……, 第m-1列. 根据状态表示`f[i][j]` 的定义, 我们答案是什么呢？ 请读者返回定义处思考一下. 答案是`f[m][0]`,  意思是前m-1列全部摆好,且从第m-1列到m列状态是0(意即从第m-1列到第m列没有伸出来的)的所有方案, 即整个棋盘全部摆好的方案.

**时间复杂度:** dp的时间复杂度 =状态表示× 状态转移

状态表示 `f[i][j]` 第一维i可取11, 第二维j(二进制数)可取2^11^ , 所以状态表示 11×2^11^, 状态转移 也是2^11^.

所以总的时间复杂度$11×2^{11}×2^{11}≈4×10^7$, 可以过.

`f[0][0]`第一个0表示第0列, 第二个0表示第0列伸出去的状态为0, 那么第0列的方案只能是竖摆这一种, 至于不需要考虑竖摆的奇偶数合法性, 因为第0列本身就是为了推导第1列而虚构的. 如果假设`f[0][0]=0`, 那么后面所有的递推就无从谈起.

`f[m][n]`中n理解为从m列伸出去的状态更合理. `f[m][0]`时, 表示当摆到m列满列并没有伸出去的状态时, 就是最多方案数了.

```c++
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
bool st[N];

int main() {
	int n, m;
	while (cin >> n >> m, n || m) {
		memset(f, 0, sizeof f);
		//预处理所有的状态是不是不存在连续奇数个0
		for (int i = 0; i < 1 << n; i++) {
			st[i] = true;
			int cnt = 0;	//当前这段连续0的个数
			for (int j = 0; j < n; j++) {
				if (i >> j & 1) {	//如果是1判断cnt是否合法
					if (cnt & 1) st[i] = false;
					cnt = 0;
				}
				else cnt++;
			}
			if (cnt & 1) st[i] = false;	//判断最后是否合法
		}
		//第0列什么都不放是一种放法,而且没有上一列捅出来
		f[0][0] = 1;
		for (int i = 1; i <= m; i++)		//枚举每一列
			for (int j = 0; j < 1 << n; j++)	//枚举每个状态
				for (int k = 0; k < 1 << n; k++)	//枚举上一列的每个状态
					if ((j & k) == 0 && st[j  | k])
						f[i][j] += f[i - 1][k];
		cout << f[m][0] << endl;
	}
	return 0;
}
```

### [91. 最短Hamilton路径](https://www.acwing.com/problem/content/93/)

给定一张 n 个点的带权无向图, 点从 0∼n−1 标号, 求起点 0 到终点 n−1 的最短 Hamilton 路径.

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次.

**解题思路: **

首先想下暴力算法, 这里直接给出一个例子. 比如数据有 5 个点, 分别是 0,1,2,3,4那么在爆搜的时候, 会枚举一下六种路径情况(只算对答案有贡献的情况的话):

- case 1: 0→1→2→**3→4**;
- case 2: 0→1→3→2→4;
- case 3: 0→2→1→**3→4**;
- case 4: 0→2→3→1→4;
- case 5: 0→3→1→2→4;
- case 6: 0→3→2→1→4;

那么观察一下 case 1 和 case 3, 可以发现, 我们在计算从点 0 到点 3 的路径时, 其实并不关心这两中路径经过的点的顺序, 而是只需要这两种路径中的较小值, 因为只有较小值可能对答案有贡献. 所以, 我们在枚举路径的时候, 只需要记录**两个属性: 当前经过的点集, 当前到了哪个点**.

而当前经过的点集不是一个数. 观察到数据中点数不会超过 2020, 我们可以用一个二进制数表示当前经过的点集. 其中第 i 位为 `1/0` 表示`是/否`经过了点 i.
然后用闫式 dp 分析法考虑 dp:

状态表示: `f[state][j]`. 其中 state 是一个二进制数, 表示点集的方法如上述所示.

- 集合: 经过的点集为 state, 且当前到了点 j 上的所有路径.
- 属性: 路径总长度的最小值

状态计算: 假设当前要从点 k 转移到 j. 那么根据 Hamilton 路径的定义, 走到点 k 的路径就不能经过点 j, 所以就可以推出状态转移方程`f[state][j] = min{f[state ^ (1 << j)][k] + w[k][j]}`. 其中`w[k][j]`表示从点 k 到点 j 的距离, `^`表示异或运算. `state ^ (1 << j)`是将 state 的第 j 位改变后的值(如果 state 的第 j 位是 1 那么将其改为 0, 否则将 state 的第 j 位改为 1).

由于到达点 j 的路径一定经过点 j, 也就是说当 state 的第 j 位为 1 的时候, `f[state][j]` 才可以被转移, 所以 `state ^ (1 << j)` 其实就是将 state 的第 j 位改为 0, 这样也就符合了 **走到点 k 的路径就不能经过点 j** 这个条件.

所有状态转移完后, 根据 `f[state][j]` 的定义, 要输出 `f[111⋯11(n个1)][n−1]`.

**时间复杂度:**

枚举所有 state 的时间复杂度是 O(2^n^), 枚举 j 的时间复杂读是 O(n), 枚举 k 的时间复杂度是 O(n), 所以总的时间复杂度是 O(n^2^2^n^).

```c++
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> w[i][j];
	memset(f, 0x3f, sizeof f);	//状态初始化为正无穷
	f[1][0] = 0;	//从0->0,状态为1
	for (int i = 0; i < 1 << n; i++)
		for (int j = 0; j < n; j++)
			if (i >> j & 1)		//只有状态i中包含点j才有意义
				for (int k = 0; k < n; k++)		//枚举从哪个点转移过来
					if ((i - (1 << j)) >> k & 1)	//i除去点j后必须包含点k
						f[i][j] = min(f[i][j], f[i - (1 << j)][k] + w[k][j]);
	cout << f[(1 << n) - 1][n - 1] << endl;
	return 0;
}
```

# 7 树形DP

### [285. 没有上司的舞会](https://www.acwing.com/problem/content/287/)

Ural 大学有 N 名职员, 编号为 1∼N. 他们的关系就像一棵以校长为根的树, 父节点就是子节点的直接上司. 每个职员有一个快乐指数, 用整数 H~i~ 给出, 其中 1≤i≤N.

现在要召开一场周年庆宴会, 不过, 没有职员愿意和直接上司一起参会. 在满足这个条件的前提下, 主办方希望邀请一部分职员参会, 使得所有参会职员的快乐指数总和最大, 求这个最大值.

**解题思路: ** O(n)

状态表示: `f[u][1]`表示以`u`为根节点的子树并且包括u的总快乐指数, `f[u][0]`表示以`u`为根节点并且不包括u的总快乐指数.

状态计算: 要想求得一棵以`u`为根节点的子树的最大指数分为两种: 选`u`节点或不选`u`节点记点u的子节点是j.

1. 选`u`, $f[u][1]+=Σf[j][0]$;
2. 不选`u`, $f[u][0]+=Σmax(f[j][1],f[j][0])$.

记根节点为`root`, 从`root`开始`dfs`一遍即可, 最后输出$max(f[root][1],f[root][0])$.

```c++
const int N = 6010;
int n;
int happy[N];
int h[N], e[N], ne[N], idx;
int f[N][2];
bool has_father[N];	//题目没有告诉父节点,需要自己判断
void add(int a, int b) {
	e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
void dfs(int u) {
	f[u][1] = happy[u];
	for (int i = h[u]; i != -1; i = ne[i]) {
		int j = e[i];	//遍历u的每一个子树
		dfs(j);
		f[u][0] += max(f[j][0], f[j][1]);
		f[u][1] += f[j][0];
	}
}
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", happy[i]);
	memset(h, -1, sizeof h);	//初始化头节点
	for (int i = 0; i < n - 1; i++) {
		int a, b;	//b是a的父节点
		scanf("%d%d", &a, &b);
		has_father[a] = true;
		add(b, a);
	}
	int root = 1;	//遍历has_father,寻找根节点
	while (has_father[root]) root++;
	dfs(root);
	printf("%d\n", max(f[root][0], f[root][1]));
	return 0;
}
```

# 8 记忆化搜索

### [901. 滑雪](https://www.acwing.com/problem/content/903/)

给定一个 R 行 C 列的矩阵, 表示一个矩形网格滑雪场. 矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度.

一个人从滑雪场中的某个区域内出发, 每次可以向上下左右任意一个方向滑动一个单位距离. 当然, 一个人能够滑动到某相邻区域的前提是该区域的高度低于自己目前所在区域的高度.

下面给出一个矩阵作为例子:

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

在给定矩阵中, 一条可行的滑行轨迹为 24−17−2−1. 在给定矩阵中, 最长的滑行轨迹为 25−24−23−…−3−2−1, 沿途共经过 25 个区域.

现在给定你一个二维矩阵表示滑雪场各区域的高度, 请你找出在该滑雪场中能够完成的最长滑雪轨迹, 并输出其长度(可经过最大区域数).

**解题思路: **O(n^2^)

本来是一个`dfs`的过程, 遍历所有的位置, 找到从当前位置往下走的最大路径, 再取最大值, 可是这样做会有很多重复的位置被重新计算过, 因此可以利用空间换时间的思想, 把遍历过的位置往下走的路径的最大值进行记录, 这就是记忆化搜索

考虑从四个方向**滑过来**的最大值, 那么当前值f(x,y)就等于四个方向**滑过来**的最大值+1. 将四个方向**滑过来**的最大值记为f(a,b), 则`f(x,y) = f(a,b)+1`, 再一步步递归进去回溯出答案.

状态表示:

- 集合: 所有从(i,j)这个点开始滑的路径长度;
- 属性: max.

状态计算: 就是搜索, 每个点能不能向上下左右动, 下面代码中的`f[x][y] = max(f[x][y],dp(a,b)+1)`; 实际上就是向四个方向判断之后转移:

- `f[i][j] = max(f[i][j],f[i-1][j]+1)`;//上
- `f[i][j] = max(f[i][j],f[i+1][j]+1)`;//下
- `f[i][j] = max(f[i][j],f[i][j-1]+1)`;//左
- `f[i][j] = max(f[i][j],f[i][j+1]+1)`;//右

```c++
const int N = 310;
int n, m;
int h[N][N];
int f[N][N];
int dx[4] = { -1, 0, 1, 0 }, dy[4] = { 0, 1, 0, -1 };
int dp(int x, int y) {
	int& v = f[x][y];	//引用:v等价于f[x][y]
	if (v != -1) return v;
	v = 1;	//初始化
	for (int i = 0; i < 4; i++) {	//枚举每一个方向
		int a = x + dx[i], b = y + dy[i];
		if (a >= 1 && a <= n && b >= 1 && b <= m && h[a][b] < h[x][y])
			v = max(v, dp(a, b) + 1);
	}
	return v;
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &h[i][j]);
	//f初始化为-1,表示每个状态都没有被算过
	memset(f, -1, sizeof f);
	int res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			res = max(res, dp(i, j));
	printf("%d\n", res);
	return 0;
}
```

最后修改：2023 年 04 月 15 日

如果觉得我的文章对你有用，请随意赞赏

2 条评论

ippchfedbe
November 21st, 2024 at 06:02 pm

你的文章充满了欢乐，让人忍不住一笑。 https://www.4006400989.com/qyvideo/74837.html

回复
zglmkjwugf
November 19th, 2024 at 07:03 pm

你的文章充满了欢乐，让人忍不住一笑。 https://www.4006400989.com/qyvideo/74837.html

回复

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

贪心讲解
评论数： 9
搜索初步
评论数： 9
竞赛常识
评论数： 6
图论初步
评论数： 6
欢迎使用 Typecho
评论数： 5

yvhnvtxwkd
《重生后我嫁给了渣男的死对头2》短片剧高清在线免费观看：htt...
enbnyxjjno
你的文章让我心情愉悦，真是太棒了！ https://ww...
opqwoumwba
《重生后我嫁给了渣男的死对头2》短片剧高清在线免费观看：htt...
weutsdhtvh
你的文章让我心情愉悦，真是太棒了！ http://www...
ijrjnzxwam
《快递爱情》剧情片高清在线免费观看：https://www.j...

贪心讲解
评论数： 9
动态规划基础
评论数： 2
欢迎使用 Typecho
评论数： 5
比赛常用技巧及库函数
评论数： 3
数据结构初步
评论数： 5

动态规划基础

RearWaves • 2023 年 04 月 15 日

# 动态规划1

# 1 背包问题

## 1.1 01背包问题

特点: 每件物品最多用一次.

![Hongda_2022-11-19_20-46-44](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_20-46-44.png)

### [2. 01背包问题](https://www.acwing.com/problem/content/2/)

有 N 件物品和一个容量是 V 的背包. 每件物品只能使用一次. 第 i 件物品的体积是 v[i], 价值是 w[i].

求解将哪些物品装入背包, 可使这些物品的总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式: 第一行两个整数, N, V, 用空格隔开, 分别表示物品数量和背包容积. 接下来有 N 行, 每行两个整数表示第 i 件物品的体积和价值.

输出格式: 输出最大价值.

**方法一: 朴素版**

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N][N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

**方法二:优化版**

> 1. 计算f[i]时只用到了 f[i - 1] (使用滚动数组);
> 2. f[i]中的状态 f[i - 1] [j] 和 f[i - 1] [j - v[i]] 第二个 [] 均 <= j;

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

## 1.2 完全背包问题

特点: 每件物品有无限个.

![Hongda_2022-11-19_21-36-51](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_21-36-51.png)

### [3. 完全背包问题](https://www.acwing.com/problem/content/3/)

有 N 件物品和一个容量是 V 的背包. 每种物品都有无限件可用. 第 i 件物品的体积是 v[i], 价值是 w[i].

求解将哪些物品装入背包, 可使这些物品的总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式: 第一行两个整数, N, V, 用空格隔开, 分别表示物品数量和背包容积. 接下来有 N 行, 每行两个整数表示第 i 件物品的体积和价值.

输出格式: 输出最大价值.

**方法一:朴素版(会超时)**

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N][N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

**方法二:优化版**

![Hongda_2022-11-19_21-51-16](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_21-51-16.png)

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N][N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

**方法三:最终版**

![Hongda_2022-11-19_22-42-00](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-19_22-42-00.png)

```c++
const int N = 1010;
int n, m;
int v[N], w[N];	//各个物品的体积和价值
int f[N];	//其中f[v][j]表示考虑前v个物品, 体积最大为j的最大价值

## 1.3 多重背包问题

特点: 每件物品的数量不一样, 有优化版.

### [4. 多重背包问题 I](https://www.acwing.com/problem/content/4/)

有 N 件物品和一个容量是 V 的背包. 第 i 件物品最多有 s[i] 件,体积是 v[i], 价值是 w[i].

求解将哪些物品装入背包, 可使这些物品的总体积不超过背包容量, 且总价值最大. 输出最大价值.

输入格式:第一行两个整数, N, V, 用空格隔开, 分别表示物品数量和背包容积. 接下来有 N 行, 每行三个整数分别表示第 i 种物品的体积、价值和数量.

输出格式:输出最大价值.

**方法一:朴素版**

```c++
const int N = 110;
int n, m;
int v[N], w[N], s[N];
int f[N][N];

### [5. 多重背包问题 II](https://www.acwing.com/problem/content/5/)

相比于上一个多重背包,数据范围:N:1000;V:2000;v[i],w[i],s[i]:2000.

优化后时间复杂度由O(NVS)降低为O(NVlogS).

![Hongda_2022-11-20_08-46-10](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-20_08-46-10.png)

**方法二:二进制优化**

## 1.4 分组背包问题

特点: N组, 每组里面物品有若干个, 每组里面最多选一个物品.

![Hongda_2022-11-20_09-44-39](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-20_09-44-39.png)

### [9. 分组背包问题](https://www.acwing.com/problem/content/9/)

求解将哪些物品装入背包, 可使物品总体积不超过背包容量, 且总价值最大. 输出最大价值.

输出格式:输出最大价值.

```c++
const int N = 110;
int n, m;
int v[N][N], w[N][N], s[N];
int f[N];

# 2 线性dp

时间复杂度: 状态数 X 计算每个状态的时间.

### [898. 数字三角形](https://www.acwing.com/problem/content/900/)

```
7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5
```

![Hongda_2022-11-28_22-55-34](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-28_22-55-34.png)

倒序dp, 倒序不需要考虑边界问题.

### [895. 最长上升子序列](https://www.acwing.com/problem/content/897/)

给定一个长度为 N 的数列, 求数值严格单调递增的子序列的长度最长是多少.

![Hongda_2022-11-29_09-49-35](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-29_09-49-35.png)

如果要存储序列最长的结果, 只需要使用一个数组把每次转移的状态记录下来即可.

### [896. 最长上升子序列 II](https://www.acwing.com/problem/content/898/)

给定一个长度为 N 的数列, 求数值严格单调递增的子序列的长度最长是多少.

**解题思路: **

若是大于则直接将这个数添加到数组f中, 即f[++cnt] = a[i];这个操作时显然的.

我们用a[i]去替代f[i]的含义是: 以a[i]为最后一个数的严格单调递增序列,这个序列中数的个数为l个.

这样当我们遍历完整个数组a后就可以得到最终的结果.

时间复杂度分析: O(nlogn)

### [897. 最长公共子序列](https://www.acwing.com/problem/content/899/)

给定两个长度分别为 N 和 M 的字符串 A 和 B, 求既是 A 的子序列又是 B 的子序列的字符串长度最长是多少.

**解题思路: **

![Hongda_2022-11-29_10-52-53](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-29_10-52-53.png)

集合划分: 以a[i],b[j]是否包含在子序列当中为依据, 因此可以分成四类:

1. a[i]不在, b[j]不在 `max=f[i−1][j−1]`
2. a[i]a[i]不在, b[j]b[j]在

> 例如: 要求a, b, c的最大值可以这样求: max(max(a,b),max(b,c))虽然b被重复使用, 但仍能求出max, 求max只要保证不漏即可.

3. a[i]在, b[j]不在 原理同(2)
4. ]a[i]在, ]b[j]在 `max=f[i−1][j−1]+1`

实际上, 在计算时, 1包含在2和3的情况中, 所以1不用考虑

### [902. 最短编辑距离](https://www.acwing.com/problem/content/904/)

给定 n 个长度不超过 10 的字符串以及 m 次询问, 每次询问给出一个字符串和一个操作次数上限.

对于每次询问, 请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串.

每个对字符串进行的单个字符的插入、删除或替换算作一次操作.

![Hongda_2022-11-29_19-03-38](https://www.rearwaves.com/usr/assets/algorithm/dynamic/Hongda_2022-11-29_19-03-38.png)

状态计算:

### [899. 编辑距离](https://www.acwing.com/problem/content/901/)

给定 n 个长度不超过 10 的字符串以及 m 次询问, 每次询问给出一个字符串和一个操作次数上限.

对于每次询问, 请你求出给定的 n 个字符串中有多少个字符串可以在上限操作次数内经过操作变成询问给出的字符串.

每个对字符串进行的单个字符的插入、删除或替换算作一次操作.

# 3 区间dp

### [282. 石子合并](https://www.acwing.com/problem/content/284/)

设有 N 堆石子排成一排, 其编号为 1, 2, 3, …, N.

每堆石子有一定的质量, 可以用一个整数来描述, 现在要将这 NN 堆石子合并成为一堆.

例如有 4 堆石子分别为 `1 3 5 2`,  我们可以先合并 1、2 堆, 代价为 4, 得到 `4 5 2`,  又合并 1, 2 堆, 代价为 9, 得到 `9 2` , 再合并得到 11, 总代价为 4+9+11=24;

如果第二步是先合并 2, 3 堆, 则代价为 7, 得到 `4 7`, 最后一次合并代价为 11, 总代价为 4+7+11=22.

问题是: 找出一种合理的方法, 使总的代价最小, 输出最小代价.

![捕获2.PNG](https://www.rearwaves.com/usr/assets/algorithm/dynamic/1606_bf26e786b8-捕获2.png)

基本结构: `f[i][j]`表示 区间 [i,j] 的答案

注: x[i,j] 表示区间 [i,j] 的 x 数组的区间和.

因为区间和只有查询, 没有修改, 考虑前缀和来维护区间和

# 4 计数类dp

### [900. 整数划分](https://www.acwing.com/problem/content/902/)

一个正整数 n 可以表示成若干个正整数之和, 形如: n=n1+n2+…+nk, 其中 n1≥n2≥…≥nk,k≥1n1≥n2≥…≥nk,k≥1.

我们将这样的一种表示称为正整数 n 的一种划分.

现在给定一个正整数 n, 请你求出 n 共有多少种不同的划分方法.

**方法一:完全背包**

`f[i][j]`表示只从1~i中选, 且总和等于j的方案数

![整数划分-优化前.jpg](https://www.rearwaves.com/usr/assets/algorithm/dynamic/42937_8ba34a42de-整数划分-优化前.jpg)

优化:

`f[i][j] = f[i-1][j] + f[i-1][j-i] + f[i-1][j-2i] + ... + f[i-1][j-si]`

`f[i][j-i] =           f[i-1][j-i] + f[i-1][j-2i] + ... + f[i-1][j-si]`

替换: `f[i][j] = f[i-1][j] + f[i][j-1]`

优化一维: `f[j] = f[j] + f[j-i]`

**方法二:计数类DP**

`f[i][j]`表示总和为i, 总个数为j的方案数

![计数类DP.jpg](https://www.rearwaves.com/usr/assets/algorithm/dynamic/42937_d5f9941cde-计数类DP.jpg)

# 5 数位统计dp

### [338. 计数问题](https://www.acwing.com/problem/content/340/)

给定两个整数 a 和 b, 求 a 和 b 之间的所有数字中 0∼9 的出现次数.

例如, a=1024, b=1032, 则 a 和 b 之间共有 9 个数如下:

```
1024 1025 1026 1027 1028 1029 1030 1031 1032
```

其中 `0` 出现 10 次, `1` 出现 10 次, `2` 出现 7 次, `3` 出现 3 次等等…

**解题思路: **分类讨论

然后每一位上都是这么讨论的, 最后累加起来就是总共出现的次数, 这样就是求出来了[1,n]的. 然后如果我想求[l,r]的用一下前缀和就搞定了.

**特殊情况:**

1) x在第1位上出现的次数(不用考虑前半段):
   
   bcdefg∈[00000,bcdefg] , ans += bcdefg+1.

3) 如果我们枚举的数是0的话 :
   0不能在第一位 , 而且枚举到的这一位前面不能全是0, 即xxx∈[001,abc-1].

**其他写法: **

# 6 状态压缩DP

### [291. 蒙德里安的梦想](https://www.acwing.com/problem/content/293/)

求把 N×M 的棋盘分割成若干个 1×2 的长方形, 有多少种方案.

例如当 N=2, M=4 时, 共有 5 种方案. 当 N=2, M=3 时, 共有 3 种方案.

如下图所示:

![2411_1.jpg](https://www.rearwaves.com/usr/assets/algorithm/dynamic/19_4dd1644c20-2411_1.jpg)

输入格式: 每组测试用例占一行, 包含两个整数 N 和 M. 当输入用例 N=0, M=0 时, 表示输入终止, 且该用例无需处理.

**解题思路: **

摆放方块的时候, 先放横着的, 再放竖着的. 总方案数等于只放横着的小方块的合法方案数.

如何判断, 当前方案数是否合法？ 所有剩余位置能否填充满竖着的小方块. 可以按列来看, 每一列内部所有连续的空着的小方块需要是偶数个.

它对应的方案数是 `f[i−1,k]`, 即前i-2列都已摆完, 且从第i-2列伸到第i-1列的状态为 k 的所有方案数.

**时间复杂度:** dp的时间复杂度 =状态表示× 状态转移

状态表示 `f[i][j]` 第一维i可取11, 第二维j(二进制数)可取2^11^ , 所以状态表示 11×2^11^, 状态转移 也是2^11^.

所以总的时间复杂度$11×2^{11}×2^{11}≈4×10^7$, 可以过.

`f[m][n]`中n理解为从m列伸出去的状态更合理. `f[m][0]`时, 表示当摆到m列满列并没有伸出去的状态时, 就是最多方案数了.

```c++
const int N = 12, M = 1 << N;
int n, m;
LL f[N][M];
bool st[N];

### [91. 最短Hamilton路径](https://www.acwing.com/problem/content/93/)

给定一张 n 个点的带权无向图, 点从 0∼n−1 标号, 求起点 0 到终点 n−1 的最短 Hamilton 路径.

Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次.

**解题思路: **

- case 1: 0→1→2→**3→4**;
- case 2: 0→1→3→2→4;
- case 3: 0→2→1→**3→4**;
- case 4: 0→2→3→1→4;
- case 5: 0→3→1→2→4;
- case 6: 0→3→2→1→4;

状态表示: `f[state][j]`. 其中 state 是一个二进制数, 表示点集的方法如上述所示.

- 集合: 经过的点集为 state, 且当前到了点 j 上的所有路径.
- 属性: 路径总长度的最小值

所有状态转移完后, 根据 `f[state][j]` 的定义, 要输出 `f[111⋯11(n个1)][n−1]`.

**时间复杂度:**

枚举所有 state 的时间复杂度是 O(2^n^), 枚举 j 的时间复杂读是 O(n), 枚举 k 的时间复杂度是 O(n), 所以总的时间复杂度是 O(n^2^2^n^).

```c++
const int N = 20, M = 1 << N;
int n;
int w[N][N];
int f[M][N];

# 7 树形DP

### [285. 没有上司的舞会](https://www.acwing.com/problem/content/287/)

**解题思路: ** O(n)

状态表示: `f[u][1]`表示以`u`为根节点的子树并且包括u的总快乐指数, `f[u][0]`表示以`u`为根节点并且不包括u的总快乐指数.

状态计算: 要想求得一棵以`u`为根节点的子树的最大指数分为两种: 选`u`节点或不选`u`节点记点u的子节点是j.

1. 选`u`, $f[u][1]+=Σf[j][0]$;
2. 不选`u`, $f[u][0]+=Σmax(f[j][1],f[j][0])$.

记根节点为`root`, 从`root`开始`dfs`一遍即可, 最后输出$max(f[root][1],f[root][0])$.

# 8 记忆化搜索

### [901. 滑雪](https://www.acwing.com/problem/content/903/)

给定一个 R 行 C 列的矩阵, 表示一个矩形网格滑雪场. 矩阵中第 i 行第 j 列的点表示滑雪场的第 i 行第 j 列区域的高度.

下面给出一个矩阵作为例子:

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

在给定矩阵中, 一条可行的滑行轨迹为 24−17−2−1. 在给定矩阵中, 最长的滑行轨迹为 25−24−23−…−3−2−1, 沿途共经过 25 个区域.

现在给定你一个二维矩阵表示滑雪场各区域的高度, 请你找出在该滑雪场中能够完成的最长滑雪轨迹, 并输出其长度(可经过最大区域数).

**解题思路: **O(n^2^)

状态表示:

- 集合: 所有从(i,j)这个点开始滑的路径长度;
- 属性: max.

状态计算: 就是搜索, 每个点能不能向上下左右动, 下面代码中的`f[x][y] = max(f[x][y],dp(a,b)+1)`; 实际上就是向四个方向判断之后转移:

- `f[i][j] = max(f[i][j],f[i-1][j]+1)`;//上
- `f[i][j] = max(f[i][j],f[i+1][j]+1)`;//下
- `f[i][j] = max(f[i][j],f[i][j-1]+1)`;//左
- `f[i][j] = max(f[i][j],f[i][j+1]+1)`;//右

2 条评论

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

动态规划基础

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款