pvpcoder's blog

No of ways to express N as a sum of k partitions ?
By pvpcoder, history, 11 years ago, In English

I Searched on the internet and I found this recurrence f(n,k)=f(n-1,k-1)+f(n-k,k).
But unable to understand how it works?

Tags dp
  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Can partitions be empty?

→ Reply
»
11 years ago, hide # |
 
Vote: I like it +11 Vote: I do not like it

If one of k partitions is 1, then the number of ways is f(n — 1, k — 1). Otherwise, substruct each partition by 1, in this case it's f(n — k, k).

→ Reply