一道题：number of permutation是 for a total score - 未名空间MITBBS历史存档

一道题：number of permutation是 for a total score# JobHunting - 待字闺中

k*t2012-01-31 08:01

1 楼

S=max score
individual points p1,p2,...,pn
how many permutations of p1,...,pn (multiple occurences of px allowed) give
us total score S.
This is essentially based on American football, where each drive can end in
2 points (safety), 3 points (field goal), 6 points (td) or 7 points (td+fg).
Example:
S=47
p1=2,p2=4,p3=7
Answer: 226234 permutations
3,3,3,3,7,7,7,7,7,:(126 permutations)
3,3,3,3,3,3,3,3,3,3,3,7,7,:(78 permutations)
2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,:(16 permutations)
2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,:(2380 permutations)
2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,:(31824 permutations)
2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,:(92378 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,:(77520 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,:(20349 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,:(1540 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,:(23 permutations)
Count = 226234

p*22012-01-31 08:01

2 楼

这不是DP吗？
int MaxCount(int S)
{
if(S<0)
return 0;
if(S==0)
return 1;
int count=0;
for(int i=0;i{
count+=(S-p[i]);
}
}

l*y2012-01-31 08:01

3 楼

有难度，好像DP没那么简单。
dp[2]=1,dp[3]=1;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;
你那样dp[47]算出来是9768761

p*22012-01-31 08:01

4 楼

我算了一下，的出来是271405，不是9768761呀。

【在 l*********y 的大作中提到】

: 有难度，好像DP没那么简单。
: dp[2]=1,dp[3]=1;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;
: 你那样dp[47]算出来是9768761

k*t2012-01-31 08:01

5 楼

我也算了个271405。不过你贴得code好像不全吧。
发信人: peking2 (myfacebook), 信区: JobHunting
标题: Re: 一道题：number of permutation是 for a total score
发信站: BBS 未名空间站 (Tue Jan 31 06:43:11 2012, 美东)
这不是DP吗？
int MaxCount(int S)
{
if(S<0)
    return 0;
if(S==0)
    return 1;
int count=0;
for(int i=0;i {
    count+=(S-p[i]);
}
}

p*22012-01-31 08:01

6 楼

是不全。我只是随手写个算法。你知道差在哪里了吗？

【在 k***t 的大作中提到】

: 我也算了个271405。不过你贴得code好像不全吧。
: 发信人: peking2 (myfacebook), 信区: JobHunting
: 标题: Re: 一道题：number of permutation是 for a total score
: 发信站: BBS 未名空间站 (Tue Jan 31 06:43:11 2012, 美东)
: 这不是DP吗？
: int MaxCount(int S)
: {
: if(S<0)
: return 0;
: if(S==0)

b*e2012-01-31 08:01

7 楼

int MaxCount(int S)
{
if(S<0 || S==1)
return 0;
if(S==0)
return 1;
int count=0;
for(int i=0;i{
count+=MaxCount(S-p[i]);
}
return count;
}

k*t2012-01-31 08:01

8 楼

赞。
随手写得几行和我洋洋洒洒写得一大段结果一致！
几点交流。
0。存一个S维的maxCount数组，就可以变成DP。
1。S==1 的判断不必要吧，也不通用。
2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

【在 b*****e 的大作中提到】

: int MaxCount(int S)
: {
: if(S<0 || S==1)
: return 0;
: if(S==0)
: return 1;
: int count=0;
: for(int i=0;i: {
: count+=MaxCount(S-p[i]);

p*22012-01-31 08:01

9 楼

一定要用DP的。我的代码没写。可以数组或hashtable.
s==1没必要,我的代码没有这个吧？
如果不只正整数的话，确实就不通用了。但是就没法收敛了呀？那不就无穷解了吗？

【在 k***t 的大作中提到】

: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

h*n2012-01-31 08:01

10 楼

能稍微解释下你的code吗？没看明白

【在 b*****e 的大作中提到】

: int MaxCount(int S)
: {
: if(S<0 || S==1)
: return 0;
: if(S==0)
: return 1;
: int count=0;
: for(int i=0;i: {
: count+=MaxCount(S-p[i]);

p*22012-01-31 08:01

11 楼

就是DP。

【在 h****n 的大作中提到】

: 能稍微解释下你的code吗？没看明白

h*n2012-01-31 08:01

12 楼

那code里面的P数组是怎么初始化的？
比如题目中的例子，难道数组p就三个元素？？
太笨了，求大牛指教

h*n2012-01-31 08:01

13 楼

那code里面的P数组是怎么初始化的？
比如题目中的例子，难道数组p就三个元素？？
太笨了，求大牛指教

z*n2012-01-31 08:01

14 楼

和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
走法走N步楼梯" 的DP题目是类似的

p*22012-01-31 08:01

15 楼

数组可以当参数传进来。也可以定义成类的成员。这个倒不重要。

【在 h****n 的大作中提到】

: 那code里面的P数组是怎么初始化的？
: 比如题目中的例子，难道数组p就三个元素？？
: 太笨了，求大牛指教

h*n2012-01-31 08:01

16 楼

赞这个，突然焕然大悟了一下。。

【在 z*****n 的大作中提到】

: 和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
: 走法走N步楼梯" 的DP题目是类似的

c*e2012-01-31 08:01

17 楼

如果用2，4，7，得到271405.
如果用2，3，7，得到1540427.

【在 p*****2 的大作中提到】

:
: 数组可以当参数传进来。也可以定义成类的成员。这个倒不重要。

c*e2012-01-31 08:01

18 楼

完整程序（C++）：
#include
#include
#include
using namespace std;
long maxCount(int s, int p[], int n) {
long* count = new long[s+1];
count[0]=1;
for(int i=1;i<=s;i++) {
count[i]=0;
for(int j=0;jif(i-p[j]>=0) count[i]+= count[i-p[j]];
}
}
return count[s];
}
int main() {
int x[3];
x[0]=2;
x[1]=3;
x[2]=7;
cout << maxCount(47,x,3) << endl;
return 0;
}

c*e2012-01-31 08:01

19 楼

S=1的判断不但不必要，而且可以是个错误。
if p[0]=1, then S!=0.

【在 k***t 的大作中提到】

: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

c*e2012-01-31 08:01

20 楼

If you use 2,3,7, your answer is not complete.
You can also have 2,3,7,7,7,7,7,7.

3,3,3,3,7,7,7,7,7,:(126 permutations)
3,3,3,3,3,3,3,3,3,3,3,7,7,:(78 permutations)
2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,:(16 permutations)
2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,:(2380 permutations)

【在 k***t 的大作中提到】

: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

k*t2012-01-31 08:01

21 楼

S=max score
individual points p1,p2,...,pn
how many permutations of p1,...,pn (multiple occurences of px allowed) give
us total score S.
This is essentially based on American football, where each drive can end in
2 points (safety), 3 points (field goal), 6 points (td) or 7 points (td+fg).
Example:
S=47
p1=2,p2=4,p3=7
Answer: 226234 permutations
3,3,3,3,7,7,7,7,7,:(126 permutations)
3,3,3,3,3,3,3,3,3,3,3,7,7,:(78 permutations)
2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,:(16 permutations)
2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,:(2380 permutations)
2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,:(31824 permutations)
2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,:(92378 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,:(77520 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,:(20349 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,3,3,:(1540 permutations)
2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,3,:(23 permutations)
Count = 226234

p*22012-01-31 08:01

22 楼

这不是DP吗？
int MaxCount(int S)
{
if(S<0)
return 0;
if(S==0)
return 1;
int count=0;
for(int i=0;i{
count+=(S-p[i]);
}
}

l*y2012-01-31 08:01

23 楼

有难度，好像DP没那么简单。
dp[2]=1,dp[3]=1;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;
你那样dp[47]算出来是9768761

p*22012-01-31 08:01

24 楼

我算了一下，的出来是271405，不是9768761呀。

【在 l*********y 的大作中提到】

: 有难度，好像DP没那么简单。
: dp[2]=1,dp[3]=1;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;
: 你那样dp[47]算出来是9768761

k*t2012-01-31 08:01

25 楼

我也算了个271405。不过你贴得code好像不全吧。
发信人: peking2 (myfacebook), 信区: JobHunting
标题: Re: 一道题：number of permutation是 for a total score
发信站: BBS 未名空间站 (Tue Jan 31 06:43:11 2012, 美东)
这不是DP吗？
int MaxCount(int S)
{
if(S<0)
    return 0;
if(S==0)
    return 1;
int count=0;
for(int i=0;i {
    count+=(S-p[i]);
}
}

p*22012-01-31 08:01

26 楼

是不全。我只是随手写个算法。你知道差在哪里了吗？

【在 k***t 的大作中提到】

: 我也算了个271405。不过你贴得code好像不全吧。
: 发信人: peking2 (myfacebook), 信区: JobHunting
: 标题: Re: 一道题：number of permutation是 for a total score
: 发信站: BBS 未名空间站 (Tue Jan 31 06:43:11 2012, 美东)
: 这不是DP吗？
: int MaxCount(int S)
: {
: if(S<0)
: return 0;
: if(S==0)

b*e2012-01-31 08:01

27 楼

int MaxCount(int S)
{
if(S<0 || S==1)
return 0;
if(S==0)
return 1;
int count=0;
for(int i=0;i{
count+=MaxCount(S-p[i]);
}
return count;
}

k*t2012-01-31 08:01

28 楼

赞。
随手写得几行和我洋洋洒洒写得一大段结果一致！
几点交流。
0。存一个S维的maxCount数组，就可以变成DP。
1。S==1 的判断不必要吧，也不通用。
2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

【在 b*****e 的大作中提到】

: int MaxCount(int S)
: {
: if(S<0 || S==1)
: return 0;
: if(S==0)
: return 1;
: int count=0;
: for(int i=0;i: {
: count+=MaxCount(S-p[i]);

p*22012-01-31 08:01

29 楼

一定要用DP的。我的代码没写。可以数组或hashtable.
s==1没必要,我的代码没有这个吧？
如果不只正整数的话，确实就不通用了。但是就没法收敛了呀？那不就无穷解了吗？

【在 k***t 的大作中提到】

: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

h*n2012-01-31 08:01

30 楼

能稍微解释下你的code吗？没看明白

【在 b*****e 的大作中提到】

: int MaxCount(int S)
: {
: if(S<0 || S==1)
: return 0;
: if(S==0)
: return 1;
: int count=0;
: for(int i=0;i: {
: count+=MaxCount(S-p[i]);

p*22012-01-31 08:01

31 楼

就是DP。

【在 h****n 的大作中提到】

: 能稍微解释下你的code吗？没看明白

h*n2012-01-31 08:01

32 楼

那code里面的P数组是怎么初始化的？
比如题目中的例子，难道数组p就三个元素？？
太笨了，求大牛指教

z*n2012-01-31 08:01

33 楼

和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
走法走N步楼梯" 的DP题目是类似的

p*22012-01-31 08:01

34 楼

数组可以当参数传进来。也可以定义成类的成员。这个倒不重要。

【在 h****n 的大作中提到】

: 那code里面的P数组是怎么初始化的？
: 比如题目中的例子，难道数组p就三个元素？？
: 太笨了，求大牛指教

h*n2012-01-31 08:01

35 楼

赞这个，突然焕然大悟了一下。。

【在 z*****n 的大作中提到】

: 和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
: 走法走N步楼梯" 的DP题目是类似的

c*e2012-01-31 08:01

36 楼

如果用2，4，7，得到271405.
如果用2，3，7，得到1540427.

【在 p*****2 的大作中提到】

:
: 数组可以当参数传进来。也可以定义成类的成员。这个倒不重要。

c*e2012-01-31 08:01

37 楼

完整程序（C++）：
#include
#include
#include
using namespace std;
long maxCount(int s, int p[], int n) {
long* count = new long[s+1];
count[0]=1;
for(int i=1;i<=s;i++) {
count[i]=0;
for(int j=0;jif(i-p[j]>=0) count[i]+= count[i-p[j]];
}
}
return count[s];
}
int main() {
int x[3];
x[0]=2;
x[1]=3;
x[2]=7;
cout << maxCount(47,x,3) << endl;
return 0;
}

c*e2012-01-31 08:01

38 楼

S=1的判断不但不必要，而且可以是个错误。
if p[0]=1, then S!=0.

【在 k***t 的大作中提到】

: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

c*e2012-01-31 08:01

39 楼

If you use 2,3,7, your answer is not complete.
You can also have 2,3,7,7,7,7,7,7.

3,3,3,3,7,7,7,7,7,:(126 permutations)
3,3,3,3,3,3,3,3,3,3,3,7,7,:(78 permutations)
2,3,3,3,3,3,3,3,3,3,3,3,3,3,3,3,:(16 permutations)
2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,3,3,:(2380 permutations)

【在 k***t 的大作中提到】

: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。

h*g2012-01-31 08:01

40 楼

这题要是求combination 的话， dp 还能解码？

【在 c**********e 的大作中提到】

: 完整程序（C++）：
: #include
: #include
: #include
: using namespace std;
: long maxCount(int s, int p[], int n) {
: long* count = new long[s+1];
: count[0]=1;
: for(int i=1;i<=s;i++) {
: count[i]=0;

y*n2012-01-31 08:01

41 楼

我用另外一种解法，也得到同样的结果。
原题中数据有误，很多种组合都没有展示出来。

【在 c**********e 的大作中提到】

: 如果用2，4，7，得到271405.
: 如果用2，3，7，得到1540427.