遇到的一个面试题，希望大家一起来思考。

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.

dp(k,i,n) = dp

1. dp(k,i,n) = sum( dp(k-1,j+1,n-j) j in [i..n])
   
2. 
   
3. if(i>n) return 0
   
4. if(k==1) return 1
   
5. 
   

复制代码

弄了个10意思一下。把结果全打印出来了。

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

复制代码

Linzertorte 发表于 2015-10-17 06:08
dp(k,i,n) = dp

非常感谢！ 求大神讲解。。

dp(k,i,n)的含义是 从[i..n]取k个不同的数,加起来和为n,有几种取法。

Linzertorte 发表于 2015-10-17 07:18
dp(k,i,n)的含义是 从取k个不同的数,加起来和为n,有几种取法。

明白了！ 谢谢！