Link to the problem on Timus Online Judge
If you look closely to the structure of different staircases for a specific n, you might understand the recursive structure of them, I mean some staircases have common prefix and from a column their difference starts.
If you are familiar with Dynamic Programming and think about state of the dynamic programming, sooner or later you will find a solution with time complexity O(n^3).
Let's define our state as this : dp[min][rem] which means in this column we are standing at we need to put at least min bricks and we have rem bricks remained to use, so what do we do about this column we are standing at?
We test all possible values for this column -> dp[min][rem] = SUM{ dp[k+1][rem-k], such that k = min...rem } which means for the next column use at least k+1 bricks and you have rem-k bricks remained.
What about the basic state? What is basic state, The state which we know the answer and now more recursion is needed. when rem is equal to 0 or rem is equal to min, there is no need to recur again, the answer to this state is equal to 1.
If you look closely to the structure of different staircases for a specific n, you might understand the recursive structure of them, I mean some staircases have common prefix and from a column their difference starts.
If you are familiar with Dynamic Programming and think about state of the dynamic programming, sooner or later you will find a solution with time complexity O(n^3).
Let's define our state as this : dp[min][rem] which means in this column we are standing at we need to put at least min bricks and we have rem bricks remained to use, so what do we do about this column we are standing at?
We test all possible values for this column -> dp[min][rem] = SUM{ dp[k+1][rem-k], such that k = min...rem } which means for the next column use at least k+1 bricks and you have rem-k bricks remained.
What about the basic state? What is basic state, The state which we know the answer and now more recursion is needed. when rem is equal to 0 or rem is equal to min, there is no need to recur again, the answer to this state is equal to 1.
No comments:
Post a Comment