Lecture Notes on Dynamic Programming and Tabulation

Introduction to Dynamic Programming

• Dynamic programming is a favorite topic to teach but often seen as difficult.
• With a gradual progression, dynamic programming can be intuitive.
• Essential for data structure and algorithm interviews.

Problems Covered

1. Fibonacci Sequence
   • Example: Calculate the 4th number in the Fibonacci sequence.
2. Grid Traveler
   • Example: Count the number of ways to move through a 6x9 grid.
3. Coin Change
   • Example: Make 27 cents with the least number of coins.
4. String Construction
   • Example: Construct the string "potentpot" from a set of substrings.

Key Takeaways: Visualizing Algorithms

• Visualize algorithms through drawings and animations.
• Design the algorithm before translating it to code.
• Analyze time and space complexity of solutions.

Course Structure

• Part 1: Memoization
• Part 2: Tabulation
• No prior knowledge of dynamic programming needed, but basic recursion and complexity analysis are assumed.

Fibonacci Problem

Recursive Approach

• Function fib(n) calculates the nth Fibonacci number.
• Base cases: fib(1) = 1, fib(2) = 1
• Recursive case: fib(n) = fib(n-1) + fib(n-2)
• Issues with performance for large n due to repetitive calculations.

Memoized Approach

• Implement memoization to store results of previous calculations to avoid redundant work.
• Base case checks for values in the memo before calculating.
• Results in significant performance improvements (e.g., calculating fib(50)).

Visualizing Recursive Calls

• Use a tree to visualize recursive calls for small values (e.g., fib(6)).
• Key insight: overlapping subproblems and repeated calculations can be optimized away.

Grid Traveler Problem

Recursive Approach

• Function calculates the number of ways to travel from top-left to bottom-right in an m x n grid.
• Base cases: Either m or n is 0 (returns 0), or 1x1 grid (returns 1).
• Recursive case: sum of ways to travel right and down.

Memoized Approach

• Use memoization to store results for (m,n) pairs to avoid redundant work.

Tabulation Approach

• Create a 2D table where each cell (i,j) contains the number of ways to get to that cell.
• Initialize starting cell (1,1) as 1.
• Fill in the table iteratively using the relation: table[i][j] = table[i-1][j] + table[i][j-1].

Can Sum Problem

Recursive Approach

• Function determines if a target sum can be achieved using numbers from an array.
• Uses recursive calls to explore all combinations.

Memoized Approach

• Implement memoization to store results of subproblems to avoid redundant checks.
• Returns boolean to indicate if the target can be achieved.

Tabulation Approach

• Create a table where each index represents whether the target sum can be achieved.
• Initialize table with False and set table[0] = True as base case.
• Fill in the table iteratively based on achievable sum indices.

How Sum Problem

Recursive Approach

• Function returns an array of numbers that sum to the target if possible.

Memoized Approach

• Memoization stores the subproblem results for efficiency.
• Returns the first valid combination found.

Tabulation Approach

• Create a table where each index holds the combination of numbers that sum to the target up to that index.
• Initialize with None, except for table[0] which is an empty array.
• Fill in the table by adding number combinations to possible sums.

Best Sum Problem

Recursive Approach

• Function returns the shortest combination of numbers that sum to the target if possible.

Memoized Approach

• Use memoization to store subproblem results efficiently.
• Track the shortest combination during recursive calls.

Tabulation Approach

• Similar to How Sum but keeps updating with the shortest combination found.
• Fill table with None, except for table[0] which is an empty array.

Conclusion

• Dynamic programming problems can be tackled using either memoization or tabulation.
• Visualize problems using trees for recursive understanding.
• Adopt tabulation for iterative solutions by building tables based on problem inputs.
• Practice problems on platforms like Coderbyte to solidify understanding.