Minimum Cost Climbing Stairs

🎯

Minimum Cost Climbing Stairs

easyDPAmazonGoogle

Imagine you want to climb a staircase but each step costs some energy. You want to reach the top spending the least energy possible.

💡 This problem is a classic example of linear dynamic programming where the decision at each step depends on previous steps. Beginners often struggle to see why greedy approaches fail and how to build the dp relation.

📋

Problem Statement

Given an integer array cost where cost[i] is the cost of i-th step on a staircase, return the minimum cost to reach the top of the floor. You can either start from step 0 or step 1, and you can climb either one or two steps at a time.

1 ≤ cost.length ≤ 10^50 ≤ cost[i] ≤ 999

💡

Example

Input"cost = [10, 15, 20]"

Output15

Start at step 1 (cost 15), then climb two steps to the top, total cost 15.

Input"cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]"

Output6

Optimal path is 0 -> 2 -> 3 -> 4 -> 6 -> 7 -> 9 -> top with total cost 6.

• cost = [0] → output 0 (only one step, zero cost)
• cost = [1, 1] → output 1 (choose cheaper start)
• cost = [10, 0, 0, 10] → output 0 (skip expensive steps)
• cost = [999, 999, 999, 999] → output 1998 (must pay some cost)

🔁

Why DP?

Why greedy fails:

A greedy approach that always picks the cheaper next step fails because sometimes paying more now leads to cheaper overall cost later. For example, cost = [10, 15, 1], greedy picks 10 then 15, total 25, but optimal is 15 then 1, total 16.

DP state:

dp[i] represents the minimum cost to reach step i.

Recurrence:dp[i] = cost[i] + min(dp[i-1], dp[i-2])

To reach step i, pay cost[i] plus the cheaper cost of reaching step i-1 or i-2.

⚠️

Common Mistakes

Starting recursion from step 0 only

Misses the possibility of starting from step 1, leading to incorrect results

✅ Return min cost of reaching last or second last step as top can be reached from either

Not handling base cases correctly in recursion

Leads to index errors or incorrect cost calculations

✅ Explicitly return cost for steps 0 and 1, and 0 for negative indices

Using greedy approach picking cheapest next step

Produces suboptimal total cost

✅ Use DP to consider all paths and choose minimum total cost

Forgetting to take min of last two dp values at the end

Returns cost to last step only, ignoring that top can be reached from last or second last step

✅ Return min(dp[n-1], dp[n-2])

Using O(n) space DP when O(1) is possible

Unnecessarily high memory usage

✅ Use two variables to store previous two dp values

🧠

Brute Force (Pure Recursion)

💡 This approach helps understand the problem by exploring all possible paths without optimization, revealing overlapping subproblems.

Intuition

Try every possible way to reach the top by recursively choosing to climb one or two steps, summing costs along the way.

Algorithm

1. Define a recursive function to compute minimum cost to reach step i.
2. Base cases: cost to reach step 0 or 1 is their own cost.
3. For other steps, recursively compute cost for i-1 and i-2, add current cost.
4. Return the minimum cost between reaching the last or second last step.

💡 The recursion tree grows exponentially because it recomputes costs for the same steps multiple times.

Recurrence:minCost(i) = cost[i] + min(minCost(i-1), minCost(i-2))

</>

Code

def minCostClimbingStairs(cost):
    n = len(cost)
    def dfs(i):
        if i < 0:
            return 0
        if i == 0 or i == 1:
            return cost[i]
        return cost[i] + min(dfs(i-1), dfs(i-2))
    return min(dfs(n-1), dfs(n-2))

# Example usage
if __name__ == '__main__':
    cost = [10, 15, 20]
    print(minCostClimbingStairs(cost))  # Output: 15

Line Notes

def dfs(i):Defines recursive helper to compute min cost to step i

if i < 0:Base case: negative index means no cost

if i == 0 or i == 1:Base case: cost to reach first two steps is their own cost

return cost[i] + min(dfs(i-1), dfs(i-2))Recursively compute min cost from previous two steps plus current cost

return min(dfs(n-1), dfs(n-2))Minimum cost to reach top is min cost to last or second last step

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        return Math.min(dfs(cost, n - 1), dfs(cost, n - 2));
    }
    private int dfs(int[] cost, int i) {
        if (i < 0) return 0;
        if (i == 0 || i == 1) return cost[i];
        return cost[i] + Math.min(dfs(cost, i - 1), dfs(cost, i - 2));
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] cost = {10, 15, 20};
        System.out.println(sol.minCostClimbingStairs(cost)); // 15
    }
}

