NYOJ 176 整数划分（二）

本文主要是介绍NYOJ 176 整数划分（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

整数划分（二）
时间限制：1000 ms | 内存限制：65535 KB
难度：3
描述
把一个正整数m分成n个正整数的和，有多少种分法？

例：把5分成3个正正数的和，有两种分法：

1 1 3

1 2 2

输入
第一行是一个整数T表示共有T组测试数据(T<=50)
每组测试数据都是两个正整数m,n，其中(1<=n<=m<=100),分别表示要拆分的正数和拆分的正整数的个数。
输出
输出拆分的方法的数目。
样例输入
2
5 2
5 3
样例输出
2

2

 

用动态dp[i][j]表示i划分为不超过j个数的划分数，则n划分为m个的划分数就是dp[n][m]-dp[n][m-1];

动态规划方程为：dp[i][j]=dp[i][j-1]+dp[i-j][j](记得如果i-j<j,则dp[i-j][j]=dp[i-j][i-j])

 

AC代码：

 

 

# include <cstdio>
# include <cstring>
using namespace std;
typedef long long int LL;
LL dp[110][110];
const int maxn=100;
int main(){int n, i, j, k, t, m;memset(dp, 0, sizeof(dp));dp[1][1]=1;dp[0][0]=1;for(i=2; i<=maxn; i++){for(j=1; j<=i; j++){if(i-j<j){dp[i][j]=dp[i-j][i-j]+dp[i][j-1];}else{dp[i][j]=dp[i-j][j]+dp[i][j-1];}}}scanf("%d", &t);for(i=1; i<=t; i++){scanf("%d%d", &n, &m);printf("%lld\n", dp[n][m]-dp[n][m-1]);}return 0;
}

 

 

 

 

 

这篇关于NYOJ 176 整数划分（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---