Grokking Dynamic Programming Patterns for Coding Interviews

0% completed

​

Minimum jumps with fee

Problem Statement

Given a staircase with ‘n’ steps and an array of 'n' numbers representing the fee that you have to pay if you take the step. Implement a method to calculate the minimum fee required to reach the top of the staircase (beyond the top-most step). At every step, you have an option to take either 1 step, 2 steps, or 3 steps. You should assume that you are standing at the first step.

Example 1:

Number of stairs (n) : 6
Fee: {1,2,5,2,1,2}
Output: 3
Explanation: Starting from index '0', we can reach the top through: 0->3->top
The total fee we have to pay will be (1+2).
`

.....

.....

.....

Like the course? Get enrolled and start learning!
C

Cockles

· 4 years ago

'Minimum jumps with fee ' example two is wrong

Show 4 replies
G

Gary

· 4 years ago

For bottom up solution, why don't isn't dp[3] initialized to fee[0], like dp[1] and dp[2] since the min fee is just cost of taking 3 steps from the 0 index? Then the for loop would start at 3 instead of 2.

Show 2 replies
Nitesh Kumar

Nitesh Kumar

· 3 days ago

O(n) time & O(1) space

class Solution:
  def findMinFee(self, fee):
    if len(fee)==0:
      return -1
    n_minus1 = n_minus2 = n_minus3 = 0
    for i in range(len(fee)-1, -1, -1):
      current_cost = fee[i] + min(n_minus1, n_minus2, n_minus3)
      n_minus3 = n_minus2
      n_minus2 = n_minus1
      n_minus1 = current_cost
    return n_minus1