Line Notes

public int minCostClimbingStairs(int[] cost)Entry point to compute min cost

return Math.min(dfs(cost, n - 1), dfs(cost, n - 2));Minimum cost to reach top is min cost to last or second last step

private int dfs(int[] cost, int i)Recursive helper to compute min cost to step i

if (i < 0) return 0;Base case for invalid step index

return cost[i] + Math.min(dfs(cost, i - 1), dfs(cost, i - 2));Recursively compute min cost from previous two steps plus current cost

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dfs(const vector<int>& cost, int i) {
    if (i < 0) return 0;
    if (i == 0 || i == 1) return cost[i];
    return cost[i] + min(dfs(cost, i - 1), dfs(cost, i - 2));
}

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    return min(dfs(cost, n - 1), dfs(cost, n - 2));
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << minCostClimbingStairs(cost) << endl; // 15
    return 0;
}

Line Notes

int dfs(const vector<int>& cost, int i)Recursive helper to compute min cost to step i

if (i < 0) return 0;Base case for invalid step index

if (i == 0 || i == 1) return cost[i];Base case for first two steps

return cost[i] + min(dfs(cost, i - 1), dfs(cost, i - 2));Recursively compute min cost from previous two steps plus current cost

return min(dfs(cost, n - 1), dfs(cost, n - 2));Minimum cost to reach top is min cost to last or second last step

function minCostClimbingStairs(cost) {
    const n = cost.length;
    function dfs(i) {
        if (i < 0) return 0;
        if (i === 0 || i === 1) return cost[i];
        return cost[i] + Math.min(dfs(i - 1), dfs(i - 2));
    }
    return Math.min(dfs(n - 1), dfs(n - 2));
}

// Example usage
console.log(minCostClimbingStairs([10, 15, 20])); // 15

Line Notes

function dfs(i)Recursive helper to compute min cost to step i

if (i < 0) return 0;Base case for invalid step index

if (i === 0 || i === 1) return cost[i];Base case for first two steps

return cost[i] + Math.min(dfs(i - 1), dfs(i - 2));Recursively compute min cost from previous two steps plus current cost

return Math.min(dfs(n - 1), dfs(n - 2));Minimum cost to reach top is min cost to last or second last step

⏱

Complexity

TimeO(2^n)

SpaceO(n) due to recursion stack

Each call branches into two calls, leading to exponential time. Stack depth is at most n.

💡 For n=20, this means over a million calls, which is impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is essential to understand the problem structure.

🧠

Top-Down DP with Memoization

💡 Memoization avoids recomputing the same states by caching results, drastically improving efficiency.

Intuition

Store results of recursive calls so that when the same step is reached again, return the cached result instead of recomputing.

Algorithm

1. Create a memo dictionary to store min cost for each step.
2. Modify recursive function to check memo before computing.
3. Compute min cost recursively with memoization.
4. Return min cost to reach top from last or second last step.

💡 Memoization converts exponential recursion into linear time by avoiding repeated work.

Recurrence:dp[i] = cost[i] + min(dp[i-1], dp[i-2])

</>

Code

def minCostClimbingStairs(cost):
    n = len(cost)
    memo = {}
    def dfs(i):
        if i < 0:
            return 0
        if i == 0 or i == 1:
            return cost[i]
        if i in memo:
            return memo[i]
        memo[i] = cost[i] + min(dfs(i-1), dfs(i-2))
        return memo[i]
    return min(dfs(n-1), dfs(n-2))

# Example usage
if __name__ == '__main__':
    cost = [10, 15, 20]
    print(minCostClimbingStairs(cost))  # Output: 15

Line Notes

memo = {}Initialize cache to store computed results

if i in memo:Return cached result if available to avoid recomputation

memo[i] = cost[i] + min(dfs(i-1), dfs(i-2))Compute and cache min cost for step i

return min(dfs(n-1), dfs(n-2))Return min cost to reach top

