Master Dynamic Programming (DP) Patterns: 12 templates for Coding Interviews

You've spent 100+ hours grinding LeetCode DP problems. You've memorized the solution to Climbing Stairs, Coin Change, and Maximum Subarray. But when a new DP twist appears in your Google interview—one you haven't seen before—your mind draws a blank. You vaguely remember a table, some states, maybe some choices... but you're not sure where to start.

Sound familiar?

The problem isn't your effort—it's pattern recognition. Most engineers memorize solutions instead of grasping the core DP templates that unite different problems. That's why, even after 200+ problems, a single twist can send you back to square one.

Here's the truth: You don't need to brute-force every DP question. You just need to master 12 Dynamic Programming (DP) patterns that appear in over 25% of FAANG interviews—and unlock dozens of problems with a single template.

---

What You'll Learn

By the end of this guide, you'll have:

✅ Mastered all 12 Dynamic Programming (DP) sub-patterns—from 0/1 Knapsack to Interval DP
✅ Developed pattern recognition skills to quickly map any DP problem to the right approach
✅ Practiced 43 curated problems asked at Google, Amazon, Facebook, Apple, and more
✅ Learned when to use each pattern (and how to spot them in interviews)
✅ Identified common pitfalls (so you won't fall for classic DP traps)
✅ Followed a clear practice roadmap to go from DP beginner to interview-ready in 2-3 weeks

---

What is Dynamic Programming (DP) Patterns?

Imagine you're trying to hike to the top of a mountain, but the path splits every few steps, and you don't want to hike the same trail twice. Dynamic Programming is like leaving breadcrumbs—so you never waste time retracing your steps. Instead of brute-forcing every possible path, you remember your solutions to subproblems, so each decision is made only once.

DP patterns are the blueprints for laying down these breadcrumbs. Instead of reinventing the wheel with every new problem, you apply a template—like a chef following a tried-and-true recipe, tweaking only the ingredients as needed.

Core Insight: Most DP problems fall into a few fundamental patterns, each with its own state, choices, and recurrence relation. If you can spot the pattern, you can unlock the solution—no matter how the problem is disguised.

Why This Pattern Matters

1. Unlocks 25%+ of FAANG interviews: DP is one of the most tested skills at Google, Amazon, Meta, Microsoft, and Apple.
2. Transforms brute force to optimal: DP converts exponential-time problems into efficient, real-world solutions.
3. Tests true understanding: Interviewers want to see if you recognize patterns, not just recall code.
4. Real-world impact: DP powers everything from route optimization at Uber to spell correction at Google.

Companies that frequently ask DP questions: Google, Amazon, Meta (Facebook), Microsoft, Apple, Bloomberg, Goldman Sachs, Uber, ByteDance.

---

The 12 Dynamic Programming (DP) Patterns Sub-Patterns

Let’s break down each DP sub-pattern and show you how to recognize and master them.

---

1. 1D Array (0/1 Knapsack, Subset Sum Style)

What it is:
This pattern tackles problems where you must decide, for each item, whether to include it (1) or not (0)—without repetition. The core is a binary choice per item, often with constraints like weight, sum, or cost.

Key insight:
The "either take it or leave it" logic lets you build a DP table (usually a 1D/2D array) where each cell records the best result for a given subset or sum. By remembering results for each possible sum, you avoid redundant work.

How it works:

• Define the state as dp[i][sum] (or dp[sum])—can you achieve sum using the first i items?
• For each item, update the DP by considering both choices: including or excluding the item.
• Return whether the target sum is achievable, or the optimal value.

When to use:

• You need to partition, subset, or select items to meet a sum/target.
• Each item can be used at most once.
• The task is to count/decide subset existence or maximize/minimize a value.
• Classic "yes/no" choices per element.

Recognition triggers:

• "Can you split, partition, or select a subset...?"
• "Each item can be used once."
• Targeting a sum or maximizing/minimizing a value with constraints.

Essential Problems:

Medium:

• ⭐ Partition Equal Subset Sum - Amazon, Facebook
  Context: Can you split an array into two subsets with equal sum?
• Target Sum - Facebook, Amazon, Adobe
  Context: Assign + or - to each number to reach a target sum.

💡 Pro Tip:
Try to compress your DP from 2D to 1D when possible—by updating the array in reverse (so you don’t overwrite values needed for the current iteration).

⚠️ Common Mistake:
Updating the DP array in the wrong order (forwards instead of backwards) can cause overcounting—leading to incorrect answers. Always update from right to left when each item is used at most once.

Example Code Pattern:

PYTHON
Copy
# 0/1 Knapsack-style DP (Subset Sum)
def canPartition(nums):
    target = sum(nums) // 2
    dp = [False] * (target + 1)
    dp[0] = True  # Base case: zero sum is always achievable
    for num in nums:
        for s in range(target, num - 1, -1):  # Backwards
            dp[s] = dp[s] or dp[s - num]
    return dp[target]

Time/Space Complexity:

• Time: O(n * target)
• Space: O(target) (with 1D compression)

---

2. 1D Array (Coin Change / Unbounded Knapsack Style)

What it is:
This pattern fits problems where you can use each item unlimited times—like making change with coins. The focus is on "repetition allowed" with different combinations leading to a target.

Key insight:
By allowing repeated use, you process the DP array forwards, so each subproblem builds on all possible previous combinations.

How it works:

• Define dp[amount] as the number of ways (or min coins) to make up amount.
• For each coin, update all possible amounts from coin to target.
• Each state represents including the current coin any number of times.

When to use:

• Unlimited or repeated use of each item.
• Counting combinations/ways to make a sum.
• "You have infinite supply of ..." or "How many ways to ...?"

Recognition triggers:

• "You can use each number as many times as needed."
• "Find the minimum/maximum number of items to reach a target."
• Coin change, making sum, or combination problems.

Essential Problems:

Medium:

• ⭐ Coin Change - Amazon, Bloomberg, Goldman Sachs, Walmart Labs, Apple
  Context: Find min coins to make a given amount.
• ⭐ Coin Change II
  Context: Count distinct combinations to make up the amount.
• Combination Sum IV - Bloomberg, Wish, Apple

💡 Pro Tip:
Order of loops matters! For unbounded knapsack, loop through coins first, then amounts—this ensures all combinations are considered.

⚠️ Common Mistake:
Reversing the loop order or using a backward loop will miss valid combinations or overcount—always iterate amounts forward for unbounded cases.

Example Code Pattern:

PYTHON
Copy
# Coin Change II - Count combinations (Unbounded Knapsack)
def change(amount, coins):
    dp = [0] * (amount + 1)
    dp[0] = 1  # One way to make amount 0
    for coin in coins:
        for x in range(coin, amount + 1):
            dp[x] += dp[x - coin]
    return dp[amount]

Time/Space Complexity:

• Time: O(n * amount)
• Space: O(amount)

---

3. 1D Array (Fibonacci Style)

What it is:
This is the "building block" DP pattern—where each state depends linearly on one or two previous states. Classic examples: Fibonacci, Climbing Stairs.

Key insight:
You only ever need the last one or two DP values, so you can optimize space to O(1).

How it works:

• Define dp[i] as the answer for the i-th step/state.
• Recurrence: dp[i] = dp[i-1] + dp[i-2] (or similar).
• Base cases for the first 1-2 steps.

When to use:

• The problem can be reduced to "choose last step(s)".
• Each state only depends on the previous one or two.
• Staircase, ways to reach N, or linear "pick/not pick" choices.

Recognition triggers:

• "Number of ways to reach X", "climb stairs", or "decode message".
• Recurrence looks like Fib(n) = Fib(n-1) + Fib(n-2).
• Choices are only to take one or two steps, rob or skip, etc.

Essential Problems:

Easy:

• ⭐ Climbing Stairs - Expedia, Amazon, Apple, Adobe, Goldman Sachs
  Context: Number of ways to reach the top.
• Fibonacci Number - JPMorgan, Amazon, Google, Apple, Facebook
• Min Cost Climbing Stairs - Amazon, Apple

Medium:

• ⭐ House Robber - Cisco, Amazon, Microsoft, Oracle, Bloomberg
  Context: Maximum money you can rob, cannot rob two adjacent houses.
• House Robber II - eBay
• Decode Ways - JPMorgan, Facebook, Google, Cisco, Amazon
• Delete and Earn - Goldman Sachs

💡 Pro Tip:
For simple Fibonacci-style DP, use two variables instead of an array for O(1) space. This is a big plus in interviews.

⚠️ Common Mistake:
Forgetting to set correct base cases (e.g., n=0, n=1) will cause incorrect results—always check edge conditions.

Example Code Pattern:

PYTHON
Copy
# Climbing Stairs - Fib style
def climbStairs(n):
    if n <= 2:
        return n
    a, b = 1, 2  # Ways to reach step 1 and 2
    for _ in range(3, n + 1):
        a, b = b, a + b  # Update with new value
    return b

Time/Space Complexity:

• Time: O(n)
• Space: O(1)

---

4. 1D Array (Kadane’s Algorithm for Max/Min Subarray)

What it is:
Kadane’s is the go-to for finding the maximum (or minimum) sum subarray in linear time. It tracks the best local and global answers in a rolling manner.

Key insight:
At each step, you decide: "Is it better to start fresh at this position, or extend the previous subarray?" A running max/min captures the answer.

How it works:

• Initialize max_ending_here and max_so_far.
• For each element, update: max_ending_here = max(nums[i], max_ending_here + nums[i])
• Update max_so_far with the maximum found so far.

When to use:

• Find max/min sum or product of a contiguous subarray.
• Problems involving "subarray" with optimal sum/product.
• Need to handle negatives/positives efficiently.

Recognition triggers:

• "Find max/min sum/product of a subarray."
• "Contiguous subarray" in the question.
• The need to process elements in order.

Essential Problems:

Medium:

• ⭐ Maximum Subarray - Microsoft, Amazon, Apple, LinkedIn, ByteDance
  Context: Classic Kadane’s—find contiguous subarray with max sum.
• Maximum Product Subarray - Amazon, LinkedIn, Google, Apple, Facebook
  Context: Includes negative numbers—track both min and max at each step.
• Maximum Sum Circular Subarray - Two Sigma, Amazon, Facebook
• Maximum Absolute Sum of Any Subarray

💡 Pro Tip:
For product subarray, maintain both current max and min—because multiplying two negatives can yield a larger positive.

⚠️ Common Mistake:
Resetting the running sum too late/too early, or not handling all-negative arrays—make sure to initialize and update max_so_far properly.

Example Code Pattern:

PYTHON
Copy
# Maximum Subarray - Kadane's Algorithm
def maxSubArray(nums):
    max_ending_here = max_so_far = nums[0]
    for num in nums[1:]:
        max_ending_here = max(num, max_ending_here + num)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

Time/Space Complexity:

• Time: O(n)
• Space: O(1)

---

5. 1D Array (Word Break Style)

What it is:
This pattern checks if a string can be segmented into valid words from a dictionary, or finds all possible segmentations. It's about partitioning strings using DP.

Key insight:
Use a DP array where dp[i] means "can the substring s[0:i] be segmented?" For each end position, check all possible previous cuts.

How it works:

• Initialize dp[0] = True (empty string is segmentable).
• For each i, check all j < i: if dp[j] is True and s[j:i] in the dictionary, set dp[i] = True.
• For "all segmentations" (Word Break II), use recursion+memoization to collect all results.

When to use:

• Segmenting a string into dictionary words.
• "Can/cannot break string into valid parts?"
• "Return all possible segmentations."

Recognition triggers:

• "Given a dictionary, can you segment...?"
• "Return all possible ways to break a string."
• Problems involving string partitioning with constraints.

Essential Problems:

Medium:

• ⭐ Word Break - Facebook, Amazon, Bloomberg, Microsoft, ByteDance
  Context: Can you segment the string?

Hard:

• Word Break II - Facebook, Amazon, Bloomberg, ByteDance, Google
  Context: Return all valid segmentations.

💡 Pro Tip:
For "all segmentations", use memoization to avoid recomputation—otherwise, recursion can explode to exponential time.

⚠️ Common Mistake:
Not initializing dp[0] = True or missing memoization for repeated subproblems—this leads to TLE for large strings.

Example Code Pattern:

PYTHON
Copy
# Word Break - DP approach
def wordBreak(s, wordDict):
    word_set = set(wordDict)
    dp = [False] * (len(s)+1)
    dp[0] = True  # Base: empty string
    for i in range(1, len(s)+1):
        for j in range(i):
            if dp[j] and s[j:i] in word_set:
                dp[i] = True
                break
    return dp[len(s)]

Time/Space Complexity:

• Time: O(n^2)
• Space: O(n)

---

6. 2D Array (Edit Distance / Levenshtein Distance)

What it is:
This pattern solves problems about transforming one string (or sequence) into another with minimum operations (insert, delete, replace).

Key insight:
Each cell dp[i][j] represents the cost to convert the first i chars of string A to the first j chars of string B. Build up the table by considering possible operations at each step.

How it works:

• Initialize first row/column with base cases (empty string transforms).
• For each cell, take the min of: insert, delete, or replace (with costs).
• Fill the DP table, answer is in dp[m][n].

When to use:

• Transforming one string/sequence to another.
• Counting edit distance, or cost to equalize two sequences.
• Problems about insert/delete/replace operations.

Recognition triggers:

• "Minimum number of insertions/deletions/replacements to transform..."
• Edit distance, spell correction, string transformation.

Essential Problems:

Medium:

• ⭐ Edit Distance - Amazon, Microsoft, Google, Square, Palantir Technologies
  Context: Classic problem for spell correction or DNA sequence alignment.
• Minimum ASCII Delete Sum for Two Strings - TripleByte

💡 Pro Tip:
When space is tight, use only two rows (current and previous) to optimize from O(mn) to O(n) space.

⚠️ Common Mistake:
Forgetting to initialize the first row and column (base cases), or not handling equal characters correctly—always check for equality before applying edit operations.

Example Code Pattern:

PYTHON
Copy
# Edit Distance - DP Table
def minDistance(word1, word2):
    m, n = len(word1), len(word2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(m+1):
        dp[i][0] = i  # Deletions
    for j in range(n+1):
        dp[0][j] = j  # Insertions
    for i in range(1, m+1):
        for j in range(1, n+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[m][n]

Time/Space Complexity:

• Time: O(m*n)
• Space: O(m*n) (can optimize to O(n))

---

7. 2D Array (Longest Common Subsequence - LCS)

What it is:
This pattern finds the longest subsequence common to two sequences (not necessarily contiguous). It’s the basis for diff tools and DNA sequence analysis.

Key insight:
Build a DP table where dp[i][j] is the length of LCS for the first i and j characters. If the current chars match, extend; otherwise, take the best previous answer.

How it works:

• Initialize the base row/column to zero.
• For each cell, if chars match: dp[i][j] = dp[i-1][j-1] + 1; else, take max of top or left.
• Result is in dp[m][n].

When to use:

• Finding longest matching subsequence between two strings/lists.
• Problems about insertions/deletions to equalize sequences.
• "What’s the minimum edits to convert one string to another?"

Recognition triggers:

• "Longest common subsequence", "minimum operations", or "insert/delete to make equal".
• Comparing two sequences for overlap or similarity.

Essential Problems:

Medium:

• ⭐ Longest Common Subsequence - Amazon, Microsoft, eBay
  Context: Classic LCS between two strings.
• Delete Operation for Two Strings - Google

Hard:

• Shortest Common Supersequence - Microsoft, Amazon
• Minimum Insertion Steps to Make a String Palindrome - Amazon, LinkedIn

💡 Pro Tip:
To reconstruct the actual sequence, backtrack from dp[m][n]—this is often an interview bonus!

⚠️ Common Mistake:
Mixing up "subarray" (contiguous) and "subsequence" (any order)—be clear on definitions and adjust DP accordingly.

Example Code Pattern:

PYTHON
Copy
# Longest Common Subsequence - DP Table
def longestCommonSubsequence(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

Time/Space Complexity:

• Time: O(m*n)
• Space: O(m*n) (can optimize to O(n))

---

8. 2D Array (Unique Paths on Grid)

What it is:
These problems involve counting or optimizing all possible ways to traverse a grid (often from top-left to bottom-right), possibly with obstacles.

Key insight:
At each cell, the number of ways (or min/max cost) to reach it is based on previous cells—often just the cell above and to the left.

How it works:

• Build a DP table matching the grid size.
• For each cell, set value based on top and left neighbors (or min/max path).
• Handle obstacles by setting cells to zero or infinity.

When to use:

• Counting paths or finding min/max cost on a grid.
• Only moves allowed: down and right (sometimes up/left).
• Obstacles or restrictions may be present.

Recognition triggers:

• "Unique paths", "min/max path sum", "triangle/grid", "obstacles".
• Grid-like input with movement restrictions.

Essential Problems:

Medium:

• ⭐ Unique Paths - Microsoft, Amazon, Facebook, Google, Bloomberg
• ⭐ Minimum Path Sum - Google, Amazon, Goldman Sachs, Facebook, Apple
• Triangle - Amazon, Bloomberg
• Minimum Falling Path Sum - Amazon
• Unique Paths II - Amazon, Bloomberg, Facebook, Microsoft
• Maximal Square - Amazon, IBM, Google, Twitter, ByteDance
• Count Square Submatrices with All Ones - Google, Amazon

💡 Pro Tip:
When movement is restricted (like only right/down), you can often optimize space to a single row or column.

⚠️ Common Mistake:
Not handling obstacles or edges/corners properly—double-check your base cases and how you initialize the first row/column.

Example Code Pattern:

PYTHON
Copy
# Unique Paths with obstacles
def uniquePathsWithObstacles(obstacleGrid):
    m, n = len(obstacleGrid), len(obstacleGrid[0])
    dp = [0] * n
    dp[0] = 1 if obstacleGrid[0][0] == 0 else 0
    for i in range(m):
        for j in range(n):
            if obstacleGrid[i][j] == 1:
                dp[j] = 0
            elif j > 0:
                dp[j] += dp[j-1]
    return dp[-1]

Time/Space Complexity:

• Time: O(m*n)
• Space: O(n)

---

9. Catalan Numbers

What it is:
Catalan numbers count distinct valid arrangements—like valid parentheses, unique BSTs, or ways to triangulate polygons.

Key insight:
The nth Catalan number counts combinations where structures are built recursively: total = sum over all possible left/right divisions.

How it works:

• Use the recurrence: dp[n] = sum(dp[i] * dp[n - i - 1]) for all i in [0, n-1].
• For each possible partition, multiply left and right possibilities.
• Initialize base cases (dp[0] = 1).

When to use:

• Counting valid parenthesis, BSTs, or recursive structures.
• "Number of ways to arrange/construct..."
• Problems with recursive composition.

Recognition triggers:

• "Arrange pairs", "unique BSTs", "different ways to parenthesize".
• Output is a count, not the actual structures.

Essential Problems:

Medium:

• ⭐ Unique Binary Search Trees - Microsoft, Bloomberg
  Context: Number of structurally unique BSTs.
• Unique Binary Search Trees II - Amazon, Google
• Different Ways to Add Parentheses - Microsoft, Flipkart

💡 Pro Tip:
Many problems that seem unrelated (parentheses, BSTs, polygon triangulation) actually share the same Catalan recurrence—try to spot it!

⚠️ Common Mistake:
Not memoizing results for recursive calls—leads to exponential time. Always use DP or memoization.

Example Code Pattern:

PYTHON
Copy
# Unique BSTs - Catalan DP
def numTrees(n):
    dp = [0] * (n+1)
    dp[0] = 1
    for nodes in range(1, n+1):
        for left in range(nodes):
            dp[nodes] += dp[left] * dp[nodes-left-1]
    return dp[n]

Time/Space Complexity:

• Time: O(n^2)
• Space: O(n)

---

10. Interval DP

What it is:
Interval DP is for problems where the answer depends on choosing the best way to break an interval (subarray, substring) into parts—often recursively.

Key insight:
You recursively solve for all subintervals, and the answer for an interval depends on the answers to its possible split points.

How it works:

• Define dp[l][r] as the answer for interval [l, r].
• For each possible split k in [l, r], update: dp[l][r] = max/min over (dp[l][k] + dp[k+1][r] + cost)
• Use memoization to avoid recomputation.

When to use:

• Partitioning intervals to maximize/minimize value.
• Problems about bursting balloons, removing boxes, or matrix chain multiplication.
• Cost/score depends on recursive interval splits.

Recognition triggers:

• "Find minimum/maximum score by breaking/removing/partitioning intervals."
• Explicit mention of choosing a split point or order of operations.

Essential Problems:

Hard:

• ⭐ Burst Balloons - Adobe, Bloomberg, Amazon, Google, Codenation
  Context: Max coins by bursting balloons in the best order.
• Remove Boxes - Apple, Amazon

💡 Pro Tip:
Always memoize subinterval results—otherwise, you'll hit exponential time and TLE.

⚠️ Common Mistake:
Not handling overlapping intervals or failing to use the right dimensions for memoization—double-check your DP indices.

Example Code Pattern:

PYTHON
Copy
# Burst Balloons - Interval DP with memoization
def maxCoins(nums):
    n = len(nums)
    nums = [1] + nums + [1]
    memo = {}
    def dp(left, right):
        if left + 1 == right:
            return 0
        if (left, right) in memo:
            return memo[(left, right)]
        res = 0
        for i in range(left+1, right):
            res = max(res, nums[left]*nums[i]*nums[right] + dp(left, i) + dp(i, right))
        memo[(left, right)] = res
        return res
    return dp(0, n+1)

Time/Space Complexity:

• Time: O(n^3)
• Space: O(n^2)

---

11. Longest Increasing Subsequence (LIS)

What it is:
LIS finds the length (or the sequence) of the longest strictly increasing subsequence in an array—used for sequence optimization.

Key insight:
You can solve it in O(n^2) with DP, or O(n log n) by combining DP and binary search.

How it works:

• DP: For each element, set dp[i] = max(dp[j] + 1) for all j < i where nums[j] < nums[i].
• O(n log n): Maintain a list to track the smallest ending values for increasing subsequences.

When to use:

• Find the longest increasing (or decreasing) subsequence.
• Problems about envelopes, mountains, or sequence optimization.
• Need to optimize for length or structure.

Recognition triggers:

• "Longest increasing/decreasing subsequence".
• "Remove as few as possible to make array X".

Essential Problems:

Medium:

• ⭐ Longest Increasing Subsequence - Apple, Amazon, Facebook, Bloomberg, Citrix
  Context: Classic LIS, O(n log n) solution is interview gold.

Hard:

• Longest Increasing Subsequence II
• Minimum Number of Removals to Make Mountain Array - Microsoft
• Russian Doll Envelopes - Google, Amazon, ByteDance, Uber

💡 Pro Tip:
Master the O(n log n) LIS technique—it impresses interviewers and is surprisingly reusable!

⚠️ Common Mistake:
Confusing "subsequence" with "subarray"—remember, subsequence elements don't need to be contiguous.

Example Code Pattern:

PYTHON
Copy
# LIS O(n log n) using binary search
import bisect
def lengthOfLIS(nums):
    sub = []
    for x in nums:
        i = bisect.bisect_left(sub, x)
        if i == len(sub):
            sub.append(x)
        else:
            sub[i] = x
    return len(sub)

Time/Space Complexity:

• Time: O(n log n)
• Space: O(n)

---

12. Stock Problems

What it is:
This family of problems is about maximizing profit by buying and selling stocks under various constraints (cooldown, limited transactions, etc.).

Key insight:
Model each "state" (day, holding/not holding, transactions left, cooldown) in your DP, and transition between them based on possible actions.

How it works:

• Define DP states: day, holding or not, transactions left, cooldown status.
• At each step, calculate the best action: buy, sell, hold, or cooldown.
• Use recursion with memoization or bottom-up DP.

When to use:

• Buy/sell stock with constraints (cooldown, limited transactions).
• Maximize profit under specific rules.
• Complex state transitions based on actions.

Recognition triggers:

• "Best time to buy and sell stock" with extra rules.
• Limited transactions, cooldown, or multiple stocks.

Essential Problems:

Medium:

• Best Time to Buy and Sell Stock with Cooldown - Amazon, Yahoo

Hard:

• ⭐ Best Time to Buy and Sell Stock III - Amazon, Google
  Context: At most two transactions.
• Best Time to Buy and Sell Stock IV - Amazon, Google, Uber

💡 Pro Tip:
Carefully define your DP state—number of transactions, holding status, and cooldown are common dimensions.

⚠️ Common Mistake:
Forgetting to account for all state transitions (e.g., cooldown, limited transactions)—leads to off-by-one errors. Draw a state diagram if you’re unsure!

Example Code Pattern:

PYTHON
Copy
# Best Time to Buy and Sell Stock with Cooldown
def maxProfit(prices):
    if not prices:
        return 0
    n = len(prices)
    hold, sold, rest = -prices[0], 0, 0
    for price in prices[1:]:
        prev_sold = sold
        sold = hold + price
        hold = max(hold, rest - price)
        rest = max(rest, prev_sold)
    return max(sold, rest)

Time/Space Complexity:

• Time: O(n)
• Space: O(1)

---

How to Master Dynamic Programming (DP) Patterns on Thita.ai

Want to accelerate your DP mastery? Thita.ai is built for pattern-based learning and AI-powered practice.

• Pattern-Based Problem Sets:
  Solve all 43 DP pattern problems with instant feedback—see the DP Pattern Sheet

• AI Hints & Instant Feedback:
  Get real-time, AI-generated hints on each problem—practice now

• Real Interview Simulation:
  Face mock DP interviews with adaptive follow-up questions—simulate now

• Track Your Progress:
  Visualize your strengths and weaknesses across all DP templates—visit your dashboard

• Technical Coaching:
  Chat with our AI Coach for personalized DP guidance and code reviews—try the AI Coach

---

Your Dynamic Programming (DP) Patterns Learning Roadmap

Plan: 2-3 weeks, ~8-10 hours per week. Each day, focus on 2-3 problems, review code patterns, and reflect on recognition triggers.

---

Week 1: Foundations (Easy DP, basic templates)

• Day 1:
  • Climbing Stairs
  • Fibonacci Number
  • Master the Sliding Window Pattern: Complete Guide with Examples — While mastering DP, also explore sliding window techniques to enhance your problem-solving toolkit.
  • For a broader understanding of essential coding patterns, refer to The 90 DSA Patterns That Cover 99% of Coding Interviews to complement your DP studies.