Learning Path
Blogs
Premium
Login

Hide Index

Dynamic Programming

0% completed

Introduction to dynamic programming

Understanding the problem
Understanding dynamic programming
The formal definition of dynamic programming
The mental model for dynamic programming

State

Definition of state
Discovering the state

Recurrence relation

The Bellman optimality equation
Deriving a recurrence relation
Verifying a recurrence relation

Base cases

Defining base cases
Identifying base cases
Verifying base cases

Order of execution

Computation order
Top down order of execution
Bottom up order of execution

Longest increasing subsequence

Understanding the longest increasing subsequence problem
Understanding the top down solution to the longest increasing subsequence problem
Understanding the bottom up solution to the longest increasing subsequence problem
Longest increasing subsequence

Longest common subsequence

Understanding the longest common subsequence problem
Understanding the top-down solution to the longest common subsequence problem
Understanding the bottom-up solution to the longest common subsequence problem
Longest common subsequence
Longest common subsequence II

Longest common substring

Understanding the longest common substring problem
Understanding the top-down solution to the longest common substring problem
Understanding the bottom-up solution to the longest common substring problem
Longest common substring

Edit distance

Understanding the edit distance problem
Understanding the top-down solution to the edit distance problem
Understanding the bottom-up solution to the edit distance problem
Edit distance

0/1 Knapsack

Understanding the 0/1 knapsack problem
Understanding the top down solution to the 0/1 knapsack problem
Understanding the bottom up solution to the 0/1 knapsack problem
Zero one knapsack
Zero one Knapsack II

Bounded Knapsack

Understanding the bounded knapsack problem
Understanding the top down solution to the bounded knapsack problem
Understanding the bottom up solution to the bounded knapsack problem
Bounded knapsack

Unbounded Knapsack

Understanding the unbounded knapsack problem
Understanding the top down solution to the unbounded knapsack problem
Understanding the bottom up solution to the unbounded knapsack problem
Unbounded knapsack

Counting knapsack

Understanding the counting knapsack problem
Understanding the top-down solution to the counting knapsack problem
Understanding the bottom-up solution to the counting knapsack problem
Counting Knapsack

Longest palindromic subsequence

Understanding the longest palindromic subsequence problem
Understanding the top down solution to the longest palindromic subsequence problem
Understanding the bottom up solution to the longest palindromic subsequence problem
Longest palindromic subsequence

Longest palindromic substring

Understanding the longest palindromic substring problem
Understanding the top down solution to the longest palindromic substring problem
Understanding the bottom up solution to the longest palindromic substring problem
Longest palindromic substring

Palindrome partitioning

Understanding the palindrome partitioning problem
Understanding the top down solution to the palindrome partitioning problem
Understanding the bottom up solution to the palindrome partitioning problem
Minimum partitioning

Matrix chain multiplication

Understanding the matrix chain multiplication problem
Understanding the top down solution to the matrix chain multiplication problem
Understanding the bottom up solution to the matrix chain multiplication problem
Matrix chain multiplication

Pattern: Linear DP

Understanding the linear DP pattern
Identifying the linear DP pattern
Covering distance
Min cost climbing stairs
Reachability check
House robber

Pattern: Running suffix DP

Understanding the running-suffix DP pattern
Identifying the running-suffix DP pattern
Best time to buy and sell stock
Longest valid subarray
Maximum product subarray
Maximum sum circular subarray

Pattern: Subsequence DP

Understanding the subsequence DP pattern
Identifying the subsequence DP pattern
Largest divisible subset
Longest increasing subsequences
Longest bitonic subsequence
Longest alternating subsequence

Pattern: Grid DP

Understanding the grid DP pattern
Identifying the grid DP pattern
Minimum path sum
Largest square area
Largest plus of 1's
Dungeon game

Pattern: Dual sequence DP

Understanding the dual-sequence DP pattern
Identifying the dual-sequence DP pattern
Pattern as subsequence
Interleaving Check
Wildcard pattern matching
Shortest common supersequence

Pattern: 0/1 knapsack

Understanding the 0/1 knapsack pattern
Identifying the 0/1 knapsack pattern
Subset sum
Partition with equal sum
Sets with smallest discrepancy
Target sum

Pattern: Bounded knapsack

Understanding the bounded knapsack pattern
Identifying the bounded knapsack pattern
Payment with limited coins
Minimum coins with limited supply
Ways to pay with limited coins
Rod cutting with limited pieces

Pattern: Unbounded knapsack

Understanding the unbounded knapsack pattern
Identifying the unbounded knapsack pattern
Coin change
Integer break
Ribbon cut
Rod cutting

Pattern: Counting knapsack

Understanding the counting knapsack pattern
Identifying the counting knapsack pattern
Subset sum count
Rod cutting combinations
Staircase climb count
Dice rolls with target sum

Pattern: Palindrome DP

Understanding the palindrome DP pattern
Identifying the palindrome DP pattern
Count palindromic substrings
Minimum insertions to make a palindrome

Pattern: Interval DP

Understanding the interval DP pattern
Identifying the interval DP pattern
Burst balloons
Minimum cost to merge stones
Minimum cost to cut a stick
Optimal game strategy
Boolean parenthesization

Assessments

Assessment 1
Assessment 2

Certificate

Certificate

We'll be right back

The site is temporarily unavailable, usually while we ship an update. Please try again in a few minutes.