整数划分问题是把一个正整数 N 拆分成一组数，并且使这组数相加等于 N 的问题.
比如:
6
5 + 1
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
这里，5+1和1+5是同一种分法。
这里探讨整数划分的可行解的数目。
问题求解：
首先假设正整数n拆分成k个数(不允许有0)，用f(n,k)表示正整数n拆分成k个数的可行拆分种类的数目。
那么
f(n,n)表示n拆分成n个数(即只有n个1)，显然f(n,n) = 1
然后，可以按照这k份中是否有一份的数为1分成两类：
1) 这k份中没有1份含1的：那么可以在n中拿出k个"1"出来，分到k份中，再将剩下n-k分到k份中，于是这时有
f(n,k) = f(n-k,k)
2) 这k份中至少有一份含有1：首先在n中拿1个"1"出来，再将剩下n-1分到k-1份中，于是这时有：f(n,k) = f(n-1,k-1)
综合起来就是：
f(n,n) = 1
f(n,k) = f(n-k,k) + f(n-1,k-1)
这两个递归式可以使用动态规划求解。
题目链接：
http://poj.org/problem?id=1283题解：直接按照整数划分来解
代码：
import java.util.Scanner;
import java.util.Arrays;;
public class Main
{
private static long [][]dp = new long[205][205];
private static long Test(int _n,int _k)
{
if(_n < _k)
return 0;
for(int i = 0; i <= _n; ++i)
Arrays.fill(dp[i],0);
for(int i = 1; i <= _n; ++i)
{
dp[i][i] = 1;
}
for(int i = 2; i <= _n; ++i)
{
for(int j = 1; j <= _k; ++j)
{
dp[i][j] = dp[i-1][j-1];
if(i - j > 0)
dp[i][j] += dp[i-j][j];
}
}
return dp[_n][_k];
}
public static void main(String[] args)
{
int n,k;
Scanner in = new Scanner(System.in);
n = in.nextInt();
k = in.nextInt();
while(!(n == 0 && k == 0))
{
System.out.println(Test(n,k));
n = in.nextInt();
k = in.nextInt();
}
}
}
题解：这题允许存在空盘，怎么做呢？换一种思路，我们先给每个盘子放上一个"1"，那么当这个盘子为1时，表示为空，于是答案便是f(n+m,n)
代码：
import java.util.Scanner;
import java.util.Arrays;
public class Main
{
private static long [][]dp = new long[32][32];
private static long Test(int _n,int _k)
{
if(_n < _k)
return 0;
for(int i = 0; i <= _n; ++i)
Arrays.fill(dp[i],0);
for(int i = 1; i <= _n; ++i)
{
dp[i][i] = 1;
}
for(int i = 2; i <= _n; ++i)
{
for(int j = 1; j <= _k; ++j)
{
dp[i][j] = dp[i-1][j-1];
if(i - j > 0)
dp[i][j] += dp[i-j][j];
}
}
return dp[_n][_k];
}
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int testcase = in.nextInt();
int m,n;
for(int i =0; i < testcase; ++i)
{
m = in.nextInt();
n = in.nextInt();
System.out.println(Test(m+n,n));
}
}
}
posted on 2011-03-28 18:42
bennycen 阅读(1166)
评论(1) 编辑 收藏 引用