http://acm.timus.ru/problem.aspx?space=1&num=1017
I have been trying this problem for a while . I have figured out the state to be dp[taken][remaining] where taken tells me the number of blocks i have used till now , and remaining tells me the number of blocks that are left with me . Now base case is trivial , but I am not able to get the transition . Can someone please help me with this . Any help is appreciated :)
f(taken, remaining) is slightly hard ....
But you're on the right track. The second dimension needs to be something else.
It should be the maximum height of the last tower. We need this information in constructing the second last tower. For example, if we have 7 bricks and we used 3 on last tower, we need to know that we are only allowed maximum height 2.
Here is the recurrence —
f(i, j) represents the number of staircases with i bricks, last tower height at most j.
Then, we have two choices — either we have a tower of height j or we do not.
f(i, j) = f(i — j, j — 1) + f(i, j — 1)
The answer is f(n, n — 1) because we need at least two stairs.
Also, if j >= i, then f(i, j) = f(i, i — 1)
Here's some code for your reference. You can follow me on GitHub if you like.
Quiet don't understand meaning of initial states. Of course, they are fictive and I see how right answer is got. The same with such auxiliary states like f(n, n). Logically it must equal f(n, n — 1), but we add f(0, n — 1). What is the meaning?
Sorry for necroposting,
UPD: All the time I thought about 2-stair staircases. Now it is clear. Sorry for disturbing.