Count n-tuples of positive integers are there that sum up to K

http://www.1point3acres.com/bbs/thread-144563-1-1.html

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)的含义是 从[i..n]取k个不同的数,加起来和为n,有几种取法。

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