6c:T489,function uniquePathsMemoization(m: number, n: number): number { /** * Count unique paths using memoization (top-down DP). * * Time Complexity: O(m * n) - each cell computed exactly once * Space Complexity: O(m * n) - memo table + O(m + n) recursion stack */ // Memoization cache using Map with string keys const memo = new Map(); function countPaths(row: number, col: number): number { // Base case: Out of bounds if (row < 0 || col < 0) { return 0; } // Base case: Starting cell if (row === 0 && col === 0) { return 1; } // Check memo before computing const key = `${row},${col}`; if (memo.has(key)) { return memo.get(key)!; } // Compute and store in memo const result = countPaths(row - 1, col) + countPaths(row, col - 1); memo.set(key, result); return result; } return countPaths(m - 1, n - 1); } // Now fast even for larger grids console.log(uniquePathsMemoization(23, 12)); // Output: 1935367206d:T56a,def unique_paths_tabulation(m: int, n: int) -> int: """ Count unique paths using tabulation (bottom-up DP). Time Complexity: O(m * n) - visit each cell once Space Complexity: O(m * n) - the DP table """ # Create m x n DP table initialized to 0 dp = [[0] * n for _ in range(m)] # Base case: First row - only one way (keep going right) for j in range(n): dp[0][j] = 1 # Base case: First column - only one way (keep going down) for i in range(m): dp[i][0] = 1 # Fill the rest of the table for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # Answer is in bottom-right corner return dp[m - 1][n - 1] # Example with step-by-step visualization def unique_paths_with_table_print(m: int, n: int) -> int: """Show the filled DP table for understanding.""" dp = [[0] * n for _ in range(m)] for j in range(n): dp[0][j] = 1 for i in range(m): dp[i][0] = 1 for i in range(1, m): for j in range(1, n): dp[i][j] = dp[i - 1][j] + dp[i][j - 1] # Print the table print(" DP Table (number of paths to each cell):") for row in dp: print(" | ".join(f"{x:3}" for x in row)) return dp[m - 1][n - 1] print(f" Answer: {unique_paths_with_table_print(3, 7)}")6e:T617,function uniquePathsTabulation(m: number, n: number): number { /** * Count unique paths using tabulation (bottom-up DP). * * Time Complexity: O(m * n) - visit each cell once * Space Complexity: O(m * n) - the DP table */ // Create m x n DP table initialized to 0 const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0)); // Base case: First row - only one way (keep going right) for (let j = 0; j < n; j++) { dp[0][j] = 1; } // Base case: First column - only one way (keep going down) for (let i = 0; i < m; i++) { dp[i][0] = 1; } // Fill the rest of the table for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } // Answer is in bottom-right corner return dp[m - 1][n - 1]; } // Example with visualization function uniquePathsWithTablePrint(m: number, n: number): number { const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(0)); for (let j = 0; j < n; j++) dp[0][j] = 1; for (let i = 0; i < m; i++) dp[i][0] = 1; for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; } } console.log(" DP Table (number of paths to each cell):"); dp.forEach(row => console.log(row.map(x => x.toString().padStart(3)).join(" | "))); return dp[m - 1][n - 1]; } console.log(` Answer: ${uniquePathsWithTablePrint(3, 7)}`);6f:T5df,def unique_paths_two_rows(m: int, n: int) -> int: """ Space-optimized version using two rows. Time Complexity: O(m * n) Space Complexity: O(n) - only two rows of length n """ # Initialize previous row (all 1s for first row logic) prev_row = [1] * n for i in range(1, m): # Current row starts with 1 (first column always 1) curr_row = [1] * n for j in range(1, n): # dp[i][j] = dp[i-1][j] + dp[i][j-1] # prev_row[j] is dp[i-1][j] (cell above) # curr_row[j-1] is dp[i][j-1] (cell to left) curr_row[j] = prev_row[j] + curr_row[j - 1] # Current becomes previous for next iteration prev_row = curr_row return prev_row[n - 1] def unique_paths_one_row(m: int, n: int) -> int: """ Ultimate space optimization: single row, in-place updates. Time Complexity: O(m * n) Space Complexity: O(n) - single row (or O(min(m,n)) if we optimize further) """ # Single row, all 1s initially dp = [1] * n for i in range(1, m): for j in range(1, n): # Before update: dp[j] contains value from previous row (above) # dp[j-1] already updated in this iteration (left) dp[j] = dp[j] + dp[j - 1] return dp[n - 1] # Verification: All three approaches give same answer print(unique_paths_two_rows(10, 15)) # Output: 817190 print(unique_paths_one_row(10, 15)) # Output: 81719070:T65e,function uniquePathsTwoRows(m: number, n: number): number { /** * Space-optimized version using two rows. * * Time Complexity: O(m * n) * Space Complexity: O(n) - only two rows of length n */ // Initialize previous row (all 1s for first row logic) let prevRow = Array(n).fill(1); for (let i = 1; i < m; i++) { // Current row starts with 1 (first column always 1) const currRow = Array(n).fill(1); for (let j = 1; j < n; j++) { // dp[i][j] = dp[i-1][j] + dp[i][j-1] // prevRow[j] is dp[i-1][j] (cell above) // currRow[j-1] is dp[i][j-1] (cell to left) currRow[j] = prevRow[j] + currRow[j - 1]; } // Current becomes previous for next iteration prevRow = currRow; } return prevRow[n - 1]; } function uniquePathsOneRow(m: number, n: number): number { /** * Ultimate space optimization: single row, in-place updates. * * Time Complexity: O(m * n) * Space Complexity: O(n) - single row */ // Single row, all 1s initially const dp = Array(n).fill(1); for (let i = 1; i < m; i++) { for (let j = 1; j < n; j++) { // Before update: dp[j] contains value from previous row (above) // dp[j-1] already updated in this iteration (left) dp[j] = dp[j] + dp[j - 1]; } } return dp[n - 1]; } // Verification: All approaches give same answer console.log(uniquePathsTwoRows(10, 15)); // Output: 817190 console.log(uniquePathsOneRow(10, 15)); // Output: 81719071:T46a,def unique_paths_with_obstacles(obstacle_grid: list[list[int]]) -> int: """ Count unique paths avoiding obstacles. Args: obstacle_grid: 2D grid where 1 = blocked, 0 = empty Time Complexity: O(m * n) Space Complexity: O(n) with space optimization """ m = len(obstacle_grid) n = len(obstacle_grid[0]) # Edge case: start or end is blocked if obstacle_grid[0][0] == 1 or obstacle_grid[m-1][n-1] == 1: return 0 # Space-optimized single row dp = [0] * n dp[0] = 1 # Starting cell for i in range(m): for j in range(n): # If current cell is obstacle, zero paths through it if obstacle_grid[i][j] == 1: dp[j] = 0 elif j > 0: # Add paths from left (dp[j] already has paths from above) dp[j] += dp[j - 1] # If j == 0 and no obstacle, dp[j] keeps its value from above return dp[n - 1] # Example grid = [ [0, 0, 0], [0, 1, 0], # Obstacle in the middle [0, 0, 0] ] print(unique_paths_with_obstacles(grid)) # Output: 272:T4b7,function uniquePathsWithObstacles(obstacleGrid: number[][]): number { /** * Count unique paths avoiding obstacles. * * Time Complexity: O(m * n) * Space Complexity: O(n) with space optimization */ const m = obstacleGrid.length; const n = obstacleGrid[0].length; // Edge case: start or end is blocked if (obstacleGrid[0][0] === 1 || obstacleGrid[m-1][n-1] === 1) { return 0; } // Space-optimized single row const dp: number[] = Array(n).fill(0); dp[0] = 1; // Starting cell for (let i = 0; i < m; i++) { for (let j = 0; j < n; j++) { // If current cell is obstacle, zero paths through it if (obstacleGrid[i][j] === 1) { dp[j] = 0; } else if (j > 0) { // Add paths from left (dp[j] already has paths from above) dp[j] += dp[j - 1]; } // If j === 0 and no obstacle, dp[j] keeps its value from above } } return dp[n - 1]; } // Example const grid = [ [0, 0, 0], [0, 1, 0], // Obstacle in the middle [0, 0, 0] ]; console.log(uniquePathsWithObstacles(grid)); // Output: 273:T448,from math import comb # Python 3.8+ def unique_paths_combinatorial(m: int, n: int) -> int: """ O(min(m, n)) solution using combinatorics. The number of paths equals C(m+n-2, m-1) = C(m+n-2, n-1) (Choose which moves are "down" from total moves) """ return comb(m + n - 2, m - 1) # Manual implementation without math.comb def unique_paths_combinatorial_manual(m: int, n: int) -> int: """ Compute C(m+n-2, min(m-1, n-1)) efficiently. Time Complexity: O(min(m, n)) Space Complexity: O(1) """ # Choose smaller value for fewer multiplications numerator_terms = m + n - 2 choose_k = min(m - 1, n - 1) result = 1 for i in range(choose_k): # Compute C(n, k) = n*(n-1)*...*(n-k+1) / k! # Multiply then divide to keep intermediate values reasonable result = result * (numerator_terms - i) // (i + 1) return result print(unique_paths_combinatorial(3, 7)) # 28 print(unique_paths_combinatorial_manual(3, 7)) # 28 print(unique_paths_combinatorial(100, 100)) # Huge number, instant65:{"json":{"id":"seed_6842bc18c74c84ee75f5f4f61122ed38","slug":"2d-dp-problems-grid-paths-lcs","category":"Data Structures & Algorithms","topic":"2D DP Problems — Grid Paths & LCS","title":"2D Dynamic Programming — Grid Paths & Longest Common Subsequence","description":"Master two-dimensional dynamic programming through classic problems: unique grid paths, grid paths with obstacles, longest common subsequence, and more. Learn to identify 2D state structures, construct DP tables, and interpret solutions geometrically.","difficulty":"INTERMEDIATE","estimatedMinutes":75,"pages":[{"id":"seed_a5765ff73f51d290bb8c86694c119ccc","title":"Unique Paths in Grid","order":0,"content":[{"id":"opening-hook","title":"Extending DP to Two Dimensions","content":[{"data":{"content":"In our exploration of dynamic programming, we've tackled problems where the state could be captured by a single index—Fibonacci, climbing stairs, house robber. These **1D DP problems** form the foundation. But many real-world problems require tracking **two independent variables** simultaneously.\n\nConsider navigating a city grid, comparing two strings character by character, or filling a knapsack where both item indices and remaining capacity matter. These problems demand a **two-dimensional state space**—and with it, a 2D DP table.\n\nThe jump from 1D to 2D DP is one of the most important conceptual leaps in algorithmic thinking. Once you master it, you unlock a vast array of problems in string processing, grid navigation, sequence alignment, and optimization."},"type":"text"},{"data":{"icon":"Target","title":"What You Will Learn","content":"By the end of this page, you will master the classic \"Unique Paths\" problem and its variants. You'll understand how to formulate 2D DP problems, visualize state transitions on a grid, and implement solutions that are both correct and efficient. This problem serves as the gateway to all 2D dynamic programming.","variant":"info"},"type":"callout"}]},{"id":"unique-paths-problem","title":"The Unique Paths Problem","content":[{"data":{"content":"**Problem Statement:**\n\nA robot is located at the top-left corner of an `m × n` grid. The robot can only move **down** or **right** at any point in time. The robot is trying to reach the bottom-right corner of the grid.\n\nHow many unique paths are there to reach the destination?\n\n**Visualizing the Grid:**\n\nImagine a 3×7 grid. The robot starts at position (0, 0) and must reach position (2, 6). At each cell, it can move right or down. The question is: in how many distinct ways can it reach the goal?"},"type":"text"},{"data":{"height":"300px","mermaidSyntax":"graph LR\n subgraph Row0[Row 0]\n S((Start)) --> A1(( )) --> A2(( )) --> A3(( )) --> A4(( )) --> A5(( )) --> A6(( ))\n end\n subgraph Row1[Row 1]\n B0(( )) --> B1(( )) --> B2(( )) --> B3(( )) --> B4(( )) --> B5(( )) --> B6(( ))\n end\n subgraph Row2[Row 2]\n C0(( )) --> C1(( )) --> C2(( )) --> C3(( )) --> C4(( )) --> C5(( )) --> G((Goal))\n end\n S --> B0\n A1 --> B1\n A2 --> B2\n A3 --> B3\n A4 --> B4\n A5 --> B5\n A6 --> B6\n B0 --> C0\n B1 --> C1\n B2 --> C2\n B3 --> C3\n B4 --> C4\n B5 --> C5\n B6 --> G"},"type":"mermaid-excalidraw"},{"data":{"content":"**Why This Problem Matters:**\n\nThe unique paths problem is deceptively simple yet profoundly instructive. It appears in:\n\n- **Grid-based games and navigation**: Counting routes in mazes, board games, and pathfinding\n- **Lattice path combinatorics**: Foundation for advanced combinatorial analysis\n- **Dynamic programming fundamentals**: The canonical example for introducing 2D DP\n- **Interview questions**: Extremely common at major tech companies, often with variations\n\nMore importantly, the **thinking pattern** you develop here transfers directly to harder problems: grid paths with obstacles, minimum path sum, longest common subsequence, and string edit distance."},"type":"text"},{"data":{"icon":"Info","title":"Constraints and Assumptions","content":"We assume the grid has no obstacles (we'll add obstacles later). Movements are restricted to right and down only—no diagonal, up, or left movements. The grid dimensions m and n are positive integers, typically 1 ≤ m, n ≤ 100 for DP solutions, though combinatorial solutions handle much larger values.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":1},{"id":"naive-recursive-approach","title":"The Naive Recursive Approach","content":[{"data":{"content":"Before diving into dynamic programming, let's develop intuition through recursion. This approach, while inefficient, reveals the problem's structure and exposes why DP is necessary.\n\n**Recursive Insight:**\n\nTo reach cell `(i, j)`, the robot must have come from either:\n1. The cell directly above: `(i-1, j)` (if it moved down)\n2. The cell directly to the left: `(i, j-1)` (if it moved right)\n\nTherefore, the number of ways to reach `(i, j)` equals the sum of ways to reach `(i-1, j)` and `(i, j-1)`.\n\n**Base Cases:**\n- If we're at the starting cell `(0, 0)`, there's exactly 1 way to be there (do nothing)\n- If the row index is negative (`i < 0`) or column index is negative (`j < 0`), there are 0 ways (we've gone off the grid)"},"type":"text"},{"data":{"fileName":"unique_paths_recursive.py","languages":[{"code":"def unique_paths_recursive(m: int, n: int) -> int:\n \"\"\"\n Count unique paths in an m x n grid using naive recursion.\n \n Time Complexity: O(2^(m+n)) - exponential, highly inefficient\n Space Complexity: O(m + n) - recursion stack depth\n \"\"\"\n def count_paths(row: int, col: int) -> int:\n # Base case: Out of bounds\n if row < 0 or col < 0:\n return 0\n \n # Base case: Starting cell\n if row == 0 and col == 0:\n return 1\n \n # Recursive case: Sum paths from above and left\n paths_from_above = count_paths(row - 1, col)\n paths_from_left = count_paths(row, col - 1)\n \n return paths_from_above + paths_from_left\n \n # Start from bottom-right corner (m-1, n-1)\n return count_paths(m - 1, n - 1)\n\n# Example: 3x7 grid\nprint(unique_paths_recursive(3, 7)) # Output: 28","label":"Python","value":"python"},{"code":"function uniquePathsRecursive(m: number, n: number): number {\n /**\n * Count unique paths in an m x n grid using naive recursion.\n * \n * Time Complexity: O(2^(m+n)) - exponential, highly inefficient\n * Space Complexity: O(m + n) - recursion stack depth\n */\n function countPaths(row: number, col: number): number {\n // Base case: Out of bounds\n if (row < 0 || col < 0) {\n return 0;\n }\n \n // Base case: Starting cell\n if (row === 0 && col === 0) {\n return 1;\n }\n \n // Recursive case: Sum paths from above and left\n const pathsFromAbove = countPaths(row - 1, col);\n const pathsFromLeft = countPaths(row, col - 1);\n \n return pathsFromAbove + pathsFromLeft;\n }\n \n // Start from bottom-right corner (m-1, n-1)\n return countPaths(m - 1, n - 1);\n}\n\n// Example: 3x7 grid\nconsole.log(uniquePathsRecursive(3, 7)); // Output: 28","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**The Problem: Exponential Time Complexity**\n\nThis recursive solution works but is catastrophically slow. For a modest 20×20 grid, it would make over 137 billion function calls!\n\nThe issue is **overlapping subproblems**. Consider a 3×3 grid. To compute paths to (2, 2), we need paths to (1, 2) and (2, 1). But both of those require paths to (1, 1)—which we compute twice. As the grid grows, this redundancy explodes exponentially."},"type":"text"},{"data":{"height":"350px","mermaidSyntax":"graph TD\n A[\"(2,2)\"] --> B[\"(1,2)\"]\n A --> C[\"(2,1)\"]\n B --> D[\"(0,2)\"]\n B --> E[\"(1,1)\"]\n C --> F[\"(1,1)\"]\n C --> G[\"(2,0)\"]\n E --> H[\"(0,1)\"]\n E --> I[\"(1,0)\"]\n F --> J[\"(0,1)\"]\n F --> K[\"(1,0)\"]\n \n style E fill:#ff9999\n style F fill:#ff9999\n style H fill:#ffcc99\n style I fill:#ffcc99\n style J fill:#ffcc99\n style K fill:#ffcc99"},"type":"mermaid-excalidraw"},{"data":{"icon":"AlertCircle","title":"Overlapping Subproblems Detected","content":"Notice how (1,1) appears in both branches of the recursion tree. The cells (0,1) and (1,0) are computed four times each! This exponential blowup is the hallmark of naive recursion on problems with overlapping subproblems—exactly the scenario where dynamic programming provides dramatic improvement.","variant":"warning"},"type":"callout"}],"titleType":"number","titleNumber":2},{"id":"memoization-approach","title":"Memoization: Top-Down Dynamic Programming","content":[{"data":{"content":"The fix for overlapping subproblems is **memoization**: cache results of subproblems so we never recompute them. Since our state is defined by two indices (row, column), we need a **2D cache**—either a 2D array or a dictionary with tuple keys.\n\n**Transformation Strategy:**\n\n1. Keep the recursive structure exactly as before\n2. Before computing, check if result is already cached\n3. After computing, store result in cache\n4. Return cached result on subsequent calls\n\nThis simple addition transforms exponential complexity to polynomial!"},"type":"text"},{"data":{"fileName":"unique_paths_memoization.py","languages":[{"code":"def unique_paths_memoization(m: int, n: int) -> int:\n \"\"\"\n Count unique paths using memoization (top-down DP).\n \n Time Complexity: O(m * n) - each cell computed exactly once\n Space Complexity: O(m * n) - memo table + O(m + n) recursion stack\n \"\"\"\n # Memoization cache: memo[row][col] = number of paths to (row, col)\n memo = {}\n \n def count_paths(row: int, col: int) -> int:\n # Base case: Out of bounds\n if row < 0 or col < 0:\n return 0\n \n # Base case: Starting cell\n if row == 0 and col == 0:\n return 1\n \n # Check memo before computing\n if (row, col) in memo:\n return memo[(row, col)]\n \n # Compute and store in memo\n result = count_paths(row - 1, col) + count_paths(row, col - 1)\n memo[(row, col)] = result\n \n return result\n \n return count_paths(m - 1, n - 1)\n\n# Now fast even for larger grids\nprint(unique_paths_memoization(23, 12)) # Output: 193536720","label":"Python","value":"python"},{"code":"$6c","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Complexity Analysis:**"},"type":"text"},{"data":{"rows":[["Time","O(2^(m+n))","O(m × n)"],["Space","O(m + n) stack","O(m × n) memo + O(m+n) stack"],["20×20 grid","~137 billion calls","400 calls"],["100×100 grid","Infeasible","10,000 calls (instant)"]],"headers":["Aspect","Before (Naive Recursion)","After (Memoization)"]},"type":"table"},{"data":{"content":"The improvement is astronomical. Memoization eliminates all redundant computation by ensuring each `(row, col)` pair is computed exactly once."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Python's functools.lru_cache","content":"Python provides @functools.lru_cache decorator that automatically memoizes function calls. For the unique paths problem: @lru_cache(maxsize=None) on count_paths eliminates manual memo management. However, understanding manual memoization is essential—lru_cache is syntactic sugar, not magic.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":3},{"id":"tabulation-approach","title":"Tabulation: Bottom-Up Dynamic Programming","content":[{"data":{"content":"While memoization works, it still uses recursion—and recursion has overhead. For this problem, we can eliminate recursion entirely using **tabulation**: build a 2D table iteratively, filling cells in an order that respects dependencies.\n\n**The DP Table:**\n\nCreate an `m × n` table where `dp[i][j]` represents the number of unique paths to reach cell `(i, j)` from `(0, 0)`.\n\n**Filling Order:**\n\nSince each cell depends on the cell above and the cell to the left, we fill the table from top-left to bottom-right, row by row or column by column.\n\n**Recurrence Relation:**\n\n```\ndp[i][j] = dp[i-1][j] + dp[i][j-1] (for i > 0 and j > 0)\ndp[i][0] = 1 (only one way to reach any cell in first column: go down)\ndp[0][j] = 1 (only one way to reach any cell in first row: go right)\n```"},"type":"text"},{"data":{"fileName":"unique_paths_tabulation.py","languages":[{"code":"$6d","label":"Python","value":"python"},{"code":"$6e","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Visualizing the DP Table for a 3×7 Grid:**\n\n```\n 1 | 1 | 1 | 1 | 1 | 1 | 1\n 1 | 2 | 3 | 4 | 5 | 6 | 7\n 1 | 3 | 6 | 10 | 15 | 21 | 28\n```\n\n**Reading the Table:**\n\n- The first row is all 1s: only one way to reach any cell by going right\n- The first column is all 1s: only one way to reach any cell by going down\n- Each interior cell is the sum of the cell above and the cell to the left\n- The bottom-right cell (28) is our answer\n\n**Notice the Pattern:**\n\nThis is actually Pascal's Triangle rotated! The value at `dp[i][j]` equals `C(i+j, i)` = `(i+j)!/(i! × j!)`. This combinatorial insight gives us an O(min(m,n)) mathematical solution, but the DP approach generalizes to problems where such closed-form solutions don't exist."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Why Tabulation Often Wins","content":"No recursion overhead, no risk of stack overflow, cache-friendly memory access patterns, and easier to reason about space optimization. For grid DP problems especially, bottom-up tabulation is typically the preferred approach in production code.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":4},{"id":"space-optimization","title":"Space Optimization: From O(m×n) to O(n)","content":[{"data":{"content":"Examine the recurrence closely: `dp[i][j] = dp[i-1][j] + dp[i][j-1]`. Each cell only depends on:\n1. The cell directly above it (previous row, same column)\n2. The cell to its left (current row, previous column)\n\n**Key Insight:**\n\nWe never need rows older than the previous row! This means we can reduce space from a full 2D table to just **two rows** (or even **one row** with careful implementation).\n\n**Rolling Array Technique:**\n\nMaintain only two arrays: `prev_row` and `curr_row`. After processing each row, the current row becomes the previous row for the next iteration."},"type":"text"},{"data":{"fileName":"unique_paths_space_optimized.py","languages":[{"code":"$6f","label":"Python","value":"python"},{"code":"$70","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Understanding the Single-Row Magic:**\n\nThe single-row optimization works because of **processing order**:\n\n1. We iterate left-to-right across each row\n2. When we update `dp[j]`, `dp[j-1]` has already been updated (current row's left neighbor)\n3. But `dp[j]` still holds the old value (previous row's same position)\n4. So `dp[j] + dp[j-1]` correctly sums \"above\" and \"left\"\n\nThis is a fundamental pattern in 2D DP space optimization. Whenever dependencies are limited to adjacent rows/columns, we can often reduce O(m×n) space to O(n) or O(m)."},"type":"text"},{"data":{"rows":[["Full 2D Table","O(m × n)","Easiest to understand, can trace any cell"],["Two Rows","O(n)","Clear separation of current/previous"],["Single Row","O(n)","Most compact, requires careful update order"],["Single Row + Swap","O(min(m, n))","Choose smaller dimension for row"]],"caption":"Space Complexity Comparison","headers":["Approach","Space Complexity","Additional Notes"]},"type":"table"}],"titleType":"number","titleNumber":5},{"id":"paths-with-obstacles","title":"Variation: Unique Paths with Obstacles","content":[{"data":{"content":"Real-world grids often have obstacles. The variation **Unique Paths II** adds this constraint: some cells are blocked, and the robot cannot pass through them.\n\n**Problem Modification:**\n\nGiven an `m × n` grid where:\n- `obstacleGrid[i][j] = 0` means the cell is empty\n- `obstacleGrid[i][j] = 1` means the cell is blocked\n\nCount unique paths from top-left to bottom-right, avoiding obstacles.\n\n**DP Modification:**\n\n```\nif obstacle[i][j] == 1:\n dp[i][j] = 0 // Can't reach a blocked cell\nelse:\n dp[i][j] = dp[i-1][j] + dp[i][j-1] // Normal case\n```\n\nThe key insight: if a cell is blocked, there are **zero ways** to reach it, which propagates correctly through the DP."},"type":"text"},{"data":{"fileName":"unique_paths_with_obstacles.py","languages":[{"code":"$71","label":"Python","value":"python"},{"code":"$72","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**Understanding Obstacle Propagation:**\n\n```\nGrid: DP Table:\n0 0 0 1 1 1\n0 1 0 → 1 0 1\n0 0 0 1 1 2\n```\n\nThe obstacle at (1,1) creates a \"shadow\"—cells that can only be reached from one direction instead of two. The blocked cell has 0 paths, which propagates correctly.\n\n**Edge Cases to Handle:**\n\n1. **Starting cell blocked**: Return 0 immediately\n2. **Ending cell blocked**: Return 0 immediately\n3. **Entire row blocked**: All cells to the right become unreachable\n4. **Entire column blocked**: All cells below become unreachable"},"type":"text"},{"data":{"icon":"Lightbulb","title":"The Power of Zero Propagation","content":"Notice how elegant the solution is: we don't need special logic for \"paths blocked by obstacle.\" Setting dp[i][j] = 0 for obstacles automatically handles all downstream effects through the normal DP recurrence. This is a hallmark of well-designed DP: the recurrence naturally handles edge cases.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":6},{"id":"related-problems","title":"Related Grid Path Problems","content":[{"data":{"content":"The unique paths problem is the simplest member of a large family of grid DP problems. The same core technique—2D table, recurrence based on neighbors—applies with modifications:\n\n**Minimum Path Sum:**\n\nInstead of counting paths, find the path with minimum sum of cell values.\n- Recurrence: `dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1])`\n\n**Maximum Path Sum:**\n\nSame structure, but use `max` instead of `min`.\n- Recurrence: `dp[i][j] = grid[i][j] + max(dp[i-1][j], dp[i][j-1])`\n\n**Dungeon Game:**\n\nFind minimum starting health to survive a grid with positive (healing) and negative (damage) cells.\n- Requires **backward DP** from destination to start\n\n**Triangle:**\n\nFind minimum path sum in a triangular grid where you can only move to adjacent cells in the next row.\n- Recurrence: `dp[i][j] = triangle[i][j] + min(dp[i-1][j-1], dp[i-1][j])`"},"type":"text"},{"data":{"left":[{"data":{"items":["**Unique Paths** — Basic counting","**Unique Paths II** — With obstacles","**Out of Boundary Paths** — Count paths leaving grid","**Knight Probability** — Probabilistic grid paths"],"title":{"icon":"Target","text":"Counting Problems","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}],"right":[{"data":{"items":["**Minimum Path Sum** — Min cost path","**Maximum Path Sum** — Max value collection","**Cherry Pickup** — Two-agent collection","**Dungeon Game** — Survival optimization"],"title":{"icon":"Zap","text":"Optimization Problems","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"}]},"type":"two-column"},{"data":{"icon":"Info","title":"The Common Thread","content":"All these problems share the 2D grid structure where each cell's value depends on specific neighbors. Master the unique paths problem thoroughly, and you'll find the others are natural extensions—same structure, different recurrence.","variant":"note"},"type":"callout"}],"titleType":"number","titleNumber":7},{"id":"combinatorial-solution","title":"The Mathematical Perspective: Combinatorics","content":[{"data":{"content":"For the basic unique paths problem (no obstacles), there's an elegant O(min(m,n)) mathematical solution based on combinatorics.\n\n**The Insight:**\n\nTo go from (0,0) to (m-1, n-1), the robot must make exactly:\n- `m - 1` moves down (D)\n- `n - 1` moves right (R)\n\nAny valid path is just an arrangement of these moves. For example, in a 3×7 grid: RRRRRRDD, RRDRRRD, etc.\n\n**Counting Arrangements:**\n\nWe need to choose which (m-1) positions out of (m+n-2) total positions are \"down\" moves. This is:\n\n`C(m+n-2, m-1) = (m+n-2)! / ((m-1)! × (n-1)!)`\n\nFor a 3×7 grid: `C(8, 2) = 8!/(2! × 6!) = 28` ✓"},"type":"text"},{"data":{"fileName":"unique_paths_combinatorial.py","languages":[{"code":"$73","label":"Python","value":"python"},{"code":"function uniquePathsCombinatorial(m: number, n: number): number {\n /**\n * O(min(m, n)) solution using combinatorics.\n * \n * Compute C(m+n-2, min(m-1, n-1)) efficiently.\n * \n * Time Complexity: O(min(m, n))\n * Space Complexity: O(1)\n */\n // Choose smaller value for fewer multiplications\n const numeratorTerms = m + n - 2;\n const chooseK = Math.min(m - 1, n - 1);\n \n let result = 1;\n for (let i = 0; i < chooseK; i++) {\n // Compute C(n, k) = n*(n-1)*...*(n-k+1) / k!\n // Multiply then divide to keep intermediate values reasonable\n result = Math.floor(result * (numeratorTerms - i) / (i + 1));\n }\n \n return result;\n}\n\n\nconsole.log(uniquePathsCombinatorial(3, 7)); // 28\nconsole.log(uniquePathsCombinatorial(23, 12)); // 193536720","label":"TypeScript","value":"typescript"}]},"type":"code"},{"data":{"content":"**When to Use Which Approach:**"},"type":"text"},{"data":{"rows":[["DP (tabulation)","O(m×n)","O(n)","Obstacles, custom weights, variants"],["Combinatorial","O(min(m,n))","O(1)","Basic counting, large grids"]],"headers":["Approach","Time","Space","Use When"]},"type":"table"},{"data":{"content":"The combinatorial solution is faster and uses constant space, but it only works for the basic problem. The moment you add obstacles, weights, or other constraints, you need the DP approach.\n\nThis is a general lesson: **DP is versatile but not always optimal**. For specific problems, mathematical insights can yield better algorithms. But DP works when those insights don't exist."},"type":"text"},{"data":{"icon":"Lightbulb","title":"Interview Strategy","content":"In interviews, start with the DP solution—it demonstrates algorithmic thinking. Then mention the combinatorial optimization as an insight. This shows both practical problem-solving and mathematical awareness. If obstacles are mentioned, explain why DP becomes necessary.","variant":"tip"},"type":"callout"}],"titleType":"number","titleNumber":8},{"id":"summary","title":"Summary and Key Takeaways","content":[{"data":{"content":"The unique paths problem serves as the perfect introduction to 2D dynamic programming. Let's consolidate what we've learned:"},"type":"text"},{"data":{"type":"ordered","items":["**2D State Space** — When a problem requires tracking two independent variables (row, column), we need a 2D DP table.","**Recurrence Relation** — `dp[i][j] = dp[i-1][j] + dp[i][j-1]` encodes the insight that paths to (i,j) come from above or left.","**Base Cases** — First row and first column have exactly one path each (only right or only down).","**Space Optimization** — Dependencies limited to adjacent rows enable O(n) space using rolling arrays or in-place updates.","**Obstacle Handling** — Set `dp[i][j] = 0` for blocked cells; propagation handles all downstream effects.","**Combinatorial Connection** — Basic counting equals `C(m+n-2, m-1)`, but DP generalizes to variants."],"title":{"icon":"CheckCircle","text":"Key Concepts Mastered","type":"icon","color":"primary","variant":"outline-circle"},"variant":"accent"},"type":"list"},{"data":{"content":"**The Mental Model:**\n\nThink of the DP table as an **accumulator of possibilities**. Each cell collects all the ways to reach it from legal predecessor cells. The answer accumulates at the destination.\n\n**What's Next:**\n\nWith grid paths mastered, we're ready for the crown jewel of 2D DP: the **Longest Common Subsequence** problem. It applies the same 2D table structure but to sequence comparison—opening doors to string algorithms, bioinformatics, and diff utilities."},"type":"text"},{"data":{"icon":"CheckCircle","title":"Page Complete","content":"You now understand the fundamental 2D DP problem: Unique Paths in Grid. This understanding forms the foundation for all grid-based DP and extends to any problem where state requires two indices. Next, we'll apply these same principles to the powerful Longest Common Subsequence problem.","variant":"success"},"type":"callout"}],"titleType":"number","titleNumber":9}],"isLocked":false},{"id":"seed_511f2659be82bd47f8c5e22c1426c93a","title":"Longest Common Subsequence","order":1,"content":null,"isLocked":true},{"id":"seed_c3184a839ed181305ab6972d522ff960","title":"State: Two Indices","order":2,"content":null,"isLocked":true},{"id":"seed_cd2797a6a0041e6a7e07e2079d10ee07","title":"Table Interpretation","order":3,"content":null,"isLocked":true}]}}