Steps to Solve Dynamic Programming Problems

General Steps for Solving DP Problems

1. Understand the Problem and Constraints:

   • Read the problem to identify the input format, output requirements, and constraints (e.g., array sizes, value ranges, time limits).
   • Determine if it’s an optimization problem (e.g., maximize profit, minimize cost) or a counting problem (e.g., number of ways to achieve a goal).
   • Example: For LeetCode #70 (Climbing Stairs), the goal is to count distinct ways to climb n stairs with 1 or 2 steps.

2. Identify the DP Pattern:

   • Recognize if the problem fits a known DP pattern (e.g., 1D DP, 2D DP, Subset Sum, LIS, Grid Paths, State Machine, Knapsack, Digit DP, Bitmask DP, Tree DP, Interval DP, Probabilistic DP).
   • Look for overlapping subproblems and optimal substructure, which are hallmarks of DP.
   • Example: For Longest Common Subsequence (LeetCode #1143), the problem involves finding the longest subsequence common to two strings, suggesting a 2D DP approach.

3. Define the State:

   • Determine the variables that represent a subproblem (e.g., index, sum, constraints).
   • State is typically dp[i] (1D), dp[i][j] (2D), or dp[i][j][k] (3D), where each dimension captures a parameter like position, capacity, or condition.
   • Example: In Knapsack, dp[i][w] represents the maximum value for the first i items with weight capacity w.

4. Formulate the Recurrence Relation:

   • Write the relationship between the current state and previous states.
   • Identify choices (e.g., include/exclude an item, move up/left in a grid) and combine results (e.g., max, min, sum).
   • Example: For Climbing Stairs, dp[i] = dp[i-1] + dp[i-2] (ways to climb i stairs = ways to climb i-1 + ways to climb i-2).

5. Determine Base Cases:

   • Identify the smallest subproblems and their solutions (e.g., dp[0], dp[1], or empty inputs).
   • Ensure all edge cases are covered (e.g., empty strings, zero capacity).
   • Example: In Longest Common Subsequence, dp[i][0] = 0 and dp[0][j] = 0 (no common subsequence with empty strings).

6. Choose the Approach: Memoization or Tabulation:

   • Memoization: Top-down, recursive with caching. Use when the state space is sparse or recursion is intuitive.
   • Tabulation: Bottom-up, iterative with arrays. Use for better space efficiency or when iteration is straightforward.
   • Example: For House Robber (LeetCode #198), tabulation with a 1D array is simpler, but memoization works for recursive clarity.

7. Design the Algorithm:

   • Write pseudocode or a plan:

     • Define the state and recurrence.
     • Initialize base cases.
     • Fill the DP table (tabulation) or cache results (memoization).
     • Handle edge cases (e.g., empty inputs, invalid states).

   • Example: For 0/1 Knapsack:

     Initialize dp[i][w] = 0 for all i, w
     Set base cases: dp[0][w] = 0, dp[i][0] = 0
     For each item i:
         For each weight w:
             If weight[i-1] <= w:
                 dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i-1]] + value[i-1])
             Else:
                 dp[i][w] = dp[i-1][w]
     Return dp[n][W]
     
     

8. Optimize Space and Time:

   • Reduce space complexity by using rolling arrays or variables when only recent states are needed.
   • Example: In Climbing Stairs, use two variables instead of an array to store dp[i-1] and dp[i-2], reducing space from O(n) to O(1).
   • Check for redundant computations or unnecessary state variables.

9. Implement the Solution:

   • Use appropriate data structures (e.g., arrays for tabulation, dictionaries for memoization).
   • Handle constraints like modulo arithmetic (e.g., for large combinatorial results) or floating-point precision (e.g., in probabilistic DP).
   • Example: For Word Break (LeetCode #139), use a 1D array to track whether prefixes can be segmented.

10. Test and Debug:

    • Test with small inputs to verify the recurrence (e.g., n = 1, n = 2).
    • Check edge cases: empty inputs, single elements, maximum constraints.
    • Debug common issues: incorrect base cases, index out-of-bounds, or wrong transitions.
    • Example: For Longest Increasing Subsequence (LeetCode #300), test nums = [1,3,2] to ensure dp[i] captures the correct length.

11. Formulate the Answer:

    • Return the result in the required format (e.g., integer, string, boolean).
    • Ensure the output matches the problem’s requirements (e.g., return -1 for no solution in Coin Change, LeetCode #322).

How to Think of a Solution

Thinking through a DP solution involves breaking down the problem, recognizing patterns, and iteratively refining the approach. Here’s how to approach it:

1. Pattern Recognition:
   • Match the problem to known DP patterns:
     • Single array/sequence: 1D DP (e.g., Climbing Stairs, House Robber).
     • Two sequences/grids: 2D DP (e.g., Longest Common Subsequence, Edit Distance).
     • Multiple constraints: 3D DP or Bitmask DP (e.g., Interleaving String, TSP).
     • Trees or intervals: Tree DP or Interval DP (e.g., House Robber III, Burst Balloons).
     • Counting numbers: Digit DP (e.g., Count Numbers with Unique Digits).
   • Example: If the problem involves two strings and a similarity metric (e.g., LeetCode #72, Edit Distance), think 2D DP.
2. Ask Key Questions:
   • What variables define the subproblem? (e.g., index, sum, position).
   • What are the choices at each step? (e.g., include/exclude, move up/left).
   • How do subproblems combine? (e.g., max, min, sum).
   • Example: In Coin Change (LeetCode #322), ask: “How many coins are needed for amount j using the first i coins?”
3. Model the Problem:
   • Represent the problem as a state transition:
     • For 1D DP: Transition between indices (e.g., dp[i] = dp[i-1] + dp[i-2]).
     • For 2D DP: Transition between pairs of indices (e.g., dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + cost).
     • For complex states: Include constraints like bitmasks or tree nodes.
   • Example: In Longest Increasing Subsequence (LeetCode #300), model as finding the longest subsequence ending at each index.
4. Test Intuition with Examples:
   • Use small test cases to build the recurrence:
     • For Climbing Stairs, try n = 3: Ways = ways(2) + ways(1) = 2 + 1 = 3.
   • Check if subproblems overlap (e.g., dp[i-1] is reused in multiple calculations).
   • Example: For Edit Distance, test word1 = "cat", word2 = "cut" to see how operations (insert, delete, replace) build the solution.
5. Contrast with Greedy:
   • Greedy fails when choices are interdependent or require exploring all options.
   • Example: In 0/1 Knapsack, Greedy (taking highest value/weight ratio) fails, but DP tries all combinations.
   • If a single-pass greedy approach seems risky (e.g., House Robber’s non-adjacent constraint), try DP to account for dependencies.