Dynamic programming

Explore top-down dynamic programming, using a memoization lookup table to store fib subproblem results and avoid recomputation with hash table keys. Learn O(n) time and O(n) space characteristics.

Master the bottom-up approach (tabulation) to dynamic programming by building a dp table, solving fib(n) iteratively, and optimizing time and space from O(n) to O(1).

Compare top-down memoization with bottom-up tabulation by weighing ease of implementation, space, and performance. Use memoization to avoid unnecessary subproblems and stack overflow, otherwise prefer tabulation.

Learn to model recursive calls with a directed acyclic graph to reveal overlapping subproblems in Fibonacci, showing how each unique call maps to a subproblem and guides bottom-up table design.

Learn to solve the minimum cost path in a matrix with dynamic programming, moving right or down, using top-down and bottom-up approaches and space optimization.

Apply the dynamic programming technique to problems with optimization goals by identifying optimal substructure and overlapping subproblems, formulating a recurrence, and choosing top-down or bottom-up approaches.

Explore dynamic programming for the paths in a matrix problem, counting routes from the top-left to bottom-right while avoiding walls (1s) by moving right or down. The lesson demonstrates recursive, memoization, and tabulation approaches, shows space optimizations to O(m) or O(min(n,m)), and analyzes O(nm) time.

Learn to solve the house robber problem with dynamic programming, using recursion and memoization to maximize non-adjacent steals. Apply tabulation and space optimization to achieve O(n) time and O(1) space.

Master the longest common subsequence problem for two strings using dynamic programming, with memoization and tabulation to achieve O(nm) time and O(nm) space, plus O(m) space optimization.

Explore the gold mine problem with dynamic programming, building a dp table and using recursion, memoization, and tabulation to compute the maximum gold path from top to last row.

Explore the Levenshtein edit distance between two words and learn dynamic programming approaches—recursion with memoization and bottom-up tabulation—using insertions, deletions, and substitutions.

Learn how dynamic programming solves the ways to climb problem by counting ways to reach step n with a given jump set, using memoization and tabulation.