推荐:数据科学课程和书籍清单以及培训讲座


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 453|回复: 6
收起左侧

[其他] 遇到的一个面试题,希望大家一起来思考。

[复制链接] |试试Instant~ |关注本帖
vieri3221 发表于 2015-10-17 05:56:32 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
How many unique n-tuples of positive integers are there that sum up to 10000?
(where n is the number of elements in given tuple and can take any arbitrary value between 1 and 10000; "unique" tuple is defined as a list of distinct numbers)

Example of such n-tuples:

n=2: (1,9999)                        
n=3: (2000, 3000, 5000)
n=4: (1000, 2000, 3000, 4000)
....

Reminder note that (1,9999) and (9999,1) still count as one (unique) tuple.

Linzertorte 发表于 2015-10-17 06:08:11 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
dp(k,i,n) = dp
  1. dp(k,i,n) = sum( dp(k-1,j+1,n-j) j in [i..n])

  2. if(i>n) return 0
  3. if(k==1) return 1

复制代码
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-17 06:17:04 | 显示全部楼层
关注一亩三分地微博:
Warald
弄了个10意思一下。把结果全打印出来了。
1.jpg
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-17 06:36:32 | 显示全部楼层
  1. 1 -> 1
  2. 2 -> 4999
  3. 3 -> 8328334
  4. 4 -> 6934032777
  5. 5 -> 3461816314862
  6. 6 -> 1151342890475132
  7. 7 -> 273265984611424114
  8. 8 -> 48592623017121969468
  9. 9 -> 6712548463154205675387
  10. 10 -> 740807371618001612924228
  11. 11 -> 66790937017578252052043181
  12. 12 -> 5009871873784760040380174020
  13. 13 -> 317392301526501226052891438009
  14. 14 -> 17201396122217187546484617003439
  15. 15 -> 806232099461405131413873254080331
  16. 16 -> 32989355213841655613376575407042959
  17. 17 -> 1188149672483861261492278604198827065
  18. 18 -> 37939250733440646632924659229406763873
  19. 19 -> 1080949949966488114221742952571651890799
  20. 20 -> 27637548799809213269957665942466154593605
复制代码
回复 支持 反对

使用道具 举报

 楼主| vieri3221 发表于 2015-10-17 06:56:43 | 显示全部楼层

非常感谢! 求大神讲解。。
回复 支持 反对

使用道具 举报

Linzertorte 发表于 2015-10-17 07:18:22 | 显示全部楼层
dp(k,i,n)的含义是 从[i..n]取k个不同的数,加起来和为n,有几种取法。
回复 支持 反对

使用道具 举报

 楼主| vieri3221 发表于 2015-10-18 00:52:31 | 显示全部楼层
Linzertorte 发表于 2015-10-17 07:18
dp(k,i,n)的含义是 从取k个不同的数,加起来和为n,有几种取法。

明白了! 谢谢!
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-7-25 17:09

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表