[{"_1":2,"_3":-5,"_4":-5},"loaderData",{"_5":6},"actionData","errors","routes/blog-tag",{"_7":8,"_9":10},"tag",{"_31":88,"_73":89,"_35":90},"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",84,"title","Dynamic Programming","slug","dsa-cheatsheet-part-13-dp","excerpt","Visual guide to DP: solving problems by breaking into subproblems. Watch the DP table fill with optimal solutions.","# Dynamic Programming\n\n## 📋 Quick Reference\n\n| Property | Value |\n|----------|-------|\n| **Type** | Optimization technique |\n| **Key Idea** | Break into subproblems, store results, avoid recomputation |\n| **Requirements** | Optimal substructure + overlapping subproblems |\n| **Approaches** | Top-down (memoization) or Bottom-up (tabulation) |\n| **Best For** | Optimization problems, counting problems |\n\n**One-liner**: *Solve complex problems by breaking into overlapping subproblems and caching results.*\n\n---\n\n## 🎮 Interactive Visualizer\n\nWatch how DP builds solutions from smaller subproblems:\n\n```visualizer-dp\nshowControls: true\nshowCode: true\n```\n\n**Try these operations:**\n1. See Fibonacci with memoization - avoid redundant calls\n2. Watch the DP table fill for knapsack\n3. Observe how subproblems build on each other\n4. Compare top-down vs bottom-up approaches\n\n---\n\n## 🔧 Classic Problems\n\n### Fibonacci (Top-Down with Memoization)\n\n```java\npublic int fibMemo(int n) {\n return fibMemo(n, new HashMap<>());\n}\n\nprivate int fibMemo(int n, Map memo) {\n if (n <= 1) return n;\n if (memo.containsKey(n)) return memo.get(n);\n\n int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);\n memo.put(n, result);\n return result;\n}\n```\n\n### Fibonacci (Bottom-Up with Tabulation)\n\n```java\npublic int fibTab(int n) {\n if (n <= 1) return n;\n\n int[] dp = new int[n + 1];\n dp[0] = 0;\n dp[1] = 1;\n\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 (O(1) instead of O(n))\npublic int fibOptimized(int n) {\n if (n <= 1) return n;\n\n int prev2 = 0, prev1 = 1;\n for (int i = 2; i <= n; i++) {\n int curr = prev1 + prev2;\n prev2 = prev1;\n prev1 = curr;\n }\n\n return prev1;\n}\n```\n\n### 0/1 Knapsack\n\n```java\npublic int knapsack(int[] weights, int[] values, int capacity) {\n int n = weights.length;\n int[][] dp = new int[n + 1][capacity + 1];\n\n for (int i = 1; i <= n; i++) {\n for (int w = 0; w <= capacity; w++) {\n // Don't take item i\n dp[i][w] = dp[i - 1][w];\n\n // Take item i (if it fits)\n if (weights[i - 1] <= w) {\n dp[i][w] = Math.max(dp[i][w],\n dp[i - 1][w - weights[i - 1]] + values[i - 1]);\n }\n }\n }\n\n return dp[n][capacity];\n}\n```\n\n### Longest Common Subsequence (LCS)\n\n```java\npublic int lcs(String s1, String s2) {\n int m = s1.length(), n = s2.length();\n int[][] dp = new int[m + 1][n + 1];\n\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (s1.charAt(i - 1) == s2.charAt(j - 1)) {\n dp[i][j] = dp[i - 1][j - 1] + 1;\n } else {\n dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n }\n }\n }\n\n return dp[m][n];\n}\n```\n\n### Coin Change (Minimum Coins)\n\n```java\npublic int coinChange(int[] coins, int amount) {\n int[] dp = new int[amount + 1];\n Arrays.fill(dp, amount + 1); // \"Infinity\"\n dp[0] = 0;\n\n for (int i = 1; i <= amount; i++) {\n for (int coin : coins) {\n if (coin <= i) {\n dp[i] = Math.min(dp[i], dp[i - coin] + 1);\n }\n }\n }\n\n return dp[amount] > amount ? -1 : dp[amount];\n}\n```\n\n---\n\n## 📊 DP Patterns\n\n### Pattern 1: Linear DP\n\n```java\n// State: dp[i] depends on dp[i-1], dp[i-2], etc.\n// Examples: Fibonacci, Climbing Stairs, House Robber\n\n// House Robber\npublic int rob(int[] nums) {\n int prev2 = 0, prev1 = 0;\n for (int num : nums) {\n int curr = Math.max(prev1, prev2 + num);\n prev2 = prev1;\n prev1 = curr;\n }\n return prev1;\n}\n```\n\n### Pattern 2: 2D Grid DP\n\n```java\n// State: dp[i][j] depends on dp[i-1][j], dp[i][j-1]\n// Examples: Unique Paths, Minimum Path Sum, LCS\n\n// Unique Paths\npublic int uniquePaths(int m, int n) {\n int[][] dp = new int[m][n];\n\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 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\n### Pattern 3: String DP\n\n```java\n// State: dp[i][j] for substrings s1[0..i] and s2[0..j]\n// Examples: LCS, Edit Distance, Palindrome\n\n// Edit Distance\npublic int editDistance(String s1, String s2) {\n int m = s1.length(), n = s2.length();\n int[][] dp = new int[m + 1][n + 1];\n\n for (int i = 0; i <= m; i++) dp[i][0] = i;\n for (int j = 0; j <= n; j++) dp[0][j] = j;\n\n for (int i = 1; i <= m; i++) {\n for (int j = 1; j <= n; j++) {\n if (s1.charAt(i-1) == s2.charAt(j-1)) {\n dp[i][j] = dp[i-1][j-1];\n } else {\n dp[i][j] = 1 + Math.min(dp[i-1][j-1],\n Math.min(dp[i-1][j], dp[i][j-1]));\n }\n }\n }\n\n return dp[m][n];\n}\n```\n\n### Pattern 4: Interval DP\n\n```java\n// State: dp[i][j] for interval [i, j]\n// Examples: Matrix Chain Multiplication, Burst Balloons\n\n// Matrix Chain Multiplication\npublic int matrixChainOrder(int[] dims) {\n int n = dims.length - 1;\n int[][] dp = new int[n][n];\n\n for (int len = 2; len <= n; len++) {\n for (int i = 0; i < n - len + 1; i++) {\n int j = i + len - 1;\n dp[i][j] = Integer.MAX_VALUE;\n\n for (int k = i; k < j; k++) {\n int cost = dp[i][k] + dp[k+1][j]\n + dims[i] * dims[k+1] * dims[j+1];\n dp[i][j] = Math.min(dp[i][j], cost);\n }\n }\n }\n\n return dp[0][n-1];\n}\n```\n\n---\n\n## ✅ When to Use DP\n\n### Good Indicators\n\n- **\"Minimum/maximum\"** - optimization problem\n- **\"Count the ways\"** - counting problem\n- **\"Can it be done?\"** - feasibility problem\n- **Overlapping subproblems** - same states computed repeatedly\n- **Optimal substructure** - optimal solution uses optimal sub-solutions\n\n### Common DP Problems\n\n| Category | Examples |\n|----------|----------|\n| Sequence | Fibonacci, Climbing Stairs, LIS |\n| Grid | Unique Paths, Minimum Path Sum |\n| String | LCS, Edit Distance, Palindrome |\n| Knapsack | 0/1 Knapsack, Coin Change |\n| Interval | Matrix Chain, Burst Balloons |\n| Tree | Tree DP, Binary Tree Maximum Path |\n\n---\n\n## 🔄 Top-Down vs Bottom-Up\n\n| Aspect | Top-Down (Memoization) | Bottom-Up (Tabulation) |\n|--------|------------------------|------------------------|\n| Direction | Start from problem, recurse | Start from base cases |\n| Computation | Only needed subproblems | All subproblems |\n| Stack | Recursion overhead | Iterative |\n| Debugging | Easier to understand | Easier to trace |\n| Space Optimization | Harder | Often possible |\n\n```java\n// Top-down: Recursive + cache\nint solve(int n, int[] memo) {\n if (baseCase) return value;\n if (memo[n] != -1) return memo[n];\n return memo[n] = /* recurrence */;\n}\n\n// Bottom-up: Iterative + array\nint solve(int n) {\n int[] dp = new int[n + 1];\n dp[0] = baseValue;\n for (int i = 1; i <= n; i++) {\n dp[i] = /* recurrence using dp[= 2) dp[i] += dp[i-2];\n```\n\n### 4. Not Recognizing DP Problem\n\n```java\n// ❌ Brute force exponential solution\n// Recursion without memoization\n\n// ✅ Look for patterns:\n// - Overlapping subproblems (same function calls)\n// - Optimal substructure (optimal uses optimal sub-solutions)\n```\n\n---\n\n## 🎤 Interview Tips\n\n**Q: How do you identify a DP problem?**\n\n> Look for optimization/counting problems with overlapping subproblems. If you see the same recursive calls being made, it's likely DP. Common patterns: \"minimum/maximum\", \"count ways\", \"is it possible\".\n\n**Q: Top-down or bottom-up?**\n\n> Top-down is often easier to derive (just add memoization to recursion). Bottom-up can be more efficient (no recursion overhead) and easier to optimize space. Start with top-down, convert to bottom-up if needed.\n\n**Q: How do you derive the recurrence?**\n\n> Think about the last decision/step. What choices lead to the current state? Express the answer in terms of smaller subproblems. Draw decision trees if stuck.\n\n**Q: How do you optimize DP space?**\n\n> If dp[i] only depends on dp[i-1] and dp[i-2], you only need two variables, not an array. For 2D DP, if you only look at the previous row, use a 1D array.\n\n---\n\n## 📚 Series Navigation\n\n**Previous**: [Part 12: Dijkstra's Algorithm](dsa-cheatsheet-part-12-dijkstra)\n\n**Next**: [Part 14: ConcurrentHashMap](dsa-cheatsheet-part-14-concurrenthashmap)\n\n---\n\n**Visualizer**: `DP` from `@tomaszjarosz/react-visualizers`\n","featuredImage","isPublished","isFeatured","subscriptionType","BASIC","publishedAt","2026-06-10T07:19:25.710945Z","createdAt","2026-06-10T07:19:25.711190Z","updatedAt","2026-06-16T21:26:56.086200Z","readingTimeMinutes",6,"estimatedReadingTime","authorId",3,"authorUsername","tomasz_main","categoryName","Algorithms","readingTime","seriesId",4,"seriesOrder",13,"author",{"_31":55,"_97":57,"_98":99,"_100":101,"_102":-5,"_103":-5,"_104":-5,"_105":-5,"_106":-5},"category",{"_31":52,"_73":59,"_35":94,"_76":95,"_96":-5},"tags",[79,80,81,82],"series",{"_31":62,"_73":74,"_35":75,"_76":77,"_78":23},"name","Interactive Data Structures & Algorithms","dsa-visualized-cheatsheet","description","A concise, visual reference for essential data structures and algorithms. Each article features an interactive visualizer showing how the structure/algorithm works step-by-step, along with complexity analysis, use cases, and quick reference code. Perfect for interview prep, quick review, or learning by visualization.","isActive",{"_31":91,"_73":92,"_35":93},{"_31":88,"_73":89,"_35":90},{"_31":86,"_73":34,"_35":87},{"_31":83,"_73":84,"_35":85},127,"Memoization","memoization",184,"dynamic-programming",281,"Dp","dp",278,"Algorithm","algorithm","algorithms","Category for Algorithms","colorHex","username","firstName","Tomasz","lastName","Jarosz","profilePicture","bio","website","githubUrl","linkedinUrl"]