Acwing-基础算法课笔记之动态规划(计数类DP)
- 一、整数划分
- 1、定义
- 2、完全背包的做法
- 代码示例
- (1)过程模拟
- (2)代码示例
- 3、计数类DP的做法
- (1)过程模拟
- (2)闫氏DP分析法
- (3)代码示例
一、整数划分
1、定义
一个正整数 n可以表示成若干个正整数之和,形如:
n = n 1 + n 2 + . . . + n k n=n_1+n_2+...+n_k n=n1+n2+...+nk,其中 n 1 ≥ n 2 ≥ . . . ≥ n k , k ≥ 1 n_1\ge n_2\ge...\ge n_k,k\ge1 n1≥n2≥...≥nk,k≥1
举例:
假设要将 5 5 5划分,以下是划分的情况:
5 = 5 5=5 5=5
5 = 1 + 4 5=1+4 5=1+4
5 = 2 + 3 5=2+3 5=2+3
5 = 1 + 1 + 3 5=1+1+3 5=1+1+3
5 = 1 + 2 + 2 5=1+2+2 5=1+2+2
5 = 1 + 1 + 1 + 2 5=1+1+1+2 5=1+1+1+2
5 = 1 + 1 + 1 + 1 + 1 5=1+1+1+1+1 5=1+1+1+1+1
2、完全背包的做法
状态表示:
d p [ i ] [ j ] dp[i][j] dp[i][j]表示只从 1 ∼ i 1\sim i 1∼i中选,且总和等于 j j j的方案数
状态转移方程:
f [ i ] [ j ] = f [ i − 1 ] [ j ] + f [ i ] [ j − i ] f[i][j]=f[i-1][j]+f[i][j-i] f[i][j]=f[i−1][j]+f[i][j−i]
其中 f [ i − 1 ] [ j ] f[i-1][j] f[i−1][j]指的是当物品装不进背包时,前 i − 1 i-1 i−1个物品当中最大价值, f [ i ] [ j − i ] f[i][j-i] f[i][j−i]指的是装的下的情况。(此为个人理解,如果有不对的地方请纠正错误)
代码示例
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int dp[N];
int mod = 1e9 + 7;
int main() {scanf("%d", &n);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {dp[j] = (dp[j] + dp[j - i]) % mod;}}printf("%d", dp[n]);return 0;
}
(1)过程模拟
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 1 | 1 | 1 | 1 | 1 | 1 |
2 | 1 | 0 | 2 | 2 | 3 | 3 |
3 | 1 | 0 | 0 | 3 | 4 | 5 |
4 | 1 | 0 | 0 | 0 | 5 | 6 |
5 | 1 | 0 | 0 | 0 | 0 | 7 |
上表中,列表示的是最终和的值,行表示和值最多由 j j j个数相加, d p [ i ] [ j ] dp[i][j] dp[i][j]则是表示的是方案个数。
(2)代码示例
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int dp[N];
int mod = 1e9 + 7;
int main() {scanf("%d", &n);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = i; j <= n; j++) {dp[j] = (dp[j] + dp[j - i]) % mod;}}printf("%d", dp[n]);return 0;
}
3、计数类DP的做法
(1)过程模拟
0 | 1 | 2 | 3 | 4 | 5 | |
---|---|---|---|---|---|---|
0 | 1 | 0 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 |
2 | 0 | 1 | 1 | 0 | 0 | 0 |
3 | 0 | 1 | 1 | 1 | 0 | 0 |
4 | 0 | 1 | 2 | 1 | 1 | 0 |
5 | 0 | 1 | 2 | 2 | 1 | 1 |
上表中,列表示的是总和 i i i,行表示有 j j j个数相加, d p [ i ] [ j ] dp[i][j] dp[i][j]则是表示的是有 j j j个数相加构成 i i i的数量。
(2)闫氏DP分析法
(3)代码示例
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 1010;
int n;
int dp[N][N];
int mod = 1e9 + 7;
int main() {scanf("%d", &n);dp[0][0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i][j] = (dp[i - 1][j - 1] + dp[i - j][j]) % mod;}}int ans = 0;for (int i = 1; i <= n; i++)ans = (ans + dp[n][i]) % mod;printf("%d", ans);return 0;
}