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: