洛谷 - P1025 数的划分(计数dp)

题目链接：点击查看

题目大意：将整数 n 分成 k 份有多少种分法

题目分析：设 dp[ i ][ j ] 为将整数 i 分成 j 份的方案数，拆分整数可以等价为放小球，相当于将 n 个小球放进 k 个盒子，最后必须保证没有空盒子的方案数，则可以其转换为两个子问题之和：

至少存在着一个盒子只有一个小球的方案数

所有盒子中的小球都大于一的方案数

上述情况一等价于 dp[ i - 1 ][ j - 1 ]，而上述情况二等价于，从每个盒子中都取出一个小球，最后将 i - j 个小球放入 j 个小球的方案数，也就是 dp[ i - j ][ j ]

所以 dp[ i ][ j ] = dp[ i - 1 ][ j - 1 ] + dp[ i - j ][ j ]

初始化的话，显然 dp[ i ][ 1 ] = 1，因为如果只有一个盒子的话，显然只有一种方法

代码：
 

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=210;LL dp[N][N];int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)dp[i][1]=1;for(int i=2;i<=n;i++)for(int j=2;j<=m;j++)dp[i][j]=dp[i-1][j-1]+dp[i-j][j];printf("%lld\n",dp[n][m]);return 0; }

 

总结

以上是生活随笔为你收集整理的洛谷 - P1025 数的划分(计数dp)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。