Suppose there are $ K $ buckets each can be filled upto $ N-1 $ balls. The gain on putting $ i $ balls in the $ k^{th} $ bucket is given by $ \Delta l\_{k,i}, \, i \in [1,N-1] $. The problem is to put $ \lambda $ balls in those buckets to maximize the overall gain.


How do we solve it?



dynamic programming and combinatorics
You can use dynamic programming as you suggest in the title.


Let $w\_{ij}$ be the max gain you can get putting $j$ balls into first $i$ buckets.


Then $w\_{ij}$ has the following recursive relation:
$$
w\_{i,j} = \max\_{0 \le t \le \min(N-1, j)}(w\_{i-1,j-t} + \Delta l\_{i, t})
$$


There $t$ is the number of balls you put into $i$-th bucket.
Hence you can calculate $w\_{K, \lambda}$ (your answer) in time $O(K \lambda N)$.


