由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字 访问原贴
JobHunting版 - 一道题：number of permutation是 for a total score
相关主题
● 请教一道题● 谈G家面经
● Facebook intern 电话面经● 上一道题吧
● 请教一道题● nvidia面试题
● Leetcode上面的题Max Points on a Line● 分享下G家第一个phone interview的题目
● amazon 一道题● 贡献A 家online assement
● 再来一道题● 报个微软的Offer
● counting problem● 问几个老算法题的最佳解法
● 回馈本版，发个cisco面经● 一道面试题
相关话题的讨论汇总
话题: int话题: count话题: maxcount话题: dp
进入JobHunting版参与讨论
1 (共1页)
k***t
发帖数: 276
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*****2
发帖数: 21240
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*********y
发帖数: 370
3
有难度，好像DP没那么简单。
dp[2]=1,dp[3]=1;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;
你那样dp[47]算出来是9768761
p*****2
发帖数: 21240
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***t
发帖数: 276
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*****2
发帖数: 21240
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*****e
发帖数: 131
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***t
发帖数: 276
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*****2
发帖数: 21240
9
一定要用DP的。我的代码没写。可以数组或hashtable.
s==1没必要,我的代码没有这个吧？
如果不只正整数的话，确实就不通用了。但是就没法收敛了呀？那不就无穷解了吗？

【在 k***t 的大作中提到】
: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。
h****n
发帖数: 1093
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]);
相关主题
● 再来一道题● 谈G家面经
● counting problem● 上一道题吧
● 回馈本版，发个cisco面经● nvidia面试题
进入JobHunting版参与讨论
p*****2
发帖数: 21240
11

就是DP。

【在 h****n 的大作中提到】
: 能稍微解释下你的code吗？没看明白
h****n
发帖数: 1093
12
那code里面的P数组是怎么初始化的？
比如题目中的例子，难道数组p就三个元素？？
太笨了，求大牛指教
h****n
发帖数: 1093
13
那code里面的P数组是怎么初始化的？
比如题目中的例子，难道数组p就三个元素？？
太笨了，求大牛指教
z*****n
发帖数: 447
14
和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
走法走N步楼梯" 的DP题目是类似的
p*****2
发帖数: 21240
15

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

【在 h****n 的大作中提到】
: 那code里面的P数组是怎么初始化的？
: 比如题目中的例子，难道数组p就三个元素？？
: 太笨了，求大牛指教
h****n
发帖数: 1093
16
赞这个，突然焕然大悟了一下。。

【在 z*****n 的大作中提到】
: 和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
: 走法走N步楼梯" 的DP题目是类似的
c**********e
发帖数: 2007
17
如果用2，4，7，得到271405.
如果用2，3，7，得到1540427.

【在 p*****2 的大作中提到】
:
: 数组可以当参数传进来。也可以定义成类的成员。这个倒不重要。
c**********e
发帖数: 2007
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;j if(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**********e
发帖数: 2007
19

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

【在 k***t 的大作中提到】
: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。
c**********e
发帖数: 2007
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 的判断只适用于正整数，这里只说整数，可能也不太通用。
相关主题
● 分享下G家第一个phone interview的题目● 问几个老算法题的最佳解法
● 贡献A 家online assement● 一道面试题
● 报个微软的Offer● 几道面试题
进入JobHunting版参与讨论
k***t
发帖数: 276
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*****2
发帖数: 21240
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*********y
发帖数: 370
23
有难度，好像DP没那么简单。
dp[2]=1,dp[3]=1;dp[4]=1;dp[5]=2;dp[6]=3;dp[7]=4;
你那样dp[47]算出来是9768761
p*****2
发帖数: 21240
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***t
发帖数: 276
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*****2
发帖数: 21240
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*****e
发帖数: 131
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***t
发帖数: 276
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*****2
发帖数: 21240
29
一定要用DP的。我的代码没写。可以数组或hashtable.
s==1没必要,我的代码没有这个吧？
如果不只正整数的话，确实就不通用了。但是就没法收敛了呀？那不就无穷解了吗？

【在 k***t 的大作中提到】
: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。
h****n
发帖数: 1093
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]);
相关主题
● amazon phone interview questions● Facebook intern 电话面经
● 菜鸟求救 请大家看看我的代码有没有问题● 请教一道题
● 请教一道题● Leetcode上面的题Max Points on a Line
进入JobHunting版参与讨论
p*****2
发帖数: 21240
31

就是DP。