import java.util.HashMap;
public class Solution {
    private HashMap<Integer, Integer> memo = new HashMap<>();
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        return Math.min(dfs(cost, n - 1), dfs(cost, n - 2));
    }
    private int dfs(int[] cost, int i) {
        if (i < 0) return 0;
        if (i == 0 || i == 1) return cost[i];
        if (memo.containsKey(i)) return memo.get(i);
        int res = cost[i] + Math.min(dfs(cost, i - 1), dfs(cost, i - 2));
        memo.put(i, res);
        return res;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] cost = {10, 15, 20};
        System.out.println(sol.minCostClimbingStairs(cost)); // 15
    }
}

Line Notes

private HashMap<Integer, Integer> memo = new HashMap<>();Cache to store computed results

if (memo.containsKey(i)) return memo.get(i);Return cached result if available

memo.put(i, res);Store computed result in cache

return Math.min(dfs(cost, n - 1), dfs(cost, n - 2));Return min cost to reach top

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

unordered_map<int,int> memo;

int dfs(const vector<int>& cost, int i) {
    if (i < 0) return 0;
    if (i == 0 || i == 1) return cost[i];
    if (memo.count(i)) return memo[i];
    memo[i] = cost[i] + min(dfs(cost, i - 1), dfs(cost, i - 2));
    return memo[i];
}

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    memo.clear();
    return min(dfs(cost, n - 1), dfs(cost, n - 2));
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << minCostClimbingStairs(cost) << endl; // 15
    return 0;
}

Line Notes

unordered_map<int,int> memo;Cache to store computed results

if (memo.count(i)) return memo[i];Return cached result if available

memo[i] = cost[i] + min(dfs(cost, i - 1), dfs(cost, i - 2));Compute and cache min cost for step i

return min(dfs(cost, n - 1), dfs(cost, n - 2));Return min cost to reach top

function minCostClimbingStairs(cost) {
    const n = cost.length;
    const memo = new Map();
    function dfs(i) {
        if (i < 0) return 0;
        if (i === 0 || i === 1) return cost[i];
        if (memo.has(i)) return memo.get(i);
        const res = cost[i] + Math.min(dfs(i - 1), dfs(i - 2));
        memo.set(i, res);
        return res;
    }
    return Math.min(dfs(n - 1), dfs(n - 2));
}

console.log(minCostClimbingStairs([10, 15, 20])); // 15

Line Notes

const memo = new Map();Cache to store computed results

if (memo.has(i)) return memo.get(i);Return cached result if available

memo.set(i, res);Store computed result in cache

return Math.min(dfs(n - 1), dfs(n - 2));Return min cost to reach top

⏱

Complexity

TimeO(n)

SpaceO(n) for memo and recursion stack

Each step is computed once and cached, reducing exponential calls to linear.

💡 For n=20, this means about 20 calls, which is efficient.

Interview Verdict: Accepted

Memoization makes the solution efficient enough for large inputs.

🧠

Bottom-Up DP (Tabulation)

💡 This approach builds the solution iteratively from the base cases up, avoiding recursion and making the process clearer and more efficient.

Intuition

Start from the first two steps and iteratively compute the minimum cost to reach each subsequent step using previously computed results.

Algorithm

1. Initialize a dp array of size n to store min cost to each step.
2. Set dp[0] = cost[0] and dp[1] = cost[1].
3. Iterate from step 2 to n-1, computing dp[i] = cost[i] + min(dp[i-1], dp[i-2]).
4. Return min(dp[n-1], dp[n-2]) as the min cost to reach the top.

💡 This iterative approach avoids recursion overhead and clearly shows the dependency between steps.

Recurrence:dp[i] = cost[i] + min(dp[i-1], dp[i-2])

</>

Code

def minCostClimbingStairs(cost):
    n = len(cost)
    dp = [0] * n
    dp[0], dp[1] = cost[0], cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    return min(dp[n-1], dp[n-2])

# Example usage
if __name__ == '__main__':
    cost = [10, 15, 20]
    print(minCostClimbingStairs(cost))  # Output: 15

Line Notes

dp = [0] * nInitialize dp array to store min cost for each step

dp[0], dp[1] = cost[0], cost[1]Base cases: cost to reach first two steps

for i in range(2, n):Iterate through steps starting from 2

dp[i] = cost[i] + min(dp[i-1], dp[i-2])Compute min cost for step i using previous two steps

return min(dp[n-1], dp[n-2])Return min cost to reach top

public class Solution {
    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) {
        Solution sol = new Solution();
        int[] cost = {10, 15, 20};
        System.out.println(sol.minCostClimbingStairs(cost)); // 15
    }
}

