UVA 10943 - How do you add?

http://uva.onlinejudge.org/external/109/10943.html

You and a friend Ryan are stuck in a deserted island. Ryan suggested the following problem, given a number $N$, how many ways can $K$ numbers less or equal than $N$ add up to $N$?

For example for $N = 5$ and $K = 2$, there are 6 ways:

$5 + 0$

$4 + 1$

$3 + 2$

$2 + 3$

$1 + 4$

$0 + 5$

This problem has the same solution that UVA 10910 - Marks Distribution. The only difference is that in Marks Distribution the author tried to make the problem a little bit more complicated by adding constraints.

We can solve this problem using Dynamic Programming. A good way to look at this problem is imagined that for each $K$ we have an empty box to be filled. to fill each one of the boxes we have $N$ objects, based on this analogy, we can further extend our ideas to the state of the solution.

The DP state is the following:

$n$ - number of objects

$k$ - current box

$rec(n, k)$ = number of ways of adding up $K$ numbers and get $N$ as the result. Finally, using this state we recursively calculate all the possible ways of filling the boxes in the following way, where $0 \leq i \leq n$ we have that $rec(n - i, k - 1)$. This means, take $i$ objects of the remaining $n$ objects and after that go to the next box $(k - 1)$.

The overall time complexity of this solution is $O(N \cdot K)$.

Bottom-up dynamic programming solution: