Definition
- Fibonacci Numbers DP pattern – the recurrence depends on the two previous values, like the Fibonacci sequence.
- Recurrence – minCost(i) = fee[i] + min(minCost(i-1), minCost(i-2)); you arrive from one or two steps below.
- Free start – you may start before step 0 or step 1 at no cost, so both base cases are 0.
- Top is past the last step – the answer is min(lastTwoCosts) because you can reach the top from either of the last two steps.
- Rolling variables – only the last two costs are needed, giving O(n) time and O(1) space.
At the National Bank of India, each workflow stage charges a processing fee and a case can advance one or two stages at a time. Operations wants the cheapest total fee to carry a case through to completion past the last stage.
Understanding the Concepts
What is the Minimum Jumps with Fee problem?
The problem gives an array of fees where each index charges a fee to step on it. You may climb one or two steps at a time, starting before the first step. The task is to find the minimum total fee to reach the top, which is one position past the last step. This is also known as Min Cost Climbing Stairs.
package com.bank.service;
public class MinCostClimbingStairs {
public int minCostClimbingStairs(int[] cost) {
int down1 = 0; // cost to stand on previous step
int down2 = 0; // cost to stand on two steps back
for (int i = 0; i < cost.length; i++) {
int current = cost[i] + Math.min(down1, down2);
down2 = down1;
down1 = current;
}
return Math.min(down1, down2); // top is past last step
}
public static void main(String[] args) {
int[] cost = {10, 15, 20};
System.out.println("Min cost: "
+ new MinCostClimbingStairs().minCostClimbingStairs(cost));
}
}
Min cost: 15
Why is this a Fibonacci Numbers pattern?
The recurrence minCost(i) = fee[i] + min(minCost(i-1), minCost(i-2)) depends on exactly the two previous values, just like the Fibonacci sequence F(n) = F(n-1) + F(n-2). The structure is the same: to compute the current value, you only need the last two, so you can use two rolling variables instead of an array.
package com.bank.service;
public class FibonacciPatternExplanation {
// Fibonacci: F(n) = F(n-1) + F(n-2)
// Min cost: MC(i) = fee[i] + min(MC(i-1), MC(i-2))
//
// Both depend on exactly two previous values.
// Both can be computed with two rolling variables.
// The difference: Fibonacci sums, min-cost takes the minimum.
public static void main(String[] args) {
System.out.println("Fibonacci: sum of two previous.");
System.out.println("Min cost: fee + min of two previous.");
System.out.println("Both use two rolling variables => O(1) space.");
}
}
Why do both base cases start at zero?
The problem says you start before the first step, so you have not paid any fee yet. You may choose to step onto step 0 or step 1 as your first move. Both starting positions are free (cost 0). This means down1 and down2 both initialise to 0.
package com.bank.service;
public class FreeStartExplanation {
// You stand before the staircase (ground level, cost 0).
// You can step onto step 0 (pay cost[0]) or step 1 (pay cost[1]).
// minCost(0) = cost[0] + min(0, 0) = cost[0]
// minCost(1) = cost[1] + min(cost[0], 0) = cost[1] (if cost[1] < cost[0] + cost[1])
public static void main(String[] args) {
int[] cost = {10, 15, 20};
System.out.println("Start at step 0: pay " + cost[0]);
System.out.println("Start at step 1: pay " + cost[1]);
System.out.println("Start at step 1 is cheaper (15 < 10+15)");
}
}
Why is the answer min(down1, down2) instead of down1?
The top is one position past the last step. You can reach it from the last step (one step up) or from the second-to-last step (two steps up). So the answer is the minimum of the cost to stand on the last step and the cost to stand on the second-to-last step.
package com.bank.service;
public class TopIsPastLastStep {
// Steps: [10, 15, 20]
// 0 1 2 TOP
//
// Reach TOP from step 2: cost on step 2 = 20, then step 1 up
// Reach TOP from step 1: cost on step 1 = 15, then step 2 up
// Answer: min(20, 15) = 15
public static void main(String[] args) {
System.out.println("Top is past the last step.");
System.out.println("Reach from step n-1 (1 up) or step n-2 (2 up).");
System.out.println("Answer: min(cost[n-1], cost[n-2]).");
}
}
How does the array-based DP version work?
Instead of rolling variables, you can use a full dp array where dp[i] is the minimum cost to stand on step i. This uses O(n) space but is easier to trace and debug.
package com.bank.service;
public class MinCostArray {
public int minCostClimbingStairs(int[] cost) {
int n = cost.length;
int[] dp = new int[n];
dp[0] = cost[0];
dp[1] = cost[1];
for (int i = 2; i < n; i++) {
dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
}
return Math.min(dp[n - 1], dp[n - 2]);
}
public static void main(String[] args) {
int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};
System.out.println("Min cost (array): "
+ new MinCostArray().minCostClimbingStairs(cost));
}
}
Min cost (array): 6
How is this used in a banking workflow?
At National Bank of India, each workflow stage charges a processing fee. A case can advance one or two stages per action. Operations wants the cheapest total fee to carry a case from intake through to completion.
package com.bank.service;
import java.math.BigDecimal;
public class WorkflowFeeOptimiser {
public BigDecimal minFee(BigDecimal[] stageFees) {
BigDecimal down1 = BigDecimal.ZERO;
BigDecimal down2 = BigDecimal.ZERO;
for (BigDecimal fee : stageFees) {
BigDecimal current = fee.add(down1.min(down2));
down2 = down1;
down1 = current;
}
return down1.min(down2);
}
public static void main(String[] args) {
BigDecimal[] fees = {
new BigDecimal("50.00"),
new BigDecimal("120.00"),
new BigDecimal("30.00"),
new BigDecimal("80.00")
};
System.out.println("Min workflow fee: " + new WorkflowFeeOptimiser().minFee(fees));
}
}
Min workflow fee: 80.00
What are the edge cases?
Edge cases include an array of length 1 (pay that fee or skip it to the top), an array of length 2 (pay the cheaper one), and all fees being zero (cost is 0).
package com.bank.service;
public class MinCostEdgeCases {
public static void main(String[] args) {
MinCostClimbingStairs solver = new MinCostClimbingStairs();
System.out.println("Length 1: " + solver.minCostClimbingStairs(new int[]{10}));
System.out.println("Length 2: " + solver.minCostClimbingStairs(new int[]{10, 15}));
System.out.println("All zero: " + solver.minCostClimbingStairs(new int[]{0, 0, 0}));
}
}
Length 1: 0
Length 2: 10
All zero: 0
What are common mistakes?
The two most common mistakes are treating the top as the last step instead of one past it (returning down1 instead of min(down1, down2)) and forgetting that both start positions are free (initialising down1 or down2 to the fee instead of 0).
Wrong code:
// WRONG: returns cost on last step, not min of last two
return down1;
Correct code:
// CORRECT: top is past last step, reachable from last or second-to-last
return Math.min(down1, down2);
What should a senior engineer know?
A senior engineer connects this to the Fibonacci Numbers DP pattern family, which includes climbing stairs (count ways), house robber, and Fibonacci itself. The pattern is always: current depends on two previous values, solved with two rolling variables. For real money the fees are BigDecimal, and the min comparison uses BigDecimal.min.
package com.bank.service;
public class SeniorMinCostNotes {
public static void main(String[] args) {
System.out.println("Fibonacci pattern family:");
System.out.println(" Climbing stairs (count ways)");
System.out.println(" Min cost climbing stairs (min fee)");
System.out.println(" House robber (max non-adjacent sum)");
System.out.println(" Fibonacci (sum of two previous)");
System.out.println("All use two rolling variables => O(1) space.");
}
}
Visual Overview
Min Cost Climbing Stairs: Rolling DP
Fees: [10, 15, 20]
Steps: 0 1 2 TOP
Start: down1=0, down2=0 (free start positions)
i=0: current = 10 + min(0, 0) = 10
down2=0, down1=10
i=1: current = 15 + min(10, 0) = 15
down2=10, down1=15
i=2: current = 20 + min(15, 10) = 30
down2=15, down1=30
Answer: min(down1, down2) = min(30, 15) = 15
Optimal path: start before step 1, step onto step 1 (pay 15),
jump 2 to TOP. Total: 15.
┌──────┐ ┌──────┐ ┌──────┐
│ 10 │ │ 15 │ │ 20 │ TOP
│ step0│ │ step1│ │ step2│ (free)
└──────┘ └──┬───┘ └──────┘
│
└─── step onto 1 (pay 15) ──── jump 2 to TOP
Key Takeaway
Minimum Jumps with Fee, also known as Min Cost Climbing Stairs, follows the Fibonacci Numbers DP pattern. The minimum cost to stand on a step is that step's fee plus the cheaper of the two steps below. The recurrence depends on exactly two previous values, so two rolling variables give O(n) time and O(1) space.
The two details that trip people up are the free start and where the top is. You may begin before step 0 or step 1 at no cost, so both rolling variables start at zero. The top is one position past the last step, reachable from either the last or second-to-last step, so the answer is the minimum of the last two rolling costs.
This is part of the Fibonacci pattern family that includes counting climbing-stairs ways, the house robber problem, and Fibonacci itself. All use the same two-variable rolling structure. For real money in banking, the fees are BigDecimal and comparisons use BigDecimal.min.
At National Bank of India, each workflow stage charges a processing fee and a case can advance one or two stages per action. Operations uses this recurrence to find the cheapest total fee to carry a case through to completion, with BigDecimal precision for the fee amounts.
Remember one sentence: the cost to reach a step is its fee plus the cheaper of the two steps below, and the top is the cheaper of the last two.
---