C***U
发帖数: 2406 | 1 假设我有一个正整数n，我要把他写成一些正整数的和。是组合问题，也就是说数字的
顺序不考虑。
有什么好的办法没有
我写了一个recrusive的，请大牛们指教一下
int count = 0;
//构造以max为最大数的 number的partition
void partitionWithMax(int number, int max) {
if(!number) {
count++;
return;
}
else {
int newMax = number > max ? max : number;
for(int i = newMax; i > 0; i--) {
partitionWithMax(number - i, i);
}
}
}
//让max从1到number都走一边
void partition(int number) {
for(int i = number; i > 0; i--) {
partitionWithMax(number - i, i);
}
} |
C***U
发帖数: 2406 | 2 没人搭理我。。。
【在 C***U 的大作中提到】
: 假设我有一个正整数n，我要把他写成一些正整数的和。是组合问题，也就是说数字的
: 顺序不考虑。
: 有什么好的办法没有
: 我写了一个recrusive的，请大牛们指教一下
: int count = 0;
: //构造以max为最大数的 number的partition
: void partitionWithMax(int number, int max) {
: if(!number) {
: count++;
: return;
|
Z*****Z
发帖数: 723 | 3 没看懂题。。。
【在 C***U 的大作中提到】
: 没人搭理我。。。
|
C***U
发帖数: 2406 | 4 例子
4的partition是如下几个
4
3+1
2+2
2+1+1
1+1+1+1
【在 Z*****Z 的大作中提到】
: 没看懂题。。。
|
p*****2
发帖数: 21240 | |
C***U
发帖数: 2406 | 6 我这里倒是还打出来了
如果只是count 如何dp
【在 p*****2 的大作中提到】
: 如果只是求count不是用dp就可以了吗？
|
p*****2
发帖数: 21240 | 7
每看到你的程序打印呀
【在 C***U 的大作中提到】
: 我这里倒是还打出来了
: 如果只是count 如何dp
|
d****o
发帖数: 1055 | 8 你这题就是用硬币找零是一道题。
give you 4 coins , 1,5,10, 25 cents, to make change to N cents。
去看那道题就可以了。
【在 C***U 的大作中提到】
: 假设我有一个正整数n，我要把他写成一些正整数的和。是组合问题，也就是说数字的
: 顺序不考虑。
: 有什么好的办法没有
: 我写了一个recrusive的，请大牛们指教一下
: int count = 0;
: //构造以max为最大数的 number的partition
: void partitionWithMax(int number, int max) {
: if(!number) {
: count++;
: return;
|
p*****2
发帖数: 21240 | 9
def count(n):
dp=[[0]*(n+1) for i in xrange(n+1)]
dp[0][0]=1
for i in xrange(1,n+1):
for j in xrange(n+1):
dp[i][j]=dp[i-1][j]
if j>=i:
dp[i][j]+=dp[i][j-i]
return dp[n][n]
【在 C***U 的大作中提到】
: 我这里倒是还打出来了
: 如果只是count 如何dp
|
Z*****Z
发帖数: 723 | 10 拜二爷
【在 p*****2 的大作中提到】
:
: def count(n):
: dp=[[0]*(n+1) for i in xrange(n+1)]
: dp[0][0]=1
:
: for i in xrange(1,n+1):
: for j in xrange(n+1):
: dp[i][j]=dp[i-1][j]
: if j>=i:
: dp[i][j]+=dp[i][j-i]
|
C***U
发帖数: 2406 | 11 哦
我电脑上是打印的。。。在这里 我改掉了。。
就是把return前面 吧数组打印出来就可以了
【在 p*****2 的大作中提到】
:
: def count(n):
: dp=[[0]*(n+1) for i in xrange(n+1)]
: dp[0][0]=1
:
: for i in xrange(1,n+1):
: for j in xrange(n+1):
: dp[i][j]=dp[i-1][j]
: if j>=i:
: dp[i][j]+=dp[i][j-i]
|