Line Notes

int[] dp = new int[n];Create dp array to store min cost per step

dp[0] = cost[0]; dp[1] = cost[1];Initialize base cases

for (int i = 2; i < n; i++)Iterate through steps from 2 to n-1

dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);Compute min cost for step i

return Math.min(dp[n - 1], dp[n - 2]);Return min cost to reach top

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCostClimbingStairs(vector<int>& cost) {
    int n = cost.size();
    vector<int> dp(n);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (int i = 2; i < n; i++) {
        dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);
    }
    return min(dp[n - 1], dp[n - 2]);
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << minCostClimbingStairs(cost) << endl; // 15
    return 0;
}

Line Notes

vector<int> dp(n);Create dp vector to store min cost per step

dp[0] = cost[0]; dp[1] = cost[1];Initialize base cases

for (int i = 2; i < n; i++)Iterate through steps from 2 to n-1

dp[i] = cost[i] + min(dp[i - 1], dp[i - 2]);Compute min cost for step i

return min(dp[n - 1], dp[n - 2]);Return min cost to reach top

function minCostClimbingStairs(cost) {
    const n = cost.length;
    const dp = new Array(n);
    dp[0] = cost[0];
    dp[1] = cost[1];
    for (let 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]);
}

console.log(minCostClimbingStairs([10, 15, 20])); // 15

Line Notes

const dp = new Array(n);Initialize dp array for min cost per step

dp[0] = cost[0]; dp[1] = cost[1];Set base cases

for (let i = 2; i < n; i++)Iterate through steps starting at 2

dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);Compute min cost for step i

return Math.min(dp[n - 1], dp[n - 2]);Return min cost to reach top

⏱

Complexity

TimeO(n)

SpaceO(n)

Single pass through cost array, storing results in dp array.

💡 For n=20, about 20 iterations, very efficient.

Interview Verdict: Accepted

This is the standard optimal solution using bottom-up DP.

🧠

Space Optimized Bottom-Up DP

💡 Since dp[i] depends only on dp[i-1] and dp[i-2], we can reduce space from O(n) to O(1) by storing only two variables.

Intuition

Keep track of minimum costs for the previous two steps and update iteratively without a full dp array.

Algorithm

1. Initialize two variables to store min cost for first two steps.
2. Iterate from step 2 to n-1, compute current min cost using previous two.
3. Update the two variables to move forward.
4. Return min of the last two computed costs.

💡 This approach maintains the same logic as tabulation but uses constant space.

Recurrence:dp[i] = cost[i] + min(dp[i-1], dp[i-2])

</>

Code

def minCostClimbingStairs(cost):
    n = len(cost)
    prev2, prev1 = cost[0], cost[1]
    for i in range(2, n):
        curr = cost[i] + min(prev1, prev2)
        prev2, prev1 = prev1, curr
    return min(prev1, prev2)

# Example usage
if __name__ == '__main__':
    cost = [10, 15, 20]
    print(minCostClimbingStairs(cost))  # Output: 15

Line Notes

prev2, prev1 = cost[0], cost[1]Initialize variables for first two steps

for i in range(2, n):Iterate through steps starting at 2

curr = cost[i] + min(prev1, prev2)Compute current min cost using previous two

prev2, prev1 = prev1, currUpdate variables to move forward

return min(prev1, prev2)Return min cost to reach top

public class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int prev2 = cost[0], prev1 = cost[1];
        for (int i = 2; i < cost.length; i++) {
            int curr = cost[i] + Math.min(prev1, prev2);
            prev2 = prev1;
            prev1 = curr;
        }
        return Math.min(prev1, prev2);
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] cost = {10, 15, 20};
        System.out.println(sol.minCostClimbingStairs(cost)); // 15
    }
}

Line Notes

int prev2 = cost[0], prev1 = cost[1];Initialize variables for first two steps

for (int i = 2; i < cost.length; i++)Iterate through steps starting at 2

int curr = cost[i] + Math.min(prev1, prev2);Compute current min cost

prev2 = prev1; prev1 = curr;Update variables for next iteration

