概念
状态记录数量的DP。
对就是这么朴实无华。
例题
AcWing900-整数划分
方案一
基础版
首先设计状态：f[i][j]表示在从1~i的数字中能够组成j的组合数。
状态转移：根据选择几个（令为k）第i个数，可以直接转换：
f[i][j]+=f[i-1][j-k*i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3,mod=1e9+7;
int n;
int f[N][N];
int main(){
cin.tie(0);
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=n;j++){
for(int k=0;i*k<=j;k++){
f[i][j]+=f[i-1][j-k*i];
f[i][j]%=mod;
}
}
}
cout<<f[n][n];
return 0;
}
|
优化版
还记得完全背包怎么优化不？
计数DP和完全背包算法是不是很像？
那就对了，所以我们就照着那个思想优化即可。
完全背包优化
f[i][j]=f[i-1][j]+f[i-1][j-i]+f[i-1][j-i2]+…+f[i-1][j-ik]
f[i][j-i]=f[i-1][j-1]+f[i-1][j-i2]+…+f[i-1][j-ik]
f[i][j-i2]=f[i-1][j-i2]+…+f[i-1][j-i*k]
所以就不用我多说了吧。
注：如果您光看优化版代码，如果您没有学过，如果您不是神童，您多半看不懂~
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3,mod=1e9+7;
int n;
int f[N];
int main(){
cin.tie(0);
cin>>n;
f[0]=1;
for(int i=1;i<=n;i++){
for(int j=i;j<=n;j++){
f[j]+=f[j-i];
f[j]%=mod;
}
}
cout<<f[n];
return 0;
}
|
方案二
f[i][j]表示所有总和是i并恰好表示成j个数之和的方案个数。
状态转移时可以分成两种情况：方案中最小数是1的方案和方案中最小数大于1的方案。
它们分别是f[i-1][j-1]与f[i-j][j]
- f[i-1][j-1]：把1去掉的情况
- f[i-j][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
| #include<bits/stdc++.h>
using namespace std;
const int N=1e3+3,mod=1e9+7;
int n;
int ans;
int f[N][N];
int main(){
cin.tie(0);
cin>>n;
f[0][0]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
f[i][j]=(f[i-1][j-1]+f[i-j][j])%mod;
}
}
for(int i=1;i<=n;i++){
ans+=f[n][i];
ans%=mod;
}
cout<<ans;
return 0;
}
|
完结撒花o(￣︶￣)o