You are given n steps of stairs and a list fee because each step has a fee associated with it. Your task is to calculate the minimum fee required to reach the top of the stairs (beyond the top step), assuming you start with the first step. At every step, you can take 1 step, 2 steps, or 3 steps.

Let’s say you have a staircase of six steps. The fee for each step is [1,2,3,2,3,1][1,2,3,2,3,1]. The minimum cost to reach the top will be 33. This cost is calculated as follows:

  • Starting from the first step, totalfee=1total fee = 1.
  • Taking 3 steps would get us to the fourth floor. The fee for the fourth floor is 2, so the totalfee=1+2=3total fee = 1+2=3.
  • Taking 3 more steps would take us beyond the top-most step. Since we are not stepping on any particular step, our total fee would remain the same.


  • 11 \leq n 4000\leq 4000
  • fee.length 4000\leq 4000

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.