Tabulation
tabulation
Algorithms
Dynamic Programming (Intro)
Naive recursive Fibonacci computes `fib(40)` in seconds, `fib(50)` in minutes, and gives up on `fib(60)`, all because it recomputes the same subproblems exponentially many times. Cache the result of each `fib(k)` the first time you compute it and the same recursion runs in linear time. That single change, remembering answers, is the entire content of dynamic programming. **Dynamic Programming (Intro)** turns that observation into a complete problem-solving framework. You will identify overlapping subproblems and optimal substructure (the two properties a problem must have for DP to apply), and master both approaches: top-down memoization (recursion plus a cache) and bottom-up tabulation (iteratively filling a table). Classic 1D problems include Fibonacci, climbing stairs, coin change, house robber, and a first look at Kadane's algorithm. The lesson teaches you to define state precisely ("what does `dp[i]` represent?"), write the transition ("how does `dp[i]` follow from earlier states?"), set base cases, and apply rolling-variable space optimization that drops `O(n)` to `O(1)`. In **Recursion Fundamentals**, you treated each recursive call as a stack frame. Memoization just attaches a cache so identical inputs return immediately. Next, **Bit Manipulation (Intro)** turns to a different toolkit, where bitwise operators give elegant `O(1)` solutions.
Not Started
0%
Practice Problems
Climbing Stairs
Given n steps, find the number of distinct ways to climb to the top when you can take 1 or 2 steps at a time.
Min Cost Climbing Stairs
Given an array of step costs, find the minimum cost to reach the top of the staircase starting from step 0 or step 1.
Burst Balloons
Given n balloons with numbers on them, burst them wisely to maximize the total coins collected, where bursting balloon i earns nums[left] * nums[i] * nums[right].
Distinct Subsequences
Given two strings s and t, return the number of distinct subsequences of s which equals t.
Regular Expression Matching
Implement regular expression matching with support for '.' (matches any single character) and '*' (matches zero or more of the preceding element).
Coin Change II
Given an array of coin denominations and a target amount, return the number of distinct combinations that make up that amount. Each coin may be used an unlimited number of times.
Coin Change
Given an array of coin denominations and a target amount, return the fewest number of coins needed to make up that amount, or -1 if it cannot be made.
Decode Ways
Given a string of digits, determine the total number of ways to decode it, where 'A' = 1, 'B' = 2, ..., 'Z' = 26.
Edit Distance
Given two strings word1 and word2, return the minimum number of operations (insert, delete, or replace a character) required to convert word1 into word2.
House Robber
Given an array representing the amount of money in each house along a street, determine the maximum amount you can rob without robbing two adjacent houses.
Longest Common Subsequence
Given two strings, return the length of their longest common subsequence. A subsequence is a sequence that can be derived by deleting some (or no) characters without changing the order of the remaining characters.
Longest Increasing Subsequence
Given an integer array, return the length of the longest strictly increasing subsequence.
Minimum Path Sum
Given an m x n grid filled with non-negative numbers, find a path from the top-left to the bottom-right that minimizes the sum of all numbers along the path.
Triangle
Given a triangle array, return the minimum path sum from top to bottom, where at each step you may move to an adjacent number on the row below.
Unique Paths II
Given an m x n grid with obstacles, count the number of unique paths from the top-left corner to the bottom-right corner, moving only right or down.
Unique Paths
Given an m x n grid, find the number of unique paths from the top-left corner to the bottom-right corner, moving only right or down.
Word Break
Given a string and a dictionary of words, determine if the string can be segmented into a space-separated sequence of dictionary words.