Dynamic Programming and Tabulation

Introduction

• Dynamic programming is liked by many but considered challenging by students.
• Essential for data structure and algorithm interviews.
• Taught through progressive complexity in problems.

Example Problems

• Fibonacci Sequence: Calculate the nth number in the sequence.
• Grid Traveler: Count the number of ways to move through an m x n grid.
• Coin Change: Determine the minimum number of coins needed to make a certain amount.
• String Construction: Given a set of substrings, find ways to construct a target string like 'potentpot'.

Course Format

• Visualization: Heavy use of whiteboards and animations.
• Algorithm Design: Translating visual and logical processes into code.
• Analyzing Complexity: Focus on time and space complexity.
• Language: Code examples in JavaScript, but adaptable to other languages.

Two Main Parts of the Course

1. Memoization: Storing results of expensive function calls and reusing them.
2. Tabulation: Building solutions iteratively using a table.

Prerequisites

• Basic understanding of recursion and complexity analysis (Big O notation).

Fibonacci Problem

• Problem: Write a function fib(n) to return the nth Fibonacci number.
• Recursive Implementation: Classic but has exponential time complexity. function fib(n) { if (n <= 2) return 1; return fib(n - 1) + fib(n - 2); }
• Time Complexity: O(2^n)

Memoization for Fibonacci

• Improvement: Store results of subproblems in a JavaScript object (hash map). function fib(n, memo = {}) { if (n in memo) return memo[n]; if (n <= 2) return 1; memo[n] = fib(n - 1, memo) + fib(n - 2, memo); return memo[n]; }
• Time Complexity: O(n)
• Space Complexity: O(n)

Grid Traveler Problem

• Problem: Count the number of ways to travel from the top-left corner to the bottom-right corner of a grid.
• Recursive Implementation: Similar to Fibonacci, but for different dimensions. function gridTraveler(m, n) { if (m == 1 && n == 1) return 1; if (m == 0 || n == 0) return 0; return gridTraveler(m - 1, n) + gridTraveler(m, n - 1); }
• Tabulation: Build a 2D array. function gridTraveler(m, n) { const table = Array(m + 1) .fill() .map(() => Array(n + 1).fill(0)); table[1][1] = 1; for (let i = 0; i <= m; i++) { for (let j = 0; j <= n; j++) { const current = table[i][j]; if (j + 1 <= n) table[i][j + 1] += current; if (i + 1 <= m) table[i + 1][j] += current; } } return table[m][n]; }

Can Sum Problem

• Problem: Return a boolean indicating whether a target sum can be made using numbers from an array.
• Tabulation: Use an array where indices represent state of reachable sums. function canSum(targetSum, numbers) { const table = Array(targetSum + 1).fill(false); table[0] = true; for (let i = 0; i <= targetSum; i++) { if (table[i]) { for (let num of numbers) { if (i + num <= targetSum) table[i + num] = true; } } } return table[targetSum]; }
• Time Complexity: O(m * n), where m is target sum and n is numbers array length.
• Space Complexity: O(m)

How Sum Problem

• Problem: Return an array containing any combination of elements that sum to the target.
• Tabulation: Use an array of arrays where indices represent state of each sum. function howSum(targetSum, numbers) { const table = Array(targetSum + 1).fill(null); table[0] = []; for (let i = 0; i <= targetSum; i++) { if (table[i] !== null) { for (let num of numbers) { const combination = [...table[i], num]; if (i + num <= targetSum) table[i + num] = combination; } } } return table[targetSum]; }

Best Sum Problem

• Problem: Return the shortest combination of elements that sum to the target.
• Tabulation: Use similar logic as How Sum but include logic to prefer shorter arrays. function bestSum(targetSum, numbers) { const table = Array(targetSum + 1).fill(null); table[0] = []; for (let i = 0; i <= targetSum; i++) { if (table[i] !== null) { for (let num of numbers) { const combination = [...table[i], num]; if (i + num <= targetSum) { if (!table[i + num] || table[i + num].length > combination.length) { table[i + num] = combination; } } } } } return table[targetSum]; }

Can Construct Problem

• Problem: Return a boolean indicating whether the target string can be constructed by concatenating words from the word bank.
• Tabulation: Use an array representing the possibility of substring construction. function canConstruct(target, wordBank) { const table = Array(target.length + 1).fill(false); table[0] = true; for (let i = 0; i <= target.length; i++) { if (table[i]) { for (let word of wordBank) { if (target.slice(i, i + word.length) === word) { table[i + word.length] = true; } } } } return table[target.length]; }
• Time Complexity: O(m^2 * n), where m is target length and n is the number of words.
• Space Complexity: O(m)

Count Construct Problem

• Problem: Return the number of ways the target string can be constructed by concatenating words from the word bank.
• Tabulation: Use an array to count ways each substring can be constructed. function countConstruct(target, wordBank) { const table = Array(target.length + 1).fill(0); table[0] = 1; for (let i = 0; i <= target.length; i++) { for (let word of wordBank) { if (target.slice(i, i + word.length) === word) { table[i + word.length] += table[i]; } } } return table[target.length]; }

All Construct Problem

• Problem: Return all possible ways the target string can be constructed using the words from the word bank.
• Tabulation: Use an array of arrays to store all combination of strings. function allConstruct(target, wordBank) { const table = Array(target.length + 1).fill().map(() => []); table[0] = [[]]; for (let i = 0; i <= target.length; i++) { for (let word of wordBank) { if (target.slice(i, i + word.length) === word) { const newCombinations = table[i].map(subArray => [...subArray, word]); table[i + word.length].push(...newCombinations); } } } return table[target.length]; }

Conclusion and Final Advice

• Recognize overlapping subproblems.
• Focus on input type and edge cases.
• Decide between memoization and tabulation.
• Use diagrams and pseudocode before actual coding.
• Practice makes perfect.