Lecture Notes: Dynamic Programming on Grids

Introduction

• Topic: Dynamic Programming (DP) on grids/2D matrix
• Subtopics covered: Counting paths, including paths with obstacles, minimum path sum, max path sum (under conditions), the triangle problem, paths with two start points
• Purpose: Solve six DP problems on grids to master the concept possible to solve any DP problems on 2D matrix
• Code Studio: Recommended platform for practice

Prerequisites

• Recursion Basics: Refer to Lecture 7 for foundational knowledge
  • Base Case: Return 1 or 0 depending on conditions
  • Count Ways: Techniques for counting paths
• DP Basics: Memorization and understanding of recursive solutions is essential

Problem 1: Total Unique Paths

• Objective: Find total unique paths from point A (top-left cell) to point B (bottom-right cell) in an m x n matrix
• Movement Constraints: Only rightward and downward movements allowed
• Example: For a 2x2 matrix, paths are 2

Steps:

1. Recursion Setup
   • Initialize function f(i, j) representing unique paths to cell (i, j) from (0, 0).
   • Recursion starts from (m-1, n-1) and aims to reach (0, 0).
2. Base Cases
   • If i == 0 and j == 0: Return 1 (reached destination)
   • If i < 0 or j < 0: Return 0 (out of boundary)
3. Recurrence Relation
   • Explore all possible paths (right and down).
   • f(i, j) = f(i-1, j) + f(i, j-1)
4. Time Complexity: Exponential (2^(m*n))
   • Space Complexity: Recursion stack space (path length = (m-1) + (n-1))*

Transition from Recursion to Memoization

• Memoization: Store results to avoid repetitive computation
  • Use DP table (dp[m][n]) initialized to -1
  • Check if dp[i][j] is already computed. If yes, return the value
  • Set dp[i][j] = f(i-1, j) + f(i, j-1)
• Time Complexity: O(m n)
• Space Complexity: O(m n + recursion stack space)

Tabulation (Bottom-Up Approach)

1. Declare DP array of size m x n
2. Initialize Base Case
   • dp[0][0] = 1
3. Iterate through the grid
   • For i from 0 to m-1
   • For j from 0 to n-1
     • Compute up and left paths
     • dp[i][j] = dp[i-1][j] + dp[i][j-1], handling boundary checks
4. Optimized Storage

• Store the previous and current rows
• Use arrays instead of full DP table to lower memory usage

Space Optimization

• Optimize to 1D Array:
  • Use two arrays: prev and curr to store transitional states
  • Update prev with curr after completing each row
• Considerations: Handle boundary conditions correctly

Conclusion

• Practice all six problems for mastery
• DP Concepts Covered:
  • Recursion, Memoization, Tabulation, and Space Optimization
• Additional Resources: Code Studio and further search for combinatorial solutions for advanced practice