DP Intuition: Overlapping Subproblems

Dynamic programming is not magic. It is disciplined reuse. When the same question appears many times inside a recursive decision tree, store the answer once and reuse it.

Repeated Work Is the Signal

Naive recursion often branches into the same smaller questions again and again. DP begins when you can name the repeated subproblem clearly: not the whole problem, but the exact state that determines an answer.

Scenario: Pricing Plan Optimization

A subscription platform evaluates ways to apply discounts over a sequence of months. If many choices lead to the same month index and remaining credits, recomputing every suffix is wasteful. Cache the answer for each state.

Same Pattern in Java, Python, and JavaScript

Climbing stairs is the simplest DP: ways(n) depends on ways(n-1) and ways(n-2), and those answers repeat.

import java.util.*;

class ClimbingStairsMemo {
    static int climb(int n) {
        return ways(n, new HashMap<>());
    }

    static int ways(int n, Map<Integer, Integer> memo) {
        if (n <= 2) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int answer = ways(n - 1, memo) + ways(n - 2, memo);
        memo.put(n, answer);
        return answer;
    }
}

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

• Return the number of ways to climb n stairs taking 1 or 2 steps.
• Given cost per step, return the minimum cost to reach the top.
• Count ways to decode a digit string where 1-26 map to letters.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Solved modelInterview Question Solutions

import java.util.*;

class ClimbingStairsMemo {
    static int climb(int n) {
        return ways(n, new HashMap<>());
    }

    static int ways(int n, Map<Integer, Integer> memo) {
        if (n <= 2) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int answer = ways(n - 1, memo) + ways(n - 2, memo);
        memo.put(n, answer);
        return answer;
    }
}

class MinCostClimb { static int minCost(int[] cost) { int two = 0, one = 0; for (int i = 2; i <= cost.length; i++) { int cur = Math.min(one + cost[i - 1], two + cost[i - 2]); two = one; one = cur; } return one; } }

class DecodeWays { static int numDecodings(String s) { int n=s.length(); int[] dp=new int[n+1]; dp[n]=1; for(int i=n-1;i>=0;i--){ if(s.charAt(i)=='0') continue; dp[i]=dp[i+1]; if(i+1<n && Integer.parseInt(s.substring(i,i+2))<=26) dp[i]+=dp[i+2]; } return dp[0]; } }

Solved modelWorked Interview Answer

Solve climbing stairs with memoization and explain why caching changes the cost. The naive recursion repeats ways(n-1), ways(n-2), and lower states many times. Memoization solves each n once, reducing exponential branching to O(n) states.

import java.util.*;

class ClimbingStairsMemo {
    static int climb(int n) {
        return ways(n, new HashMap<>());
    }

    static int ways(int n, Map<Integer, Integer> memo) {
        if (n <= 2) return n;
        if (memo.containsKey(n)) return memo.get(n);
        int answer = ways(n - 1, memo) + ways(n - 2, memo);
        memo.put(n, answer);
        return answer;
    }
}

Hands-on drillTry It Yourself

Failure patternsCommon Mistakes to Avoid

• Calling every recursion DP.
• Not naming the state.
• Caching with an incomplete key.
• Ignoring base cases.
• Using DP when branches never overlap.

Execution guardrailQuick-Start Checklist

• Find repeated subproblems.
• Name state precisely.
• Define recurrence.
• Define base cases.
• Decide memo or table.
• State number of unique states.

Recall drillKnowledge Check

VocabularyKey Terms

Next practiceFurther Reading

• Practice Fibonacci, climbing stairs, min cost climbing stairs, and decode ways.
• Compare recursion tree with memo cache.
• Review recursion before complex DP.