【计数dp】P1025 划分数 dp or dfs
首先划分数算是计数dp的一个题型叭,先从《挑战》上讲起
挑战上划分可以为0
dp[i][j]代表j的i划分
- 每种划分都大于1 dp[i][j-i]
- 至少存在一种划分为0 dp[i-1][j]
dp[i][j]=dp[i][j-i]+dp[i-1][j]
若是划分成正整数
- 每种划分都大于1 dp[i][j-i]
- 至少存在一种划分为1 dp[i-1][j-1]
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k;
int dp[10][210]; //dp[i][j] j的i划分
int main()
{
cin>>n>>k;
dp[0][0]=1;
for(int i=1;i<=k;++i)
for(int j=0;j<=n;++j)
{
if(j-i>=0)
dp[i][j]=dp[i-1][j-1]+dp[i][j-i]; //每份不能为空
else
dp[i][j]=dp[i-1][j-1];
}
cout<<dp[k][n]<<endl;
}
拿到这道题的第一想法其实是dfs,dfs会比dp慢不少
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,k;
int cnt=0;
void dfs(int sum,int last,int layer)
{
if(layer==k)
{
if(sum==n)
{
++cnt;
}
return ;
}
for(int i=last;i<=n-sum;++i)
{
if(sum+(k-layer)*i>n) return ;
dfs(sum+i,i,layer+1); //把第一组数套进去想层数是不是给错了,比如一开始是(0+1,1,第一层)
}
}
int main()
{
cin>>n>>k;
dfs(0,1,0);
cout<<cnt<<endl;
}