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!!