【在 h****n 的大作中提到】
: 能稍微解释下你的code吗？没看明白
h****n
发帖数: 1093
32
那code里面的P数组是怎么初始化的？
比如题目中的例子，难道数组p就三个元素？？
太笨了，求大牛指教
z*****n
发帖数: 447
33
和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
走法走N步楼梯" 的DP题目是类似的
p*****2
发帖数: 21240
34

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

【在 h****n 的大作中提到】
: 那code里面的P数组是怎么初始化的？
: 比如题目中的例子，难道数组p就三个元素？？
: 太笨了，求大牛指教
h****n
发帖数: 1093
35
赞这个，突然焕然大悟了一下。。

【在 z*****n 的大作中提到】
: 和Cracking the Code Interview上，那道" 每次可以走1，2或者3步，求一共有多少种
: 走法走N步楼梯" 的DP题目是类似的
c**********e
发帖数: 2007
36
如果用2，4，7，得到271405.
如果用2，3，7，得到1540427.

【在 p*****2 的大作中提到】
:
: 数组可以当参数传进来。也可以定义成类的成员。这个倒不重要。
c**********e
发帖数: 2007
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;j if(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**********e
发帖数: 2007
38

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

【在 k***t 的大作中提到】
: 赞。
: 随手写得几行和我洋洋洒洒写得一大段结果一致！
: 几点交流。
: 0。存一个S维的maxCount数组，就可以变成DP。
: 1。S==1 的判断不必要吧，也不通用。
: 2。S<0 的判断只适用于正整数，这里只说整数，可能也不太通用。
c**********e
发帖数: 2007
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*****g
发帖数: 312
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;
相关主题
● Leetcode上面的题Max Points on a Line● counting problem
● amazon 一道题● 回馈本版，发个cisco面经
● 再来一道题● 谈G家面经
进入JobHunting版参与讨论
y****n
发帖数: 743
41
我用另外一种解法，也得到同样的结果。
原题中数据有误，很多种组合都没有展示出来。

【在 c**********e 的大作中提到】
: 如果用2，4，7，得到271405.
: 如果用2，3，7，得到1540427.
1 (共1页)
进入JobHunting版参与讨论
相关主题
● 一道面试题● amazon 一道题
● 几道面试题● 再来一道题
● amazon phone interview questions● counting problem
● 菜鸟求救 请大家看看我的代码有没有问题● 回馈本版，发个cisco面经
● 请教一道题● 谈G家面经
● Facebook intern 电话面经● 上一道题吧
● 请教一道题● nvidia面试题
● Leetcode上面的题Max Points on a Line● 分享下G家第一个phone interview的题目
相关话题的讨论汇总
话题: int话题: count话题: maxcount话题: dp

未名新帖统计// 7月16日

#版面帖数(主题数)
-全站4871 (796)
1Military3777 (569)
2Stock341 (51)
3Joke117 (17)
4History116 (3)
5Automobile100 (9)
6USANews55 (9)
7Midlife45 (1)
8Headline41 (41)
9Dreamer33 (13)
10FleaMarket32 (20)
11Living30 (7)

* 这里只显示发帖超过25的版面，努力灌水吧:-)

历史上的今天

  1. faintcat妹妹看进来～～ 发表于12年前.
  2. NSC, PD 1/7/2007, EB2, ... 发表于11年前.
  3. [FBA求购]MJVE2 758 MJVM2 ... 发表于6年前.
  4. 老生常谈,归与不归 发表于10年前.
  5. 【申请】Seattle西雅图 版版主——申请人... 发表于9年前.
  6. 宝宝出生，头骨骨折，求祝福 发表于9年前.
  7. 求推荐舒缓优美的古典音乐 发表于11年前.
  8. 百分之一的北京人上北大 中国网友愤怒(转载） 发表于10年前.
  9. 新人带狗狗Bailey来报道 发表于12年前.
  10. 全世界最有价值的运动队 发表于10年前.
  11. 请问大切诺基的质量如何 发表于6年前.
  12. TNND，军版全是BKC 发表于15年前.
  13. Inception 发表于12年前.
  14. 微软的有些家属可真恶心，为了卖保险脸都不要了 发表于10年前.
  15. 每周坐高铁的苦逼来说说感受吧!! 发表于9年前.
除非另有声明，本站内容采用Creative Commons BY-NC-SA 3.0协议进行许可，转载请注明来自未名观察 - 隐私政策2011-07-24 10:06:12由admin编辑