return Math.min(prev1, prev2);Return min cost to reach top

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int minCostClimbingStairs(vector<int>& cost) {
    int prev2 = cost[0], prev1 = cost[1];
    for (int i = 2; i < cost.size(); i++) {
        int curr = cost[i] + min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return min(prev1, prev2);
}

int main() {
    vector<int> cost = {10, 15, 20};
    cout << minCostClimbingStairs(cost) << endl; // 15
    return 0;
}

Line Notes

int prev2 = cost[0], prev1 = cost[1];Initialize variables for first two steps

for (int i = 2; i < cost.size(); i++)Iterate through steps starting at 2

int curr = cost[i] + min(prev1, prev2);Compute current min cost

prev2 = prev1; prev1 = curr;Update variables for next iteration

return min(prev1, prev2);Return min cost to reach top

function minCostClimbingStairs(cost) {
    let prev2 = cost[0], prev1 = cost[1];
    for (let i = 2; i < cost.length; i++) {
        let curr = cost[i] + Math.min(prev1, prev2);
        prev2 = prev1;
        prev1 = curr;
    }
    return Math.min(prev1, prev2);
}

console.log(minCostClimbingStairs([10, 15, 20])); // 15

Line Notes

let prev2 = cost[0], prev1 = cost[1];Initialize variables for first two steps

for (let i = 2; i < cost.length; i++)Iterate through steps starting at 2

let curr = cost[i] + Math.min(prev1, prev2);Compute current min cost

prev2 = prev1; prev1 = curr;Update variables for next iteration

return Math.min(prev1, prev2);Return min cost to reach top

⏱

Complexity

TimeO(n)

SpaceO(1)

Single pass with constant extra space.

💡 For n=20, this is very efficient and uses minimal memory.

Interview Verdict: Accepted

This is the most optimal solution in both time and space.

📊

All Approaches - One-Glance Tradeoffs

💡 In interviews, code bottom-up DP or space optimized DP for best balance of clarity and efficiency.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(2^n)	O(n) recursion stack	Yes (deep recursion)	N/A	Mention only - never code
2. Top-Down DP with Memoization	O(n)	O(n) memo + recursion stack	Possible but less likely	Yes with extra tracking	Good to mention, sometimes code if comfortable
3. Bottom-Up DP (Tabulation)	O(n)	O(n)	No	Yes with extra tracking	Standard solution to code
4. Space Optimized Bottom-Up DP	O(n)	O(1)	No	No (without extra work)	Best for follow-up or optimization

💼

Interview Strategy

💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Clarify problem constraints and inputs.Explain brute force recursion to show understanding of problem structure.Introduce memoization to optimize recursion.Present bottom-up DP as the standard solution.Finally, show space optimization for best efficiency.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 10min → Test: 5min. Total ~20min

What the Interviewer Tests

Ability to identify overlapping subproblems, write correct DP recurrence, optimize from brute force to efficient DP, and communicate clearly.

Common Follow-ups

• What if you can climb up to k steps at a time? → Generalize recurrence to min over last k dp states.
• Can you reconstruct the path taken? → Store choices in an auxiliary array during DP.

💡 These follow-ups test your ability to generalize DP and track solution paths.

🔍

Pattern Recognition

When to Use

1) Problem involves linear steps or sequence; 2) Choices depend on previous one or two steps; 3) Min or max cost/score to reach end; 4) Overlapping subproblems with optimal substructure.

Signature Phrases

'You can climb either one or two steps at a time''Return the minimum cost to reach the top'

NOT This Pattern When

Problems requiring 2D DP or knapsack style decisions are different despite some similarities.

Similar Problems

Climbing Stairs - counts ways to climb stairs, similar step choicesHouse Robber - linear dp with max sum, similar recurrenceFibonacci Number - classic linear recurrence pattern

Practice

1. You are given an array representing daily stock prices. You want to find the maximum profit possible by buying once and selling once after the buy day. Which approach guarantees the optimal solution with linear time and constant space complexity?

easy

A. Use nested loops to check all pairs of buy and sell days and track the maximum profit.

B. Use a dynamic programming table storing maximum profit for each day and each possible transaction count.

C. Iterate once, tracking the minimum price so far and updating the maximum profit by comparing current price minus minimum price.

D. Apply a greedy algorithm that always sells on the next day if the price is higher than the buy day.

Solution

1. Step 1: Understand problem constraints

   The problem requires exactly one buy and one sell, with the sell day after the buy day, maximizing profit.

2. Step 2: Identify optimal approach

   Tracking the minimum price so far and updating max profit in one pass ensures O(n) time and O(1) space, guaranteeing optimality.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   One pass with min price tracking is classic and efficient [OK]

