CODEWITHSUNDEEP
algorithmdynamic-programming
rsirs
rsirs

Reputation: 107

Possible Staircases using Dynamic Programming

For the Staircase problem mentioned in the URL http://acm.timus.ru/problem.aspx?num=1017&locale=en enter image description here

Can we solve it in linear time O(k) where k is the maximum steps possible? I felt like missing some logic using below approach

enter image description here

Any Suggestions?

Below is the code That I have implemented:

    def answer(n):
        steps = determine_steps(n)
        x = ((n -1) - n/steps) * ((n-2) - n/steps + 1)  #Minimum of two stair case
        for i in range(3, steps):
            x = x * ((n-i)/i)    #Stairs from 3 can go from minimum height 0 to max (n-i)/i
        return x


    def determine_steps(n):
        """Determine no of steps possible"""
        steps = 1;
        while (steps * steps + steps) <= 2 * n:
            steps = steps + 1
        return steps - 1

    #print answer(212)
    print answer(212)

Upvotes: 3

Views: 1284

Answers (1)

Vinay Lodha
Vinay Lodha

Reputation: 211

Suppose, you have a function which takes 2 parameters, one left which is number of bricks left and the other one is curr which is the current height of the step which you are on. Now, at any step you have 2 options. The first option is to increase the height of the current step you are on by adding one more brick, i.e., rec(left-1, curr+1) and the second option is to create a new step whose height should be greater than curr ,i.e., rec(left-curr-1, curr+1) ( you created a step of height curr+1 ). Now, left can never be negative , thus if left<0 then return 0. And when left is 0 that means, we have created a valid staircase,thus if left==0 then return 1.

This case: if dp[left][curr] !=-1 is just for memoization.

Now, rec( 212-1, 1 ) means a step of height 1 is created and it is the current step. And for final answer 1 is subtracted because any valid staircase should contain at least 2 steps so, subtracting 1 for single step staircase.

# your code goes here
dp = [ [-1]*501 for i in range(501) ]

def rec(left, curr):
    if left<0:
        return 0
    if left==0:
        return 1
    if dp[left][curr] !=-1:
        return dp[left][curr]
    dp[left][curr] = rec(left-1, curr+1) + rec( left-curr-1, curr+1)
    return dp[left][curr]

print ( rec(212-1,1) - 1 )

Feel free to comment back, if you are not able to understand the code.

Upvotes: 4

Related Questions