15 DP variations for Interviews

If you’ve ever felt DP problems look different but somehow feel the same — you’re right.
Here’s a complete breakdown — starting with the Top 15 Core DP

  1. Longest Increasing Subsequence (LIS)
    Concept: Subsequence DP + Binary Search Optimization
    Follow-ups:
    LeetCode 300. Longest Increasing Subsequence
    LeetCode 673. Number of Longest Increasing Subsequence
    GFG: Longest Increasing Subsequence (DP-3)

  2. 0/1 Knapsack Problem
    Concept: Subset sum DP, classic iterative and recursive forms
    Follow-ups:
    GFG: 0-1 Knapsack Problem
    LeetCode 416. Partition Equal Subset Sum
    LeetCode 494. Target Sum

  3. Longest Common Subsequence (LCS)
    Concept: Classic string DP, foundation for many string matching problems
    Follow-ups:
    LeetCode 1143. Longest Common Subsequence
    LeetCode 583. Delete Operation for Two Strings
    GFG: Print Shortest Common Supersequence

  4. Edit Distance (String Transformation)
    Concept: DP over strings with insertion, deletion, replacement operations
    Follow-ups:
    LeetCode 72. Edit Distance
    LeetCode 97. Interleaving String
    GFG: Edit Distance Problem

  5. Maximum Subarray / Kadane’s Algorithm
    Concept: DP over prefix sums; can be extended for circular arrays
    Follow-ups:
    LeetCode 53. Maximum Subarray
    LeetCode 918. Maximum Sum Circular Subarray
    GFG: Largest Sum Contiguous Subarray

  6. Coin Change (Ways and Min Coins)
    Concept: Combinatorial DP (unbounded knapsack variant)
    Follow-ups:
    LeetCode 322. Coin Change
    LeetCode 518. Coin Change II
    GFG: Coin Change Problem

  7. House Robber Series (Linear and Circular)
    Concept: DP on arrays with adjacency constraints
    Follow-ups:
    LeetCode 198. House Robber
    LeetCode 213. House Robber II
    LeetCode 740. Delete and Earn (advanced variant)

  8. Unique Paths (Grid Traversal DP)
    Concept: Grid-based combinatorial DP, extendable with obstacles
    Follow-ups:
    LeetCode 62. Unique Paths
    LeetCode 63. Unique Paths II
    GFG: Number of Unique Paths

  9. Minimum Path Sum / Triangle Path DP
    Concept: Classic DP on grid or triangle
    Follow-ups:
    LeetCode 64. Minimum Path Sum
    LeetCode 120. Triangle
    GFG: Minimum Path Sum in Grid

  10. Palindromic Substrings and Subsequences
    Concept: DP over substrings, expand-around-center approach
    Follow-ups:
    LeetCode 647. Palindromic Substrings
    LeetCode 516. Longest Palindromic Subsequence
    GFG: Longest Palindromic Subsequence

  11. Partition DP (Matrix Chain Multiplication Type)
    Concept: DP with interval partitioning
    Follow-ups:
    GFG: Matrix Chain Multiplication
    LeetCode 312. Burst Balloons
    LeetCode 1547. Minimum Cost to Cut a Stick

  12. Subset Sum and Variations
    Concept: Boolean DP, classic knapsack-based problems
    Follow-ups:
    LeetCode 698. Partition to K Equal Sum Subsets
    LeetCode 473. Matchsticks to Square
    GFG: Subset Sum Problem

  13. Stock Buy and Sell (Profit Maximization DP)
    Concept: State machine DP (hold, sell, cooldown variants)
    Follow-ups:
    LeetCode 121. Best Time to Buy and Sell Stock
    LeetCode 122. Best Time to Buy and Sell Stock II
    LeetCode 309. Best Time to Buy and Sell Stock with Cooldown

  14. Frog Jump / Minimum Cost Climbing Stairs
    Concept: Basic DP recurrence with local decisions
    Follow-ups:
    LeetCode 746. Min Cost Climbing Stairs
    GFG: Frog Jump (Atcoder DP Series A)
    LeetCode 70. Climbing Stairs

  15. Distinct Subsequences / Counting Subsequences
    Concept: Counting DP for string transformations
    Follow-ups:
    LeetCode 115. Distinct Subsequences
    GFG: Count Distinct Subsequences
    LeetCode 940. Distinct Subsequences II

Bonus for extra practice:

  1. Tree DP — Diameter, Path Sums, and Rerooting
    Concept: DP over tree nodes using postorder + rerooting (subtree + complement computation)
    Follow-ups:
    LeetCode 124. Binary Tree Maximum Path Sum
    LeetCode 543. Diameter of Binary Tree
    GFG: Sum of distances in tree (rerooting based)

  2. Bitmask DP — Traveling Salesman and Subset Problems
    Concept: DP state represented by subsets (bitmask of visited nodes)
    Follow-ups:
    LeetCode 847. Shortest Path Visiting All Nodes
    GFG: Traveling Salesman Problem (TSP) using Bitmask DP
    LeetCode 698. Partition to K Equal Sum Subsets

  3. Digit DP — Counting numbers with given properties
    Concept: DP over digits with tight/loose bounds for number formation problems
    Follow-ups:
    LeetCode 1012. Numbers With Repeated Digits
    GFG: Count numbers with sum of digits equal to given value
    LeetCode 2719. Count of Integers With Digit Sum in Range

Suggest if you have more, would love to add on!!

Comments (2)