🧩

Dynamic Programming

30 cards · 🇺🇸 English

Memoization, tabulation, and classic dynamic programming patterns.

Study all 30 cards for free

Flashcards, quizzes, pixel-art games and a daily review that remembers for you.

Study this deck free

Try the first 10 cards

1 / 10
Question

Dynamic programming

Knew itLearning

Tap the card for the answer · swipe right if you knew it, left if not

Already have an account? Sign in

Cards

  1. 1Dynamic programming
    Algorithmic paradigm solving complex problems by breaking them into simpler subproblems, storing results to avoid redundant computation
  2. 2Two key properties needed for dynamic programming
    1) Optimal substructure: optimal solution contains optimal solutions to subproblems. 2) Overlapping subproblems: same subproblems solved multiple times
  3. 3Memoization (top-down DP)
    Recursively solve problem, storing results in cache (e.g., hash map, array) to avoid recomputing; lazy evaluation approach
  4. 4Tabulation (bottom-up DP)
    Iteratively solve subproblems in order, building up solution from base cases; typically uses array/table; avoids recursion overhead
  5. 5Fibonacci sequence as a DP problem
    Classic example: F(n) = F(n-1) + F(n-2); naive recursion O(2ⁿ), DP reduces to O(n) time, O(1) space with optimization
  6. 60/1 Knapsack problem
    Given items with weights and values, maximize value in knapsack with weight capacity W; each item taken 0 or 1 time; O(nW) DP solution
  7. 7Recurrence relation for 0/1 Knapsack
    dp[i][w] = max(dp[i-1][w], dp[i-1][w-wᵢ] + vᵢ) - either skip item i or include it
  8. 8Longest Common Subsequence (LCS) problem
    Find longest subsequence common to two sequences (not necessarily contiguous); O(mn) DP solution using 2D table
  9. 9LCS recurrence relation
    If X[i]==Y[j]: dp[i][j] = 1 + dp[i-1][j-1]; else: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
  10. 10Longest Increasing Subsequence (LIS) problem
    Find length of longest strictly increasing subsequence; O(n²) DP or O(n log n) with binary search
  11. 11Edit Distance (Levenshtein) problem
    Minimum operations (insert, delete, substitute) to transform one string to another; O(mn) DP solution
  12. 12Coin Change problem
    Find minimum coins to make amount, or count ways to make amount; classic DP problem with O(n×amount) complexity
  13. 13Matrix Chain Multiplication problem
    Find optimal order to multiply chain of matrices to minimize scalar multiplications; O(n³) DP solution
  14. 14Rod Cutting problem
    Given rod of length n and prices for each length, maximize profit by cutting rod; similar to unbounded knapsack
  15. 150/1 vs unbounded knapsack
    0/1: each item used once. Unbounded: infinite supply of each item; recurrence and solution differ
  16. 16Subset Sum problem
    Determine if subset of numbers sums to target; O(n×sum) DP; variation: count subsets with given sum
  17. 17Space optimization in DP
    Reduce space from O(n²) to O(n) or O(1) by observing that often only previous row/column needed; common in knapsack, LCS
  18. 18Partition Equal Subset Sum problem
    Can array be partitioned into two subsets with equal sum? Reduces to subset sum with target = total_sum/2
  19. 19House Robber problem
    Maximize money robbed from houses in a line/circle without robbing adjacent houses; O(n) DP with state transitions
  20. 20Maximum Subarray Sum (Kadane's) problem
    Find contiguous subarray with largest sum; O(n) solution: dp[i] = max(nums[i], dp[i-1] + nums[i])
  21. 21Climbing Stairs problem
    Count ways to reach top of n-step staircase taking 1 or 2 steps; equivalent to Fibonacci: dp[n] = dp[n-1] + dp[n-2]
  22. 22Palindrome Partitioning problem
    Minimum cuts to partition string into palindromes; O(n²) DP with precomputed palindrome check
  23. 23DP on trees
    DP where states depend on tree structure; examples: tree diameter, max independent set on tree; often use DFS with memoization
  24. 24Digit DP
    Technique for counting numbers with specific properties in a range; uses digit-by-digit construction with tight bound tracking
  25. 25Bitmask DP
    DP where state includes bitmask representing subset; used in TSP, assignment problems; state space O(2ⁿ × n)
  26. 26Traveling Salesman Problem (TSP) DP solution
    O(2ⁿ × n²) using bitmask DP; dp[mask][i] = min cost to visit cities in mask ending at city i
  27. 27State transition in DP
    The recurrence relation showing how current state depends on previous states; defines how to build solution from subproblems
  28. 28Identify if a problem can use DP
    Check for: overlapping subproblems, optimal substructure, ability to define state, clear recurrence relation
  29. 29Time complexity trade-off in DP
    DP trades space (storing results) for time (avoiding recomputation); typically achieves polynomial time from exponential naive solutions
  30. 30DP vs greedy algorithms
    Greedy: makes locally optimal choices, may not give global optimum. DP: considers all subproblems, guarantees global optimum when applicable

Articles about this deck

More Programming decks

See all
Study all 30 cards free