[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":83,"_73":84,"_35":85},"articles",{"_11":12,"_13":14,"_15":16,"_17":16,"_18":19,"_20":21,"_22":23,"_24":23,"_25":16,"_26":27},"content",[30],"pageable",{"_28":21,"_29":19},"totalElements",1,"totalPages","size",10,"number",0,"first",true,"last","numberOfElements","empty",false,"page_number","page_size",{"_31":32,"_33":34,"_35":36,"_37":38,"_11":39,"_40":-5,"_41":23,"_42":27,"_43":44,"_45":46,"_47":48,"_49":50,"_51":52,"_53":52,"_54":55,"_56":57,"_58":59,"_60":52,"_61":62,"_63":64,"_65":66,"_67":68,"_69":70,"_71":72},"id",43,"title","Dynamic Programming Foundations","slug","algorithms-part-16-dynamic-programming-foundations","excerpt","Understand optimal substructure and overlapping subproblems. Learn memoization vs tabulation and how to define DP states correctly.","# Part 16: Dynamic Programming Foundations - From Recursion to Optimization\n\n## 📋 At a Glance\n\n| Aspect | Details |\n|--------|---------|\n| Time to Read | 35 minutes |\n| Prerequisites | Part 2 (Recursion), Part 3 (Divide & Conquer) |\n| Key Concepts | Optimal Substructure, Overlapping Subproblems, Memoization, Tabulation |\n| Difficulty | ⭐⭐⭐ (Intermediate) |\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ DYNAMIC PROGRAMMING OVERVIEW │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ TWO KEY PROPERTIES │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ │ │\n│ │ 1. OPTIMAL SUBSTRUCTURE │ │\n│ │ Optimal solution contains optimal sub-solutions │ │\n│ │ │ │\n│ │ fib(5) = fib(4) + fib(3) │ │\n│ │ ↓ ↓ │ │\n│ │ optimal optimal │ │\n│ │ │ │\n│ │ 2. OVERLAPPING SUBPROBLEMS │ │\n│ │ Same subproblems solved multiple times │ │\n│ │ │ │\n│ │ fib(5) │ │\n│ │ / \\ │ │\n│ │ fib(4) fib(3) ← computed twice! │ │\n│ │ / \\ / \\ │ │\n│ │ fib(3) fib(2) fib(2) fib(1) │ │\n│ │ │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ TWO APPROACHES │\n│ ┌──────────────────────┐ ┌──────────────────────┐ │\n│ │ TOP-DOWN │ │ BOTTOM-UP │ │\n│ │ (Memoization) │ │ (Tabulation) │ │\n│ │ │ │ │ │\n│ │ Start from problem │ │ Start from base │ │\n│ │ Recurse down │ │ Build up to answer │ │\n│ │ Cache results │ │ Fill table │ │\n│ │ │ │ │ │\n│ │ Natural, lazy │ │ Iterative, complete │ │\n│ └──────────────────────┘ └──────────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🎯 What You'll Learn\n\nAfter completing this article, you will be able to:\n\n1. **Recognize DP problems**: Identify optimal substructure and overlapping subproblems\n2. **Choose the right approach**: Decide between memoization and tabulation\n3. **Define states correctly**: The hardest and most important skill\n4. **Write transitions**: Convert recurrence relations to code\n5. **Optimize space**: Reduce memory when only recent states matter\n\n---\n\n## 🔥 Production Story: The Shipping Cost Disaster\n\nA logistics company needed to calculate optimal shipping routes. Their system was timing out during peak hours.\n\n### The Problem\n\n```java\n// ❌ Naive recursive solution - exponential time\npublic class ShippingCalculator {\n public int minCost(int[] warehouses, int destination) {\n return minCostRecursive(warehouses, 0, destination);\n }\n\n private int minCostRecursive(int[] warehouses, int current, int dest) {\n if (current == dest) return 0;\n if (current > dest) return Integer.MAX_VALUE;\n\n int minCost = Integer.MAX_VALUE;\n for (int jump = 1; jump <= 3; jump++) { // Can move 1-3 warehouses\n int next = current + jump;\n if (next < warehouses.length) {\n int cost = minCostRecursive(warehouses, next, dest);\n if (cost != Integer.MAX_VALUE) {\n minCost = Math.min(minCost, warehouses[next] + cost);\n }\n }\n }\n return minCost;\n }\n}\n\n// With 50 warehouses: 3^50 potential calls = TIMEOUT\n```\n\n### The Investigation\n\nThe team traced the call tree:\n\n```\nminCost(0, 50)\n├── minCost(1, 50)\n│ ├── minCost(2, 50)\n│ │ ├── minCost(3, 50) ← Called from multiple paths\n│ │ ├── minCost(4, 50)\n│ │ └── minCost(5, 50)\n│ ├── minCost(3, 50) ← Same call again!\n│ └── minCost(4, 50) ← Same call again!\n├── minCost(2, 50) ← Same call again!\n└── minCost(3, 50) ← Same call again!\n\nExponential explosion of redundant computations!\n```\n\n### The Solution\n\n```java\n// ✅ DP solution with memoization - O(n) time\npublic class OptimizedShippingCalculator {\n private int[] memo;\n\n public int minCost(int[] warehouses, int destination) {\n memo = new int[warehouses.length];\n Arrays.fill(memo, -1);\n return minCostDP(warehouses, 0, destination);\n }\n\n private int minCostDP(int[] warehouses, int current, int dest) {\n if (current == dest) return 0;\n if (current > dest) return Integer.MAX_VALUE;\n\n // Check cache first\n if (memo[current] != -1) return memo[current];\n\n int minCost = Integer.MAX_VALUE;\n for (int jump = 1; jump <= 3; jump++) {\n int next = current + jump;\n if (next < warehouses.length) {\n int cost = minCostDP(warehouses, next, dest);\n if (cost != Integer.MAX_VALUE) {\n minCost = Math.min(minCost, warehouses[next] + cost);\n }\n }\n }\n\n memo[current] = minCost; // Cache result\n return minCost;\n }\n}\n\n// ✅ Even better: Bottom-up tabulation\npublic int minCostTabulation(int[] warehouses, int destination) {\n int[] dp = new int[destination + 1];\n Arrays.fill(dp, Integer.MAX_VALUE);\n dp[destination] = 0;\n\n for (int i = destination - 1; i >= 0; i--) {\n for (int jump = 1; jump <= 3 && i + jump <= destination; jump++) {\n if (dp[i + jump] != Integer.MAX_VALUE) {\n dp[i] = Math.min(dp[i], warehouses[i + jump] + dp[i + jump]);\n }\n }\n }\n\n return dp[0];\n}\n```\n\n### The Impact\n\n| Metric | Before | After |\n|--------|--------|-------|\n| 50 warehouses | Timeout (>30s) | 0.1ms |\n| 500 warehouses | Impossible | 1ms |\n| Peak hour failures | 2,400/day | 0 |\n| Route optimization | Disabled | Real-time |\n\n---\n\n## 🧠 Mental Model: The Notebook Approach\n\nThink of DP as a student solving math problems with a notebook:\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ THE NOTEBOOK APPROACH │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ WITHOUT NOTEBOOK (Naive Recursion) │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ │ │\n│ │ Teacher: \"What's fib(5)?\" │ │\n│ │ Student: \"I need fib(4) and fib(3)...\" │ │\n│ │ │ │\n│ │ Teacher: \"What's fib(4)?\" │ │\n│ │ Student: \"I need fib(3) and fib(2)...\" │ │\n│ │ │ │\n│ │ Teacher: \"What's fib(3)?\" ← Asked AGAIN! │ │\n│ │ Student: Recalculates from scratch... │ │\n│ │ │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n│ WITH NOTEBOOK (Memoization) │\n│ ┌─────────────────────────────────────────────────────────┐ │\n│ │ │ │\n│ │ ┌─────────────────┐ │ │\n│ │ │ NOTEBOOK │ │ │\n│ │ │ fib(1) = 1 │ │ │\n│ │ │ fib(2) = 1 │ │ │\n│ │ │ fib(3) = 2 ✓ │ ← Already calculated! │ │ \n│ │ │ fib(4) = 3 │ │ │\n│ │ │ fib(5) = 5 │ │ │\n│ │ └─────────────────┘ │ │\n│ │ │ │\n│ │ Teacher: \"What's fib(3)?\" │ │\n│ │ Student: *checks notebook* \"It's 2!\" │ │\n│ │ │ │\n│ └─────────────────────────────────────────────────────────┘ │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n**Key insight**: DP = Recursion + Memory\n\n---\n\n## 🔬 Deep Dive: Recognizing DP Problems\n\n### The Two Properties\n\n**1. Optimal Substructure**\n\nThe optimal solution to the problem contains optimal solutions to subproblems.\n\n```java\n// Example: Shortest path\n// If A → B → C is the shortest path from A to C,\n// then A → B must be the shortest path from A to B\n\n// Example: Longest Increasing Subsequence\n// LIS ending at position i = 1 + max(LIS ending at j) for all j < i where arr[j] < arr[i]\n```\n\n**2. Overlapping Subproblems**\n\nThe same subproblems are solved multiple times.\n\n```java\n// Fibonacci call tree shows massive overlap:\n//\n// fib(6)\n// / \\\n// fib(5) fib(4) ← fib(4) computed twice\n// / \\ / \\\n// fib(4) fib(3) fib(3) fib(2) ← fib(3) computed 3 times\n// / \\\n// fib(3) fib(2) ← fib(2) computed 5 times\n```\n\n### When to Use DP vs Other Techniques\n\n```\n┌─────────────────────────────────────────────────────────────────┐\n│ TECHNIQUE SELECTION │\n├─────────────────────────────────────────────────────────────────┤\n│ │\n│ Problem has optimal substructure? │\n│ ├── NO → Not suitable for DP │\n│ └── YES → Check for overlapping subproblems │\n│ ├── NO → Use Divide & Conquer (no caching needed) │\n│ └── YES → Use Dynamic Programming │\n│ │\n│ Examples: │\n│ │\n│ MergeSort: Optimal substructure ✓, Overlapping ✗ │\n│ → Divide & Conquer (subproblems are independent) │\n│ │\n│ Fibonacci: Optimal substructure ✓, Overlapping ✓ │\n│ → Dynamic Programming │\n│ │\n│ Greedy problems: Optimal substructure ✓, make local choice │\n│ → Greedy Algorithm (if greedy choice property) │\n│ │\n└─────────────────────────────────────────────────────────────────┘\n```\n\n---\n\n## 🔬 Deep Dive: Memoization (Top-Down)\n\n### The Pattern\n\n```java\npublic class MemoizationTemplate {\n private Map memo = new HashMap<>();\n\n public Result solve(State state) {\n // 1. Base case\n if (isBaseCase(state)) {\n return baseResult(state);\n }\n\n // 2. Check memo\n if (memo.containsKey(state)) {\n return memo.get(state);\n }\n\n // 3. Compute result\n Result result = computeFromSubproblems(state);\n\n // 4. Store in memo\n memo.put(state, result);\n\n return result;\n }\n}\n```\n\n### Fibonacci with Memoization\n\n```java\npublic class FibonacciMemo {\n private long[] memo;\n\n public long fib(int n) {\n memo = new long[n + 1];\n Arrays.fill(memo, -1);\n return fibHelper(n);\n }\n\n private long fibHelper(int n) {\n // Base cases\n if (n <= 1) return n;\n\n // Check memo\n if (memo[n] != -1) return memo[n];\n\n // Compute and store\n memo[n] = fibHelper(n - 1) + fibHelper(n - 2);\n return memo[n];\n }\n}\n```\n\n### Climbing Stairs with Memoization\n\n```java\npublic class ClimbingStairs {\n // You can climb 1 or 2 steps. How many ways to reach top?\n private int[] memo;\n\n public int climbStairs(int n) {\n memo = new int[n + 1];\n Arrays.fill(memo, -1);\n return climb(n);\n }\n\n private int climb(int n) {\n if (n <= 0) return n == 0 ? 1 : 0;\n if (memo[n] != -1) return memo[n];\n\n memo[n] = climb(n - 1) + climb(n - 2);\n return memo[n];\n }\n}\n```\n\n### When to Use Memoization\n\n**Advantages**:\n- Natural translation from recursive thinking\n- Only computes needed subproblems (lazy evaluation)\n- Easier to write initially\n\n**Disadvantages**:\n- Recursion overhead (stack space)\n- Hash map overhead for complex states\n- Risk of stack overflow for deep recursion\n\n---\n\n## 🔬 Deep Dive: Tabulation (Bottom-Up)\n\n### The Pattern\n\n```java\npublic class TabulationTemplate {\n public Result solve(Input input) {\n // 1. Create DP table\n Result[] dp = new Result[size];\n\n // 2. Initialize base cases\n dp[0] = baseCase();\n\n // 3. Fill table in topological order\n for (int i = 1; i < size; i++) {\n dp[i] = computeFromPrevious(dp, i);\n }\n\n // 4. Return answer\n return dp[size - 1];\n }\n}\n```\n\n### Fibonacci with Tabulation\n\n```java\npublic class FibonacciTab {\n public long fib(int n) {\n if (n <= 1) return n;\n\n long[] dp = new long[n + 1];\n\n // Base cases\n dp[0] = 0;\n dp[1] = 1;\n\n // Fill table\n for (int i = 2; i <= n; i++) {\n dp[i] = dp[i - 1] + dp[i - 2];\n }\n\n return dp[n];\n }\n\n // Space-optimized version - O(1) space\n public long fibOptimized(int n) {\n if (n <= 1) return n;\n\n long prev2 = 0, prev1 = 1;\n\n for (int i = 2; i <= n; i++) {\n long current = prev1 + prev2;\n prev2 = prev1;\n prev1 = current;\n }\n\n return prev1;\n }\n}\n```\n\n### Climbing Stairs with Tabulation\n\n```java\npublic class ClimbingStairsTab {\n public int climbStairs(int n) {\n if (n <= 2) return n;\n\n int[] dp = new int[n + 1];\n dp[1] = 1;\n dp[2] = 2;\n\n for (int i = 3; i <= n; i++) {\n dp[i] = dp[i - 1] + dp[i - 2];\n }\n\n return dp[n];\n }\n\n // With k different step sizes\n public int climbStairsK(int n, int[] steps) {\n int[] dp = new int[n + 1];\n dp[0] = 1; // One way to stay at ground\n\n for (int i = 1; i <= n; i++) {\n for (int step : steps) {\n if (i >= step) {\n dp[i] += dp[i - step];\n }\n }\n }\n\n return dp[n];\n }\n}\n```\n\n### When to Use Tabulation\n\n**Advantages**:\n- No recursion overhead\n- Better cache locality\n- Easier to optimize space\n- No stack overflow risk\n\n**Disadvantages**:\n- Must compute ALL subproblems (even unused ones)\n- Need to determine correct order of computation\n- Sometimes harder to visualize\n\n---\n\n## 🔬 Deep Dive: State Definition\n\n### The Most Critical Step\n\nState definition is often the hardest part of DP. The state must:\n1. **Uniquely identify a subproblem**\n2. **Be sufficient to compute the answer**\n3. **Lead to a manageable number of states**\n\n### Common State Patterns\n\n```java\n// Pattern 1: Single index\n// dp[i] = answer for first i elements\nint[] dp = new int[n]; // O(n) states\n\n// Pattern 2: Two indices\n// dp[i][j] = answer for subarray [i, j]\nint[][] dp = new int[n][n]; // O(n²) states\n\n// Pattern 3: Index + capacity\n// dp[i][w] = answer using first i items with capacity w\nint[][] dp = new int[n][capacity]; // O(n * capacity) states\n\n// Pattern 4: Index + previous choice\n// dp[i][prev] = answer at position i given previous choice\nint[][] dp = new int[n][choices]; // O(n * choices) states\n\n// Pattern 5: Bitmask\n// dp[mask] = answer when selected items represented by mask\nint[] dp = new int[1 << n]; // O(2^n) states\n```\n\n### Example: House Robber\n\n**Problem**: Rob houses for maximum money, can't rob adjacent houses.\n\n```java\npublic class HouseRobber {\n // State: dp[i] = max money robbing houses 0..i\n\n public int rob(int[] nums) {\n if (nums.length == 0) return 0;\n if (nums.length == 1) return nums[0];\n\n int[] dp = new int[nums.length];\n\n // Base cases\n dp[0] = nums[0];\n dp[1] = Math.max(nums[0], nums[1]);\n\n // Transition: either rob house i (skip i-1) or don't rob i\n for (int i = 2; i < nums.length; i++) {\n dp[i] = Math.max(\n dp[i - 1], // Don't rob house i\n dp[i - 2] + nums[i] // Rob house i\n );\n }\n\n return dp[nums.length - 1];\n }\n\n // Space optimized\n public int robOptimized(int[] nums) {\n if (nums.length == 0) return 0;\n\n int prev2 = 0; // dp[i-2]\n int prev1 = 0; // dp[i-1]\n\n for (int num : nums) {\n int current = Math.max(prev1, prev2 + num);\n prev2 = prev1;\n prev1 = current;\n }\n\n return prev1;\n }\n}\n```\n\n### Example: Coin Change\n\n**Problem**: Minimum coins to make amount.\n\n```java\npublic class CoinChange {\n // State: dp[amount] = minimum coins to make this amount\n\n public int coinChange(int[] coins, int amount) {\n int[] dp = new int[amount + 1];\n Arrays.fill(dp, amount + 1); // \"Infinity\"\n dp[0] = 0; // 0 coins for amount 0\n\n for (int a = 1; a <= amount; a++) {\n for (int coin : coins) {\n if (coin <= a && dp[a - coin] != amount + 1) {\n dp[a] = Math.min(dp[a], dp[a - coin] + 1);\n }\n }\n }\n\n return dp[amount] > amount ? -1 : dp[amount];\n }\n\n // Count number of ways (different problem!)\n public int coinChangeWays(int[] coins, int amount) {\n int[] dp = new int[amount + 1];\n dp[0] = 1; // One way to make 0\n\n // Process coins in outer loop to avoid counting permutations\n for (int coin : coins) {\n for (int a = coin; a <= amount; a++) {\n dp[a] += dp[a - coin];\n }\n }\n\n return dp[amount];\n }\n}\n```\n\n---\n\n## 🔬 Deep Dive: Writing Recurrence Relations\n\n### The Formula Approach\n\n1. **Define what dp[state] represents**\n2. **Identify choices at each state**\n3. **Write recurrence based on choices**\n4. **Identify base cases**\n\n### Example: Minimum Path Sum\n\n```java\npublic class MinPathSum {\n // dp[i][j] = minimum sum to reach cell (i, j) from (0, 0)\n\n public int minPathSum(int[][] grid) {\n int m = grid.length, n = grid[0].length;\n int[][] dp = new int[m][n];\n\n // Base case: starting cell\n dp[0][0] = grid[0][0];\n\n // Fill first row (can only come from left)\n for (int j = 1; j < n; j++) {\n dp[0][j] = dp[0][j - 1] + grid[0][j];\n }\n\n // Fill first column (can only come from top)\n for (int i = 1; i < m; i++) {\n dp[i][0] = dp[i - 1][0] + grid[i][0];\n }\n\n // Fill rest (can come from left or top)\n for (int i = 1; i < m; i++) {\n for (int j = 1; j < n; j++) {\n dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];\n }\n }\n\n return dp[m - 1][n - 1];\n }\n\n // Recurrence relation:\n // dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])\n // Base: dp[0][0] = grid[0][0]\n}\n```\n\n### Example: Unique Paths\n\n```java\npublic class UniquePaths {\n // dp[i][j] = number of unique paths to reach (i, j)\n\n public int uniquePaths(int m, int n) {\n int[][] dp = new int[m][n];\n\n // Base: first row and column have only one path\n for (int i = 0; i < m; i++) dp[i][0] = 1;\n for (int j = 0; j < n; j++) dp[0][j] = 1;\n\n // Recurrence: paths = from_left + from_top\n for (int i = 1; i < m; i++) {\n for (int j = 1; j < n; j++) {\n dp[i][j] = dp[i - 1][j] + dp[i][j - 1];\n }\n }\n\n return dp[m - 1][n - 1];\n }\n\n // With obstacles\n public int uniquePathsWithObstacles(int[][] grid) {\n int m = grid.length, n = grid[0].length;\n int[][] dp = new int[m][n];\n\n // Handle obstacles in base cases\n for (int i = 0; i < m && grid[i][0] == 0; i++) dp[i][0] = 1;\n for (int j = 0; j < n && grid[0][j] == 0; j++) dp[0][j] = 1;\n\n for (int i = 1; i < m; i++) {\n for (int j = 1; j < n; j++) {\n if (grid[i][j] == 0) {\n dp[i][j] = dp[i - 1][j] + dp[i][j - 1];\n }\n }\n }\n\n return dp[m - 1][n - 1];\n }\n}\n```\n\n---\n\n## ⚠️ Common Mistakes\n\n### Mistake 1: Wrong Base Case\n\n```java\n// ❌ WRONG: Missing or incorrect base case\npublic int fib(int n) {\n int[] dp = new int[n + 1];\n // Forgot dp[0] = 0, dp[1] = 1\n for (int i = 2; i <= n; i++) {\n dp[i] = dp[i-1] + dp[i-2]; // Uses uninitialized values!\n }\n return dp[n];\n}\n\n// ✅ CORRECT: Explicit base cases\npublic int fib(int n) {\n if (n <= 1) return n;\n int[] dp = new int[n + 1];\n dp[0] = 0;\n dp[1] = 1;\n for (int i = 2; i <= n; i++) {\n dp[i] = dp[i-1] + dp[i-2];\n }\n return dp[n];\n}\n```\n\n---\n\n### Mistake 2: Wrong Iteration Order\n\n```java\n// ❌ WRONG: Computing before dependencies are ready\nfor (int i = 0; i < n; i++) {\n dp[i] = dp[i + 1] + dp[i + 2]; // dp[i+1], dp[i+2] not computed yet!\n}\n\n// ✅ CORRECT: Process in order so dependencies are ready\nfor (int i = n - 1; i >= 0; i--) {\n dp[i] = dp[i + 1] + dp[i + 2]; // dp[i+1], dp[i+2] already computed\n}\n```\n\n---\n\n### Mistake 3: Off-by-One in Array Size\n\n```java\n// ❌ WRONG: Array too small\nint[] dp = new int[n]; // Indices 0 to n-1\ndp[n] = value; // ArrayIndexOutOfBoundsException!\n\n// ✅ CORRECT: Size accounts for index n\nint[] dp = new int[n + 1]; // Indices 0 to n\ndp[n] = value; // OK\n```\n\n---\n\n### Mistake 4: Modifying Memo During Recursion\n\n```java\n// ❌ WRONG: Incorrect memoization\nprivate int solve(int i) {\n if (memo[i] != -1) return memo[i];\n\n int result = 0;\n for (int j = 0; j < i; j++) {\n memo[i] = solve(j); // Bug: overwriting memo[i] in loop!\n result += memo[i];\n }\n memo[i] = result;\n return result;\n}\n\n// ✅ CORRECT: Only store final result\nprivate int solve(int i) {\n if (memo[i] != -1) return memo[i];\n\n int result = 0;\n for (int j = 0; j < i; j++) {\n result += solve(j); // Don't touch memo[i] here\n }\n memo[i] = result; // Store once at the end\n return result;\n}\n```\n\n---\n\n## 🐛 Debug This: Incorrect State Transition\n\nThis climbing stairs solution has a bug. Can you find it?\n\n```java\npublic class BuggyClimbingStairs {\n // Problem: Climb n stairs, can take 1, 2, or 3 steps at a time\n // Count total number of ways\n\n public int climbStairs(int n) {\n if (n <= 2) return n;\n\n int[] dp = new int[n + 1];\n dp[0] = 1;\n dp[1] = 1;\n dp[2] = 2;\n\n for (int i = 3; i <= n; i++) {\n // BUG IS HERE\n dp[i] = dp[i - 1] + dp[i - 2];\n }\n\n return dp[n];\n }\n}\n```\n\n

🔍 Click to reveal the bug

\n\n**Bug**: The transition doesn't account for 3-step jumps.\n\n```java\n// ❌ BUG: Missing 3-step option\ndp[i] = dp[i - 1] + dp[i - 2];\n\n// ✅ FIX: Include all three step sizes\ndp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];\n```\n\nThe problem states you can take 1, 2, or 3 steps, but the transition only considers 1 and 2 steps.\n\n**Example for n=4**:\n- Bug returns: 5 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)\n- Correct: 7 (adds 1+3, 3+1)\n\n

\n\n---\n\n## 💻 Exercises\n\n### Exercise 1: Jump Game ⭐⭐\n\nGiven array where `nums[i]` is max jump length from position i, determine if you can reach the last index.\n\n```java\npublic boolean canJump(int[] nums) {\n // dp[i] = true if can reach index i\n // Your implementation\n}\n```\n\n---\n\n### Exercise 2: Decode Ways ⭐⭐\n\nCount ways to decode a digit string into letters (A=1, B=2, ..., Z=26).\n\n```java\npublic int numDecodings(String s) {\n // dp[i] = number of ways to decode s[0..i-1]\n // Your implementation\n}\n```\n\n**Example**: \"226\" → 3 ways: \"BZ\" (2,26), \"VF\" (22,6), \"BBF\" (2,2,6)\n\n---\n\n### Exercise 3: Maximum Subarray ⭐⭐\n\nFind contiguous subarray with largest sum (Kadane's algorithm as DP).\n\n```java\npublic int maxSubArray(int[] nums) {\n // dp[i] = max sum ending at index i\n // Your implementation\n}\n```\n\n---\n\n### Exercise 4: Word Break ⭐⭐⭐\n\nGiven string s and dictionary, determine if s can be segmented into dictionary words.\n\n```java\npublic boolean wordBreak(String s, List wordDict) {\n // dp[i] = true if s[0..i-1] can be segmented\n // Your implementation\n}\n```\n\n---\n\n### Exercise 5: Palindrome Partitioning ⭐⭐⭐⭐\n\nFind minimum cuts to partition string into palindromes.\n\n```java\npublic int minCut(String s) {\n // dp[i] = min cuts for s[0..i-1]\n // Hint: precompute isPalindrome[i][j]\n // Your implementation\n}\n```\n\n---\n\n## 🎤 Interview Questions\n\n### Q1: \"How do you decide between memoization and tabulation?\"\n\n**Answer**:\n\n| Factor | Memoization | Tabulation |\n|--------|-------------|------------|\n| **Ease of implementation** | Easier (natural recursion) | Requires understanding order |\n| **Subproblems computed** | Only needed ones | All subproblems |\n| **Stack space** | O(recursion depth) | O(1) extra |\n| **Cache performance** | Worse (scattered access) | Better (sequential) |\n| **Space optimization** | Harder | Easier |\n\n**My approach**:\n1. Start with memoization for quick solution\n2. Convert to tabulation if needed for performance\n3. Optimize space if only recent states matter\n\n---\n\n### Q2: \"Walk me through solving a DP problem.\"\n\n**Answer**: I use a systematic 5-step approach:\n\n```\nStep 1: RECOGNIZE\n- Does it have optimal substructure?\n- Are there overlapping subproblems?\n- Can I solve smaller versions first?\n\nStep 2: DEFINE STATE\n- What information do I need to uniquely identify a subproblem?\n- What does dp[state] represent?\n\nStep 3: WRITE RECURRENCE\n- What choices do I have at each state?\n- How do I combine subproblem solutions?\n\nStep 4: IDENTIFY BASE CASES\n- What are the smallest subproblems?\n- What are their answers?\n\nStep 5: DETERMINE ORDER\n- Which subproblems depend on which?\n- Fill table in correct order\n```\n\n---\n\n### Q3: \"How would you optimize this DP from O(n²) space to O(n)?\"\n\n**Answer**: Look at the recurrence to see which previous states are needed:\n\n```java\n// Original: O(n²) space\nint[][] dp = new int[n][n];\nfor (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n dp[i][j] = dp[i-1][j-1] + dp[i-1][j]; // Only uses row i-1\n }\n}\n\n// Optimized: O(n) space - only keep two rows\nint[] prev = new int[n];\nint[] curr = new int[n];\nfor (int i = 0; i < n; i++) {\n for (int j = 0; j < n; j++) {\n curr[j] = prev[j-1] + prev[j];\n }\n int[] temp = prev;\n prev = curr;\n curr = temp;\n}\n\n// Further optimized: single row with careful ordering\nint[] dp = new int[n];\nfor (int i = 0; i < n; i++) {\n for (int j = n-1; j >= 0; j--) { // Reverse to not overwrite needed values\n dp[j] = dp[j-1] + dp[j];\n }\n}\n```\n\n---\n\n### Q4: \"What's the difference between DP and greedy?\"\n\n**Answer**:\n\n```\nDynamic Programming:\n- Considers ALL choices at each step\n- Guaranteed optimal solution\n- Higher time complexity\n- Example: 0/1 Knapsack\n\nGreedy:\n- Makes LOCALLY optimal choice\n- May not be globally optimal\n- Lower time complexity\n- Example: Fractional Knapsack\n\nWhen greedy works:\n- Greedy choice property: local optimum leads to global optimum\n- Optimal substructure: still needed\n\nExample where greedy fails:\nCoins [1, 3, 4], Amount = 6\nGreedy: 4 + 1 + 1 = 3 coins\nOptimal: 3 + 3 = 2 coins\n```\n\n---\n\n### Q5: \"How do you handle DP problems with multiple constraints?\"\n\n**Answer**: Add dimensions to the state:\n\n```java\n// Single constraint: capacity\nint[] dp = new int[capacity + 1];\n\n// Two constraints: capacity and weight limit\nint[][] dp = new int[capacity + 1][weightLimit + 1];\n\n// Three constraints: use 3D array or encode state\nint[][][] dp = new int[n][capacity + 1][weightLimit + 1];\n\n// Many constraints: bitmask or map\nMap dp = new HashMap<>();\n// where State encodes all constraints\n```\n\n**Example: Knapsack with capacity AND item count limit**:\n\n```java\npublic int knapsack(int[] values, int[] weights, int capacity, int maxItems) {\n // dp[i][w][k] = max value using items 0..i-1 with weight w and k items\n int[][][] dp = new int[values.length + 1][capacity + 1][maxItems + 1];\n\n for (int i = 1; i <= values.length; i++) {\n for (int w = 0; w <= capacity; w++) {\n for (int k = 0; k <= maxItems; k++) {\n // Don't take item i\n dp[i][w][k] = dp[i-1][w][k];\n\n // Take item i (if possible)\n if (w >= weights[i-1] && k >= 1) {\n dp[i][w][k] = Math.max(dp[i][w][k],\n dp[i-1][w - weights[i-1]][k-1] + values[i-1]);\n }\n }\n }\n }\n\n return dp[values.length][capacity][maxItems];\n}\n```\n\n---\n\n## 📋 Quick Reference\n\n### DP Problem Categories\n\n| Category | State | Example |\n|----------|-------|---------|\n| Linear | dp[i] | Climbing stairs, House robber |\n| 2D Grid | dp[i][j] | Unique paths, Min path sum |\n| Interval | dp[i][j] for [i,j] | Matrix chain, Palindrome |\n| Knapsack | dp[i][w] | 0/1 Knapsack, Coin change |\n| String | dp[i][j] | LCS, Edit distance |\n| Bitmask | dp[mask] | TSP, Subset problems |\n\n### Complexity Patterns\n\n```\ndp[n] → O(n) time, O(n) or O(1) space\ndp[n][m] → O(nm) time, O(nm) or O(m) space\ndp[n][n] → O(n²) time, O(n²) or O(n) space\ndp[2^n] → O(2^n) time, O(2^n) space\ndp[n][2^n] → O(n × 2^n) time and space\n```\n\n### Key Code Patterns\n\n```java\n// Memoization template\nif (memo[state] != UNSET) return memo[state];\nresult = compute();\nmemo[state] = result;\nreturn result;\n\n// Tabulation template\ndp[base] = baseValue;\nfor (each state in topological order) {\n dp[state] = combine(dp[dependencies]);\n}\nreturn dp[target];\n\n// Space optimization (when only previous row needed)\nint[] prev = ..., curr = ...;\nfor (...) {\n // compute curr from prev\n swap(prev, curr);\n}\n```\n\n---\n\n## 🔗 What's Next?\n\nIn **Part 17: Classic DP Patterns**, we'll explore:\n- 0/1 Knapsack and variants\n- Longest Common Subsequence (LCS)\n- Longest Increasing Subsequence (LIS)\n- Edit Distance (Levenshtein)\n- Matrix Chain Multiplication\n\n---\n\n## 📅 Review Schedule\n\n| Day | Focus | Time |\n|-----|-------|------|\n| 0 | Full read + exercises 1-2 | 90 min |\n| 1 | Quick Reference review | 10 min |\n| 3 | Implement Fibonacci both ways | 15 min |\n| 7 | Exercises 3-4 | 30 min |\n| 14 | Debug exercise + Exercise 5 | 20 min |\n| 30 | Interview questions | 15 min |\n\n---\n\n**Next**: [Part 17: Classic DP Patterns →](./algorithms-part-17-classic-dp-patterns.md)\n\n**Series**: [Algorithms Compendium Index](./algorithms-part-0-series-overview.md)\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.250296Z","createdAt","2026-06-10T07:19:25.251331Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",20,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",2,"seriesOrder",16,"author",{"_31":55,"_99":57,"_100":101,"_102":103,"_104":-5,"_105":-5,"_106":-5,"_107":-5,"_108":-5},"category",{"_31":95,"_73":59,"_35":96,"_76":97,"_98":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Algorithms Compendium: From Theory to Production","algorithms-compendium","description","A comprehensive 23-part series covering all essential algorithms for Java developers. From foundational concepts like complexity analysis and recursion, through sorting (QuickSort, MergeSort, TimSort), searching (binary search, string matching), graph algorithms (DFS, BFS, Dijkstra, MST), dynamic programming, greedy algorithms, backtracking, to probabilistic data structures (Bloom filters, HyperLogLog) and interview patterns. Includes real production stories, mental models, exercises, and 100+ interview questions.","isActive",{"_31":92,"_73":93,"_35":94},{"_31":89,"_73":90,"_35":91},{"_31":86,"_73":87,"_35":88},{"_31":83,"_73":84,"_35":85},185,"Tabulation","tabulation",186,"Optimal Substructure","optimal-substructure",127,"Memoization","memoization",184,"Dynamic Programming","dynamic-programming",6,"algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]