Hint: Track min price and max profit in one pass [OK]

Common Mistakes:

• Using nested loops causes TLE on large inputs
• Greedy selling next day misses better future profits
• DP table wastes space for this simple case

2. You are given a list of daily stock prices and want to maximize profit by buying and selling any number of times, but you cannot hold more than one stock at a time. Which algorithmic approach guarantees the optimal solution for this problem?

easy

A. Greedy approach summing all positive price differences between consecutive days

B. Dynamic Programming using a state machine to track holding and not holding states

C. Pure brute force recursion exploring all buy/sell combinations without memoization

D. Divide and conquer by splitting the price array and merging results

Solution

1. Step 1: Understand problem constraints

   The problem allows unlimited transactions but only one stock can be held at a time.

2. Step 2: Identify suitable algorithm

   For this problem, the greedy approach of summing all positive price differences between consecutive days guarantees the optimal profit. This works because any profitable transaction can be decomposed into these increments.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Greedy summing positive differences is optimal for unlimited transactions without cooldown or fees [OK]

Hint: Sum all positive price differences between consecutive days to get max profit [OK]

Common Mistakes:

• Assuming DP is required when greedy suffices
• Using brute force without memoization
• Trying divide and conquer without state tracking

3. Consider the following code snippet implementing the optimal Jump Game solution. What is the value of maxReach after the third iteration (i=2) when input is [2,0,2]?

easy

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Trace iterations for input [2,0,2]

   i=0: maxReach = max(0, 0+2) = 2; i=1: maxReach = max(2, 1+0) = 2; i=2: maxReach = max(2, 2+2) = 4

2. Step 2: Identify maxReach after third iteration (i=2)

   After i=2, maxReach is 4, which is the value after the third iteration completes.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   maxReach updated to 4 after i=2 [OK]

Hint: Track maxReach updates carefully at each iteration [OK]

Common Mistakes:

• Off-by-one error in iteration count
• Confusing maxReach before vs after update
• Ignoring early return conditions

4. What is the time and space complexity of the optimal dynamic programming solution for the unlimited transactions stock problem using the space-optimized state machine approach?

medium

A. Time: O(n^2), Space: O(n) due to nested loops and dp array

B. Time: O(n), Space: O(1) by tracking only current holding and not holding states

C. Time: O(n), Space: O(n) because of recursion stack in memoization

D. Time: O(2^n), Space: O(n) due to exponential recursion without memoization

Solution

1. Step 1: Analyze time complexity

   The algorithm iterates once over the price list (length n), performing constant time operations per iteration -> O(n) time.

2. Step 2: Analyze space complexity

   Only two variables track states (holding, not_holding), no arrays or recursion stack -> O(1) space.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Single pass with constant state variables confirms O(n) time and O(1) space [OK]

Hint: Space optimized DP uses constant space, not arrays or recursion [OK]

Common Mistakes:

• Confusing recursion stack space with iterative DP
• Assuming DP always uses O(n) space
• Mistaking nested loops for this linear solution

5. Suppose the House Robber II problem is modified so that you can rob the same house multiple times (i.e., unlimited reuse), but still cannot rob two adjacent houses in the same night. Which of the following approaches correctly adapts the solution to this variant?

hard

A. Since houses can be robbed multiple times, simply sum all house values ignoring adjacency

B. Modify rob_linear to consider robbing the current house multiple times by adding nums[i] repeatedly in the recurrence

C. Use the same DP but allow adding nums[i] multiple times in rob_linear without changing adjacency checks

D. Use a DP that tracks states with and without robbing the current house, allowing reuse but skipping adjacent houses, effectively a modified linear DP with state transitions

Solution

1. Step 1: Understand the reuse constraint

   Robbing the same house multiple times requires tracking states to ensure no two adjacent houses are robbed in the same iteration.

2. Step 2: Modify DP to track states

   DP must track whether the previous house was robbed to prevent adjacency, allowing multiple robberies over time but not consecutively.

3. Step 3: Reject naive summation or repeated addition

   Simply adding nums[i] multiple times or ignoring adjacency breaks problem constraints.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Stateful DP with adjacency checks handles reuse correctly [OK]

Hint: Track rob/no-rob states to handle reuse with adjacency [OK]

Common Mistakes:

• Ignoring adjacency when reusing houses
• Trying to add nums[i] repeatedly without state
• Summing all values ignoring constraints