Solution 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).

Example 2:

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

Let's first start with a recursive brute-force solution.

Basic Solution

At every step, we have three options: either jump 1 step, 2 steps, or 3 steps. So our algorithm will look like:

java

class Solution {

  public int findMinFee(int[] fee) {
    return findMinFeeRecursive(fee, 0);
  }

  private int findMinFeeRecursive(int[] fee, int currentIndex) {
    if (currentIndex > fee.length - 1) return 0;

    // if we take 1 step, we are left with 'n-1' steps;
    int take1Step = findMinFeeRecursive(fee, currentIndex + 1);
    // similarly, if we took 2 steps, we are left with 'n-2' steps;
    int take2Step = findMinFeeRecursive(fee, currentIndex + 2);
    // if we took 3 steps, we are left with 'n-3' steps;
    int take3Step = findMinFeeRecursive(fee, currentIndex + 3);

    int min = Math.min(Math.min(take1Step, take2Step), take3Step);

    return min + fee[currentIndex];
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    int[] fee = { 1, 2, 5, 2, 1, 2 };
    System.out.println(sc.findMinFee(fee));
    fee = new int[] { 2, 3, 4, 5 };
    System.out.println(sc.findMinFee(fee));
  }
}

The time complexity of the above algorithm is exponential . The space complexity is which is used to store the recursion stack.

Top-down Dynamic Programming with Memoization

To resolve overlapping subproblems, we can use an array to store the already solved subproblems. Here is the code:

java

class Solution {

  public int findMinFee(int[] fee) {
    int dp[] = new int[fee.length];
    return findMinFeeRecursive(dp, fee, 0);
  }

  private int findMinFeeRecursive(int[] dp, int[] fee, int currentIndex) {
    if (currentIndex > fee.length - 1) return 0;

    if (dp[currentIndex] == 0) {
      // if we take 1 step, we are left with 'n-1' steps;
      int take1Step = findMinFeeRecursive(dp, fee, currentIndex + 1);
      // similarly, if we took 2 steps, we are left with 'n-2' steps;
      int take2Step = findMinFeeRecursive(dp, fee, currentIndex + 2);
      // if we took 3 steps, we are left with 'n-3' steps;
      int take3Step = findMinFeeRecursive(dp, fee, currentIndex + 3);

      dp[currentIndex] =
        fee[currentIndex] + Math.min(Math.min(take1Step, take2Step), take3Step);
    }

    return dp[currentIndex];
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    int[] fee = { 1, 2, 5, 2, 1, 2 };
    System.out.println(sc.findMinFee(fee));
    fee = new int[] { 2, 3, 4, 5 };
    System.out.println(sc.findMinFee(fee));
  }
}

Bottom-up Dynamic Programming

Let's try to populate our dp[] array from the above solution, working in a bottom-up fashion. As we saw in the above code, every findMinFeeRecursive(n) is the minimum of the three recursive calls; we can use this fact to populate our array.

Code

Here is the code for our bottom-up dynamic programming approach:

java

class Solution {

  public int findMinFee(int[] fee) {
    int dp[] = new int[fee.length + 1]; // +1 to handle the 0th step
    dp[0] = 0; // if there are no steps, we dont have to pay any fee
    dp[1] = fee[0]; // only one step, so we have to pay its fee
    // for 2 or 3 steps staircase, since we start from the first step so we have to pay its fee
    // and from the first step we can reach the top by taking two or three steps, so we don't
    // have to pay any other fee.
    dp[2] = dp[3] = fee[0];

    for (int i = 3; i < fee.length; i++) dp[i + 1] = Math.min(
      fee[i] + dp[i],
      Math.min(fee[i - 1] + dp[i - 1], fee[i - 2] + dp[i - 2])
    );

    return dp[fee.length];
  }

  public static void main(String[] args) {
    Solution sc = new Solution();
    int[] fee = { 1, 2, 5, 2, 1, 2 };
    System.out.println(sc.findMinFee(fee));
    fee = new int[] { 2, 3, 4, 5 };
    System.out.println(sc.findMinFee(fee));
  }
}

The above solution has time and space complexity of .

Fibonacci number pattern

We can clearly see that this problem follows the Fibonacci number pattern. The only difference is that every Fibonacci number is a sum of the two preceding numbers, whereas in this problem every number (total fee) is the minimum of previous three numbers.

🤖 Don't fully get this? Learn it with Claude

Stuck on Solution Minimum jumps with fee? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🪜 Hint ladder (no spoilers)

Progressively stronger hints — you still solve it.

I'm working on the problem **Solution Minimum jumps with fee** (DSA). Give me a HINT LADDER: start with the tiniest nudge, then wait. Only reveal the next, stronger hint when I ask. Do NOT show the full solution unless I type 'show solution'. Keep me doing the thinking. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🎨 Explain the approach visually

See the technique, not just code.

Explain the optimal approach to **Solution Minimum jumps with fee** with a VISUAL walkthrough: trace it on a small concrete example using ASCII art / a step-by-step diagram, narrate what changes each step, then give time & space complexity with a one-line derivation. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔍 Review my solution

Catch bugs, edge cases, sub-optimality.

I'll paste my solution to **Solution Minimum jumps with fee**. Review it for correctness, missed edge cases, and time/space complexity, then coach me toward the optimal — don't just rewrite it. Ask me to paste my code now. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🔁 Drill the pattern

Lock in recognition with look-alikes.

Give me 2 problems that use the SAME underlying pattern as **Solution Minimum jumps with fee**. For each, let me attempt first, then review my answer and name the trigger signal that reveals the pattern. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Solution Minimum jumps to reach th Solution House thief →