http://codeforces.com/problemset/problem/946/D

[暴力法]

等價於把K個相同的物品放置到n個相異的籃子中。
Complexity = C(k + n - 1,  n - 1) or C(k + n - 1,  k);
By n, m and k (1 ≤ n, m ≤ 500, 0 ≤ k ≤ 500).
max Complexity ~ C(1000, 500) ~ (4^500)

Stirling's approximation yields the following approximation, when ${\displaystyle n,i}$ are sufficiently large:

${\displaystyle {n \choose i}\sim {\sqrt {n \over 2\pi i(n-i)}}\cdot {n^{n} \over i^{i}(n-i)^{n-i}}}$

In particular, when ${\displaystyle n}$ is sufficiently large:

${\displaystyle {2n \choose n}\sim {\frac {4^{n}}{\sqrt {\pi n}}}}$

[遞迴公式]

設opt(s, t)為在前s個weeks可缺席t堂課最佳解，h(s, i)是在第s個week缺席i堂課花費的hour數。

則 opt(s, t) = min(opt(s -1, t - i) + h(s, i)), i = 0 to k。

[bottom up]

一開始我們在第0周(s = 0)，該時的opt(0, i) = h(s, i)
最後opt(n,k)就是最佳解。

[Time Complexity]:

共有n列，每列有k個元素，每個元素需要計算k個組合，故複雜度為O(n*(k^2))。

[Space Complexity]:

用兩列每列k+1個元素的表格即可。

[Example]

1.輸入 n = 3, m = 5, k = 4

01011

10011

11100

表格如下:

ex: 當s = 1且t = 4時，由下表計算知道2為最佳。