Skip to content

13. Dynamic Programming#

Theory#

Use DP when the problem has optimal substructure (optimal solution built from optimal subsolutions) and overlapping subproblems (same states recomputed in naive recursion).

Five-step framework#

  1. Define state — what does dp[i] or dp[i][j] represent? Name it precisely.
  2. Recurrence — how does state i relate to smaller states?
  3. Base cases — smallest subproblems with known answers.
  4. Iteration order — fill table so dependencies are ready (often left→right, or by increasing capacity).
  5. Reconstruction — if path required, store parent pointers or backtrack from final state.

Top-down vs bottom-up#

Top-down (memo) Bottom-up (tabulation)
Code @cache / @lru_cache on recursion nested loops filling table
Space O(states) memo + O(depth) stack O(states) table
When quick to write; sparse states need full table; space optimization 
from functools import cache

@cache
def dp(i: int) -> int:
    if base(i):
        return base_value
    return combine(dp(i - 1), dp(i - 2))

Common DP families#

Family State hint Examples
0/1 knapsack include/exclude each item LC 416, 494
Unbounded knapsack unlimited use per item LC 322, 518
LCS / edit distance two string indices LC 1143, 72
Grid path (row, col) LC 62, 64
Linear sequence dp[i] from prior indices LC 300 (LIS), 198 (house robber)
Tree DP return value per subtree LC 337, 124

Pitfalls#

  • If a greedy choice is provably optimal, DP is overkill — state why greedy fails before committing to DP.
  • Space optimize 1D rolling arrays when recurrence only needs last k rows (knapsack: one row, iterate right-to-left).
  • State explosion: if dimensions exceed ~10⁶, look for structure (monotonic queue, greedy, or math).

See also: Recursion for memoization and backtracking contrast.

Problems at a glance#

LC Problem
416 Equal Sum Partition ↗
494 Target Sum ↗
1049 Last Stone Weight II ↗
518 Coin Change I – Maximum Number of Ways ↗
322 Coin Change II – Minimum Number of Coins ↗
1891 Maximum Ribbon Cut ↗
516 Longest Palindromic Subsequence ↗
5 Longest Palindromic Substring ↗
647 Count of Palindromic Substrings ↗
1312 Minimum Number of Insertions to Make a String Palindrome ↗
72 Edit Distance ↗
300 Longest Increasing Subsequence ↗
368 Largest Divisible Subset ↗
354 Russian Doll Envelopes ↗
646 Maximum Length of Pair Chain ↗
673 Number of Longest Increasing Subsequence ↗
740 Delete and Earn ↗
1048 Longest String Chain ↗
87 Scramble String ↗
887 Super Egg Drop ↗
1039 Minimum Score Triangulation of Polygon ↗
1130 Minimum Cost Tree From Leaf Values ↗
312 Burst Balloons ↗
70 Climbing Stairs ↗
198 House Robber I ↗
213 House Robber II ↗
91 Decode Ways ↗
1137 Tribonacci Number ↗
53 Maximum Subarray ↗
152 Maximum Product Subarray ↗
1749 Maximum Absolute Sum of Any Subarray ↗
543 Diameter of Binary Tree ↗
124 Maximum Path Sum in Binary Tree ↗
508 Most Frequent Subtree Sum ↗
62 Unique Paths in Grid ↗
64 Minimum Path Sum in Grid ↗
120 Triangle ↗
221 Maximal Square ↗
931 Minimum Falling Path Sum ↗
174 Dungeon Game ↗
741 Cherry Pickup ↗
44 Wildcard Matching ↗
10 Regular Expression Matching ↗
698 Partition to K Equal Sum Subsets ↗
847 Shortest Path Visiting All Nodes ↗
1349 Maximum Students Taking Exam ↗
943 Find the Shortest Superstring ↗
1986 Minimum Number of Work Sessions to Finish Tasks ↗
1434 Number of Ways to Wear Different Hats to Each Other ↗
2305 Fair Distribution of Cookies ↗
233 Number of Digit One ↗
600 Non-negative Integers without Consecutive Ones ↗
902 Numbers At Most N Given Digit Set ↗
1012 Numbers With Repeated Digits ↗
688 Knight Probability in Chessboard ↗
808 Soup Servings ↗
837 New 21 Game ↗
121 Best Time to Buy and Sell Stock ↗
122 Best Time to Buy and Sell Stock II ↗
123 Best Time to Buy and Sell Stock III ↗
188 Best Time to Buy and Sell Stock IV ↗
309 Best Time to Buy and Sell Stock with Cooldown ↗
714 Best Time to Buy and Sell Stock with Transaction Fee ↗
968 Binary Tree Cameras ↗

0-1 Knapsack#

Problem 1: Subset Sum (GeeksforGeeks)#

Problem Statement

Given a set of non-negative integers arr[] and a target sum sum, determine whether a subset of the array exists whose elements add up to exactly sum. Each element can be used at most once.

Example 1:

Input: arr = [3, 34, 4, 12, 5, 2], sum = 9
Output: true
Explanation: Subset {4, 5} sums to 9.

Example 2:

Input: arr = [3, 34, 4, 12, 5, 2], sum = 30
Output: false

Constraints:

  • 1 <= arr.length <= 100
  • 0 <= arr[i], sum <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isSubsetSum(self, arr: list[int], target: int) -> bool:
        n = len(arr)
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = True

        for i in range(1, n + 1):
            for s in range(target + 1):
                if arr[i - 1] <= s:
                    dp[i][s] = dp[i - 1][s] or dp[i - 1][s - arr[i - 1]]
                else:
                    dp[i][s] = dp[i - 1][s]
        return dp[n][target]
Explanation:
dp[i][s] = can first i items form sum s? Skip item i (dp[i-1][s]) or take it if it fits (dp[i-1][s-arr[i-1]]).

Time: O(n × target)  |  Space: O(n × target)

1
2
3
4
5
6
7
8
class Solution:
    def isSubsetSum(self, arr: list[int], target: int) -> bool:
        dp = [False] * (target + 1)
        dp[0] = True
        for num in arr:
            for s in range(target, num - 1, -1):
                dp[s] = dp[s] or dp[s - num]
        return dp[target]
Explanation:
Single row; iterate s right-to-left so each item is used at most once per outer loop.

Time: O(n × target)  |  Space: O(target)

Problem 2: Equal Sum Partition (Leetcode:416)#

Problem Statement

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal, or false otherwise.

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: Partition as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5]
Output: false

Constraints:

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for num in nums:
            for s in range(target, num - 1, -1):
                dp[s] = dp[s] or dp[s - num]
        return dp[target]
Explanation:
Equal partition exists iff some subset sums to total/2. Odd total → impossible.

Time: O(n × sum)  |  Space: O(sum)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False
        target = total // 2
        reachable = {0}
        for num in nums:
            reachable = reachable | {s + num for s in reachable}
            if target in reachable:
                return True
        return target in reachable
Explanation:
Track all achievable sums in a set; early exit when target appears.

Time: O(n × sum) worst case  |  Space: O(sum)

Problem 3: Count of Subset Sum (GeeksforGeeks)#

Problem Statement

Given an array arr[] of non-negative integers and a target sum, count the number of subsets whose elements add up to exactly sum. Each element is used at most once; order does not matter.

Example 1:

Input: arr = [2, 3, 5, 6, 8, 10], sum = 10
Output: 3
Explanation: {2,3,5}, {10}, {2,8}.

Example 2:

Input: arr = [1, 2, 3], sum = 3
Output: 2
Explanation: {1,2}, {3}.

Constraints:

  • 1 <= arr.length <= 100
  • 0 <= arr[i], sum <= 10³
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def countSubsetSum(self, arr: list[int], target: int) -> int:
        dp = [0] * (target + 1)
        dp[0] = 1
        for num in arr:
            for s in range(target, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[target]
Explanation:
dp[s] = number of subsets summing to s. Adding item num: dp[s] += dp[s-num]. Right-to-left preserves 0/1 constraint.

Time: O(n × target)  |  Space: O(target)

Problem 4: Minimum Subset Sum Difference (GeeksforGeeks)#

Problem Statement

Given an array arr[], partition it into two subsets (every element in exactly one subset) such that the absolute difference of their sums is minimized. Return that minimum difference.

Example 1:

Input: arr = [1, 6, 11, 5]
Output: 1
Explanation: Subsets {1, 5, 6} (sum 12) and {11} (sum 11) → |12−11| = 1.

Example 2:

Input: arr = [1, 2, 7, 1, 5]
Output: 0
Explanation: {1, 2, 5} and {7, 1} both sum to 8.

Constraints:

  • 1 <= arr.length <= 30
  • 0 <= arr[i] <= 50
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minimumDifference(self, arr: list[int]) -> int:
        total = sum(arr)
        n = len(arr)
        target = total // 2
        dp = [[False] * (target + 1) for _ in range(n + 1)]
        for i in range(n + 1):
            dp[i][0] = True
        for i in range(1, n + 1):
            for s in range(target + 1):
                dp[i][s] = dp[i - 1][s]
                if arr[i - 1] <= s:
                    dp[i][s] = dp[i][s] or dp[i - 1][s - arr[i - 1]]
        for s in range(target, -1, -1):
            if dp[n][s]:
                return total - 2 * s
        return total
Explanation:
Find largest s1 ≤ total/2 achievable. Subset sums s1 and total−s1 give minimum diff total − 2×s1.

Time: O(n × total)  |  Space: O(n × total)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minimumDifference(self, arr: list[int]) -> int:
        total = sum(arr)
        reachable = {0}
        for num in arr:
            reachable |= {s + num for s in reachable}
        best = 0
        for s in reachable:
            if s <= total // 2:
                best = max(best, s)
        return total - 2 * best
Explanation:
Enumerate all subset sums via set expansion; pick best s ≤ total/2.

Time: O(n × 2^n) worst case  |  Space: O(2^n)

Problem 5: Count of Subsets with Given Difference (GeeksforGeeks)#

Problem Statement

Given an array arr[] and an integer D, count subsets where sum(subset1) − sum(subset2) = D. Every element belongs to exactly one subset.

Example 1:

Input: arr = [1, 1, 2, 3], D = 1
Output: 3

Example 2:

Input: arr = [1, 2, 3], D = 1
Output: 2

Constraints:

  • 1 <= arr.length <= 50
  • 0 <= arr[i], D <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countSubsetsWithDiff(self, arr: list[int], diff: int) -> int:
        total = sum(arr)
        if (total + diff) % 2 or (total - diff) < 0:
            return 0
        target = (total + diff) // 2
        dp = [0] * (target + 1)
        dp[0] = 1
        for num in arr:
            for s in range(target, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[target]
Explanation:
Let S1 − S2 = D and S1 + S2 = total → S1 = (total + D) / 2. Count subsets summing to S1 (must be integer and feasible).

Time: O(n × target)  |  Space: O(target)

Problem 6: Target Sum (Leetcode:494)#

Problem Statement

Given an integer array nums and an integer target, assign each element a + or − sign so that the resulting expression equals target. Return the number of ways.

Example 1:

Input: nums = [1,1,1,1,1], target = 3
Output: 5

Example 2:

Input: nums = [1], target = 1
Output: 1

Constraints:

  • 1 <= nums.length <= 20
  • 0 <= nums[i] <= 1000
  • 0 <= sum(nums[i]) <= 1000
  • −1000 <= target <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        total = sum(nums)
        if (total + target) % 2 or abs(target) > total:
            return 0
        subset_sum = (total + target) // 2
        dp = [0] * (subset_sum + 1)
        dp[0] = 1
        for num in nums:
            for s in range(subset_sum, num - 1, -1):
                dp[s] += dp[s - num]
        return dp[subset_sum]
Explanation:
+num contributes to positive subset sum P; −num does not. Need P − (total−P) = target → P = (total + target)/2.

Time: O(n × sum)  |  Space: O(sum)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def findTargetSumWays(self, nums: list[int], target: int) -> int:
        from functools import cache

        @cache
        def dfs(i: int, curr: int) -> int:
            if i == len(nums):
                return 1 if curr == target else 0
            return dfs(i + 1, curr + nums[i]) + dfs(i + 1, curr - nums[i])

        return dfs(0, 0)
Explanation:
Direct recursion with memo on (index, running_sum). Good for small n ≤ 20.

Time: O(n × sum)  |  Space: O(n × sum)

Problem 7: Last Stone Weight II (Leetcode:1049)#

Problem Statement

You are given an array of integers stones where stones[i] is the weight of the ith stone. On each turn, pick two stones and smash them: if equal, both destroyed; otherwise the lighter is destroyed and the heavier loses the difference in weight. Return the smallest possible weight of the last remaining stone.

Example 1:

Input: stones = [2,7,4,1,8,1]
Output: 1

Example 2:

Input: stones = [31,26,33,21,40]
Output: 23

Constraints:

  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def lastStoneWeightII(self, stones: list[int]) -> int:
        total = sum(stones)
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True
        for w in stones:
            for s in range(target, w - 1, -1):
                dp[s] = dp[s] or dp[s - w]
        for s in range(target, -1, -1):
            if dp[s]:
                return total - 2 * s
        return 0
Explanation:
Optimal strategy partitions stones into two piles with minimum sum difference — equivalent to minimum subset sum difference. Answer = total − 2×best.

Time: O(n × total)  |  Space: O(total)

Unbounded Knapsack#

Problem 1: Rod Cutting (GeeksforGeeks)#

Problem Statement

Given a rod of length n and an array prices[] where prices[i] is the price of a piece of length i+1, determine the maximum revenue obtainable by cutting the rod into pieces and selling them. Each length can be used unlimited times.

Example 1:

Input: n = 8, prices = [1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
Explanation: Cut as 2 + 6 → price 5 + 17 = 22.

Constraints:

  • 1 <= n <= 10³
  • 1 <= prices.length <= n
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def cutRod(self, prices: list[int], n: int) -> int:
        dp = [0] * (n + 1)
        for length in range(1, n + 1):
            for cut in range(1, length + 1):
                dp[length] = max(dp[length], prices[cut - 1] + dp[length - cut])
        return dp[n]
Explanation:
dp[L] = max revenue for rod length L. Try every cut size cut; reuse remainder via dp[L−cut] (unbounded).

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def cutRod(self, prices: list[int], n: int) -> int:
        from functools import cache

        @cache
        def dfs(length: int) -> int:
            if length == 0:
                return 0
            best = 0
            for cut in range(1, length + 1):
                best = max(best, prices[cut - 1] + dfs(length - cut))
            return best

        return dfs(n)
Explanation:
Same recurrence; memo avoids recomputing sub-lengths.

Time: O(n²)  |  Space: O(n)

Problem 2: Coin Change I – Maximum Number of Ways (Leetcode:518)#

Problem Statement

Given an integer array coins of distinct denominations and an integer amount, return the number of combinations that make up that amount. Each coin may be used an unlimited number of times. The answer fits in a 32-bit integer.

Example 1:

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: 5=5, 5=2+2+1, 5=2+1+1+1, 5=1+1+1+1+1.

Example 2:

Input: amount = 3, coins = [2]
Output: 0

Constraints:

  • 1 <= coins.length <= 300
  • 1 <= coins[i] <= 5000
  • 0 <= amount <= 5000
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for a in range(coin, amount + 1):
                dp[a] += dp[a - coin]
        return dp[amount]
Explanation:
Outer loop over coins avoids counting permutations as distinct. dp[a] += ways to form a−coin.

Time: O(amount × coins)  |  Space: O(amount)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def change(self, amount: int, coins: list[int]) -> int:
        dp = [[0] * (len(coins) + 1) for _ in range(amount + 1)]
        for j in range(len(coins) + 1):
            dp[0][j] = 1
        for a in range(1, amount + 1):
            for i in range(len(coins) - 1, -1, -1):
                dp[a][i] = dp[a][i + 1]
                if a >= coins[i]:
                    dp[a][i] += dp[a - coins[i]][i]
        return dp[amount][0]
Explanation:
dp[a][i] = combinations using coins i..end. Take coin (dp[a−coin][i]) or skip (dp[a][i+1]).

Time: O(amount × coins)  |  Space: O(amount × coins)

Problem 3: Coin Change II – Minimum Number of Coins (Leetcode:322)#

Problem Statement

Given an integer array coins and an integer amount, return the fewest number of coins needed to make up that amount. If impossible, return -1. Each coin may be used unlimited times.

Example 1:

Input: coins = [1,2,5], amount = 11
Output: 3
Explanation: 11 = 5 + 5 + 1.

Example 2:

Input: coins = [2], amount = 3
Output: -1

Constraints:

  • 1 <= coins.length <= 12
  • 1 <= coins[i] <= 2³¹ − 1
  • 0 <= amount <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [amount + 1] * (amount + 1)
        dp[0] = 0
        for a in range(1, amount + 1):
            for c in coins:
                if a >= c:
                    dp[a] = min(dp[a], 1 + dp[a - c])
        return dp[amount] if dp[amount] <= amount else -1
Explanation:
dp[a] = min coins for amount a. Try every coin: dp[a] = min(dp[a], 1 + dp[a−c]).

Time: O(amount × coins)  |  Space: O(amount)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        from functools import cache

        @cache
        def dfs(remaining: int) -> int:
            if remaining == 0:
                return 0
            if remaining < 0:
                return float("inf")
            return min(1 + dfs(remaining - c) for c in coins)

        ans = dfs(amount)
        return ans if ans != float("inf") else -1
Explanation:
Recursive min over all coin choices with memo on remaining.

Time: O(amount × coins)  |  Space: O(amount)

Problem 4: Maximum Ribbon Cut (Leetcode:1891)#

Problem Statement

You are given an integer array ribbons and an integer k. You may cut any ribbon into segments of positive integer length (unlimited cuts). Return the maximum length x such that you can obtain at least k ribbons of length x. Return 0 if impossible.

Example 1:

Input: ribbons = [9,7,5], k = 3
Output: 5
Explanation: Cut to get three ribbons of length 5.

Example 2:

Input: ribbons = [7,5,9], k = 4
Output: 4

Constraints:

  • 1 <= ribbons.length <= 10⁵
  • 1 <= ribbons[i] <= 10⁵
  • 1 <= k <= 10⁹
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxLength(self, ribbons: list[int], k: int) -> int:
        def can_cut(length: int) -> bool:
            return sum(r // length for r in ribbons) >= k

        lo, hi = 0, max(ribbons)
        while lo < hi:
            mid = (lo + hi + 1) // 2
            if can_cut(mid):
                lo = mid
            else:
                hi = mid - 1
        return lo
Explanation:
If length x works, any smaller length works too (monotonic). Binary search the maximum feasible x; check by summing ribbon // x.

Time: O(n log max(ribbons))  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxLength(self, ribbons: list[int], k: int) -> int:
        total = sum(ribbons)
        if total < k:
            return 0
        lo, hi = 1, total // k
        while lo <= hi:
            mid = (lo + hi) // 2
            count = sum(r // mid for r in ribbons)
            if count >= k:
                lo = mid + 1
            else:
                hi = mid - 1
        return hi
Explanation:
Upper bound: total // k. Same binary search with hi = mid - 1 variant.

Time: O(n log(total/k))  |  Space: O(1)

Longest Common Subsequence#

Problem 1: Longest Common Substring (GeeksforGeeks)#

Problem Statement

Given two strings s1 and s2, find the length of the longest common substring (contiguous). Unlike subsequence, characters must be adjacent.

Example 1:

Input: s1 = "ABABC", s2 = "BABCA"
Output: 3
Explanation: "BAB" is the longest common substring.

Example 2:

Input: s1 = "abcd", s2 = "efgh"
Output: 0

Constraints:

  • 1 <= s1.length, s2.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def longestCommonSubstring(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        best = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                    best = max(best, dp[i][j])
        return best
Explanation:
dp[i][j] = length of common substring ending at s1[i-1] and s2[j-1]. Reset to 0 on mismatch (implicit). Track global max.

Time: O(m × n)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestCommonSubstring(self, s1: str, s2: str) -> int:
        prev = [0] * (len(s2) + 1)
        best = 0
        for c1 in s1:
            curr = [0]
            for j, c2 in enumerate(s2, 1):
                val = prev[j - 1] + 1 if c1 == c2 else 0
                curr.append(val)
                best = max(best, val)
            prev = curr
        return best
Explanation:
Only previous row needed; val depends on diagonal prev[j-1].

Time: O(m × n)  |  Space: O(n)

Problem 2: Print Longest Common Subsequence (GeeksforGeeks)#

Problem Statement

Given two strings, return one longest common subsequence (not necessarily unique). If none exists, return "".

Example 1:

Input: s1 = "ABCDGH", s2 = "AEDFHR"
Output: "ADH"

Example 2:

Input: s1 = "AGGTAB", s2 = "GXTXAYB"
Output: "GTAB"

Constraints:

  • 1 <= s1.length, s2.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def printLCS(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        i, j = m, n
        result = []
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                result.append(s1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] >= dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
        return "".join(reversed(result))
Explanation:
Standard LCS table, then backtrack from (m,n): match → take char; else move toward larger DP neighbor.

Time: O(m × n)  |  Space: O(m × n)

Problem 3: Shortest Common Supersequence (GeeksforGeeks)#

Problem Statement

Given two strings s1 and s2, find the length of the shortest string that has both s1 and s2 as subsequences.

Example 1:

Input: s1 = "abac", s2 = "cab"
Output: 5
Explanation: "cabac" has length 5.

Example 2:

Input: s1 = "geek", s2 = "eke"
Output: 5

Constraints:

  • 1 <= s1.length, s2.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def shortestCommonSupersequence(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        lcs = dp[m][n]
        return m + n - lcs
Explanation:
Supersequence must include all chars of both strings; shared LCS chars counted once: |SCS| = |s1| + |s2| − LCS.

Time: O(m × n)  |  Space: O(m × n)

Problem 4: Print Shortest Common Supersequence (GeeksforGeeks)#

Problem Statement

Return the actual shortest common supersequence string (any valid answer if multiple exist).

Example 1:

Input: s1 = "abac", s2 = "cab"
Output: "cabac"

Example 2:

Input: s1 = "geek", s2 = "eke"
Output: "geeke"

Constraints:

  • 1 <= s1.length, s2.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def printSCS(self, s1: str, s2: str) -> str:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        i, j = m, n
        result = []
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                result.append(s1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] >= dp[i][j - 1]:
                result.append(s1[i - 1])
                i -= 1
            else:
                result.append(s2[j - 1])
                j -= 1
        result.extend(reversed(s1[:i]))
        result.extend(reversed(s2[:j]))
        return "".join(reversed(result))
Explanation:
Backtrack like LCS print; on mismatch append the char from the side we move away from. Append leftovers at end.

Time: O(m × n)  |  Space: O(m × n)

Problem 5: Minimum Insertions and Deletions to Convert String A to B (GeeksforGeeks)#

Problem Statement

Given strings s1 and s2, find the minimum number of insertions and deletions needed to transform s1 into s2.

Example 1:

Input: s1 = "heap", s2 = "pea"
Output: 3
Explanation: Delete 'h', insert 'p' at start, delete 'p' from end → 2 deletions + 1 insertion.

Example 2:

Input: s1 = "geeksforgeeks", s2 = "geeks"
Output: 8

Constraints:

  • 1 <= s1.length, s2.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minOperations(self, s1: str, s2: str) -> int:
        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        lcs = dp[m][n]
        return (m - lcs) + (n - lcs)
Explanation:
Keep LCS chars; delete (m − LCS) from s1, insert (n − LCS) to match s2.

Time: O(m × n)  |  Space: O(m × n)

Problem 6: Longest Repeating Subsequence (GeeksforGeeks)#

Problem Statement

Find the length of the longest subsequence of a string that appears at least twice in the string (non-overlapping occurrences).

Example 1:

Input: s = "AABEBCDD"
Output: 3
Explanation: "ABD" repeats.

Example 2:

Input: s = "aabb"
Output: 2

Constraints:

  • 1 <= s.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def longestRepeatingSubsequence(self, s: str) -> int:
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == s[j - 1] and i != j:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[n][n]
Explanation:
LCS of string with itself, but only count matches when i ≠ j (non-overlapping positions).

Time: O(n²)  |  Space: O(n²)

Problem 7: Length of Longest Subsequence of A Which is Substring in B (GeeksforGeeks)#

Problem Statement

Given strings A and B, find the length of the longest subsequence of A that is a contiguous substring of B.

Example 1:

Input: A = "ABCD", B = "BACDBD"
Output: 3
Explanation: "ACD" is a subsequence of A and substring "ACD" in B.

Constraints:

  • 1 <= A.length, B.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def longestSubseqSubstring(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        best = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if A[i - 1] == B[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        # Check each subsequence ending state via backtracking is expensive;
        # alternative: try all substrings of B
        for start in range(n):
            for end in range(start, n):
                sub = B[start:end + 1]
                if self._is_subsequence(A, sub):
                    best = max(best, len(sub))
        return best

    def _is_subsequence(self, A: str, sub: str) -> bool:
        j = 0
        for c in A:
            if j < len(sub) and c == sub[j]:
                j += 1
        return j == len(sub)
Explanation:
O(n²) substrings of B; two-pointer check if each is subsequence of A. For large inputs, use DP on (i,j) tracking best contiguous match length in B.

Time: O(m × n²)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def longestSubseqSubstring(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        best = 0
        for start in range(n):
            i = 0
            for j in range(start, n):
                while i < m and (j - start + 1) > (i + 1):
                    i += 1
                if i < m and A[i] == B[j]:
                    i += 1
                    best = max(best, i)
                else:
                    break
        return best
Explanation:
For each start in B, extend while chars match subsequence order in A.

Time: O(m × n)  |  Space: O(1)

Problem 8: Subsequence Pattern Matching (GeeksforGeeks)#

Problem Statement

Given strings s and pattern, determine whether pattern appears as a subsequence of s.

Example 1:

Input: s = "abcde", pattern = "ace"
Output: true

Example 2:

Input: s = "abc", pattern = "acb"
Output: false

Constraints:

  • 1 <= s.length <= 10⁴
  • 1 <= pattern.length <= 10²
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def isSubsequence(self, s: str, pattern: str) -> bool:
        j = 0
        for c in s:
            if j < len(pattern) and c == pattern[j]:
                j += 1
        return j == len(pattern)
Explanation:
Scan s; advance pattern pointer on match. All pattern chars found in order → true.

Time: O(|s| + |pattern|)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isSubsequence(self, s: str, pattern: str) -> bool:
        m, n = len(s), len(pattern)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        for j in range(n + 1):
            dp[0][j] = False
        dp[0][0] = True
        for i in range(1, m + 1):
            dp[i][0] = True
            for j in range(1, n + 1):
                dp[i][j] = dp[i - 1][j]
                if s[i - 1] == pattern[j - 1]:
                    dp[i][j] = dp[i][j] or dp[i - 1][j - 1]
        return dp[m][n]
Explanation:
dp[i][j] = is pattern[:j] subsequence of s[:i]? Useful when preprocessing for many patterns.

Time: O(m × n)  |  Space: O(m × n)

Problem 9: Count How Many Times String A Appears as Subsequence in B (GeeksforGeeks)#

Problem Statement

Given strings A (pattern) and B (text), count how many distinct index sequences in B form A as a subsequence.

Example 1:

Input: A = "rabb", B = "rabbbbit"
Output: 4

Example 2:

Input: A = "abc", B = "abcbc"
Output: 3

Constraints:

  • 1 <= A.length <= 100
  • 1 <= B.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def countSubseqOccurrences(self, A: str, B: str) -> int:
        m, n = len(A), len(B)
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for j in range(n + 1):
            dp[0][j] = 1
        for i in range(1, m + 1):
            dp[i][0] = 0
            for j in range(1, n + 1):
                dp[i][j] = dp[i][j - 1]
                if A[i - 1] == B[j - 1]:
                    dp[i][j] += dp[i - 1][j - 1]
        return dp[m][n]
Explanation:
dp[i][j] = ways to form A[:i] as subsequence in B[:j]. Skip B[j-1] or match if chars equal.

Time: O(m × n)  |  Space: O(m × n)

Problem 10: Longest Palindromic Subsequence (Leetcode:516)#

Problem Statement

Given a string s, return the length of the longest subsequence of s that is a palindrome.

Example 1:

Input: s = "bbbab"
Output: 4
Explanation: "bbbb" is the longest palindromic subsequence.

Example 2:

Input: s = "cbbd"
Output: 2

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i + 1][j - 1]
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][n - 1]
Explanation:
dp[i][j] = LPS length in s[i..j]. Match outer chars → +2 inner; else max of excluding one end.

Time: O(n²)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestPalindromeSubseq(self, s: str) -> int:
        t = s[::-1]
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[n][n]
Explanation:
LPS length equals LCS of s with its reverse.

Time: O(n²)  |  Space: O(n²)

Problem 11: Longest Palindromic Substring (Leetcode:5)#

Problem Statement

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also valid.

Example 2:

Input: s = "cbbd"
Output: "bb"

Constraints:

  • 1 <= s.length <= 1000
  • s consists of digits and English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def longestPalindrome(self, s: str) -> str:
        start = end = 0

        def expand(l: int, r: int) -> None:
            nonlocal start, end
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if r - l > end - start:
                    start, end = l, r
                l -= 1
                r += 1

        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)
        return s[start:end + 1]
Explanation:
Try each center (odd and even length palindromes); expand while chars match.

Time: O(n²)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        best_start, best_len = 0, 1
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    if j - i + 1 > best_len:
                        best_start, best_len = i, j - i + 1
        return s[best_start:best_start + best_len]
Explanation:
dp[i][j] true if s[i..j] palindrome; fill by increasing length.

Time: O(n²)  |  Space: O(n²)

Problem 12: Count of Palindromic Substrings (Leetcode:647)#

Problem Statement

Given a string s, return the number of palindromic substrings in it.

Example 1:

Input: s = "abc"
Output: 3

Example 2:

Input: s = "aaa"
Output: 6

Constraints:

  • 1 <= s.length <= 1000
  • s consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def countSubstrings(self, s: str) -> int:
        count = 0

        def expand(l: int, r: int) -> None:
            nonlocal count
            while l >= 0 and r < len(s) and s[l] == s[r]:
                count += 1
                l -= 1
                r += 1

        for i in range(len(s)):
            expand(i, i)
            expand(i, i + 1)
        return count
Explanation:
Each expansion counts one palindrome; cover odd and even centers.

Time: O(n²)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def countSubstrings(self, s: str) -> int:
        n = len(s)
        dp = [[False] * n for _ in range(n)]
        count = 0
        for i in range(n - 1, -1, -1):
            for j in range(i, n):
                if s[i] == s[j] and (j - i <= 2 or dp[i + 1][j - 1]):
                    dp[i][j] = True
                    count += 1
        return count
Explanation:
Same palindrome DP as LPS substring; count True entries.

Time: O(n²)  |  Space: O(n²)

Problem 13: Minimum Number of Deletions to Make a String Palindrome (GeeksforGeeks)#

Problem Statement

Find the minimum number of deletions required to make a string a palindrome.

Example 1:

Input: s = "aebcbda"
Output: 2
Explanation: Delete 'e' and 'c' → "abdba".

Example 2:

Input: s = "geeksforgeeks"
Output: 8

Constraints:

  • 1 <= s.length <= 10³
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minDeletions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        t = s[::-1]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        lps = dp[n][n]
        return n - lps
Explanation:
Chars in LPS need not be deleted; delete the rest: n − LPS.

Time: O(n²)  |  Space: O(n²)

Problem 14: Minimum Number of Insertions to Make a String Palindrome (Leetcode:1312)#

Problem Statement

Given a string s, return the minimum number of insertions needed to make s a palindrome.

Example 1:

Input: s = "zzazz"
Output: 0

Example 2:

Input: s = "mbadm"
Output: 2
Explanation: Insert 'b' and 'd' → "mbadabdm".

Constraints:

  • 1 <= s.length <= 500
  • s consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minInsertions(self, s: str) -> int:
        n = len(s)
        dp = [[0] * n for _ in range(n)]
        for i in range(n - 1, -1, -1):
            dp[i][i] = 1
            for j in range(i + 1, n):
                if s[i] == s[j]:
                    dp[i][j] = 2 + dp[i + 1][j - 1]
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return n - dp[0][n - 1]
Explanation:
Insertions fill missing mirror chars; minimum = n − longest palindromic subsequence.

Time: O(n²)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minInsertions(self, s: str) -> int:
        t = s[::-1]
        n = len(s)
        dp = [[0] * (n + 1) for _ in range(n + 1)]
        for i in range(1, n + 1):
            for j in range(1, n + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = 1 + dp[i - 1][j - 1]
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return n - dp[n][n]
Explanation:
Same as deletions version; insert chars not in LPS.

Time: O(n²)  |  Space: O(n²)

Problem 15: Edit Distance (Leetcode:72 | GeeksforGeeks)#

Problem Statement

Given two strings word1 and word2, return the minimum number of operations to convert word1 to word2. Allowed operations: insert, delete, or replace a character.

Example 1:

Input: word1 = "horse", word2 = "ros"
Output: 3

Example 2:

Input: word1 = "intention", word2 = "execution"
Output: 5

Constraints:

  • 0 <= word1.length, word2.length <= 500
  • word1 and word2 consist of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        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
        for j in range(n + 1):
            dp[0][j] = j
        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],      # delete
                        dp[i][j - 1],      # insert
                        dp[i - 1][j - 1],  # replace
                    )
        return dp[m][n]
Explanation:
dp[i][j] = min edits for word1[:i] → word2[:j]. Match → no cost; else 1 + min of three operations.

Time: O(m × n)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m, n = len(word1), len(word2)
        prev = list(range(n + 1))
        for i in range(1, m + 1):
            curr = [i] + [0] * n
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    curr[j] = prev[j - 1]
                else:
                    curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
            prev = curr
        return prev[n]
Explanation:
Only previous row needed for recurrence.

Time: O(m × n)  |  Space: O(n)

Longest Increasing Subsequence#

Problem 1: Longest Increasing Subsequence (Leetcode:300)#

Problem Statement

Given an integer array nums, return the length of the longest strictly increasing subsequence.

Example 1:

Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: LIS is [2,3,7,101].

Example 2:

Input: nums = [0,1,0,3,2,3]
Output: 4

Constraints:

  • 1 <= nums.length <= 2500
  • −10⁴ <= nums[i] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        n = len(nums)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
Explanation:
dp[i] = LIS length ending at index i. Extend from any prior j with nums[j] < nums[i].

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def lengthOfLIS(self, nums: list[int]) -> int:
        import bisect

        tails: list[int] = []
        for x in nums:
            pos = bisect.bisect_left(tails, x)
            if pos == len(tails):
                tails.append(x)
            else:
                tails[pos] = x
        return len(tails)
Explanation:
tails[k] = smallest tail of an increasing subsequence of length k+1. Binary search placement gives O(n log n).

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

Problem 2: Largest Divisible Subset (Leetcode:368)#

Problem Statement

Given an integer array nums, return the largest subset such that every pair (a, b) satisfies a % b == 0 or b % a == 0. Return any valid answer.

Example 1:

Input: nums = [1,2,3]
Output: [1,2]
Explanation: [1,3] is also valid.

Example 2:

Input: nums = [1,2,4,8]
Output: [1,2,4,8]

Constraints:

  • 1 <= nums.length <= 1000
  • 1 <= nums[i] <= 10⁹
  • All elements are distinct.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)
        dp = [1] * n
        parent = [-1] * n
        best_idx = 0
        for i in range(n):
            for j in range(i):
                if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    parent[i] = j
            if dp[i] > dp[best_idx]:
                best_idx = i
        result = []
        while best_idx != -1:
            result.append(nums[best_idx])
            best_idx = parent[best_idx]
        return result[::-1]
Explanation:
Sort so divisibility only needs check against smaller elements. Track parent to reconstruct subset.

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution:
    def largestDivisibleSubset(self, nums: list[int]) -> list[int]:
        nums.sort()
        n = len(nums)
        memo: dict[int, int] = {}

        def dfs(i: int) -> int:
            if i in memo:
                return memo[i]
            best = 1
            for j in range(i):
                if nums[i] % nums[j] == 0:
                    best = max(best, 1 + dfs(j))
            memo[i] = best
            return best

        start = max(range(n), key=dfs)
        result = []
        cur = start
        while cur >= 0:
            result.append(nums[cur])
            nxt = -1
            for j in range(cur):
                if nums[cur] % nums[j] == 0 and dfs(j) + 1 == dfs(cur):
                    nxt = j
                    break
            cur = nxt
        return result
Explanation:
Same recurrence via memoized DFS; reconstruct by following decreasing chain lengths.

Time: O(n²)  |  Space: O(n)

Problem 3: Russian Doll Envelopes (Leetcode:354)#

Problem Statement

Given envelopes [width, height], one envelope fits inside another if both dimensions are strictly larger. Return the maximum number of envelopes you can nest.

Example 1:

Input: envelopes = [[5,4],[6,4],[6,7],[2,3]]
Output: 3
Explanation: [2,3] → [5,4] → [6,7].

Example 2:

Input: envelopes = [[1,1],[1,1],[1,1]]
Output: 1

Constraints:

  • 1 <= envelopes.length <= 10⁵
  • envelopes[i].length == 2
  • 1 <= width_i, height_i <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        import bisect

        envelopes.sort(key=lambda e: (e[0], -e[1]))
        tails: list[int] = []
        for _, h in envelopes:
            pos = bisect.bisect_left(tails, h)
            if pos == len(tails):
                tails.append(h)
            else:
                tails[pos] = h
        return len(tails)
Explanation:
Sort by width ascending, height descending (same width cannot nest). LIS on heights via patience sorting.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxEnvelopes(self, envelopes: list[list[int]]) -> int:
        envelopes.sort(key=lambda e: (e[0], -e[1]))
        n = len(envelopes)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if envelopes[j][1] < envelopes[i][1]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
Explanation:
Classic LIS on heights after sort; simpler but O(n²).

Time: O(n²)  |  Space: O(n)

Problem 4: Maximum Length of Pair Chain (Leetcode:646)#

Problem Statement

Given pairs [a, b] where a < b, a chain satisfies pairs[i][1] < pairs[j][0] for consecutive pairs. Return the longest chain length.

Example 1:

Input: pairs = [[1,2],[2,3],[3,4]]
Output: 2
Explanation: [1,2] → [3,4].

Example 2:

Input: pairs = [[1,2],[7,8],[4,5]]
Output: 3

Constraints:

  • 1 <= pairs.length <= 1000
  • −1000 <= pairs[i][0], pairs[i][1] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort(key=lambda p: p[1])
        count = 0
        end = float("-inf")
        for a, b in pairs:
            if a > end:
                count += 1
                end = b
        return count
Explanation:
Sort by end time; greedily pick next non-overlapping pair. Equivalent to LIS with O(n log n) greedy.

Time: O(n log n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def findLongestChain(self, pairs: list[list[int]]) -> int:
        pairs.sort()
        n = len(pairs)
        dp = [1] * n
        for i in range(n):
            for j in range(i):
                if pairs[j][1] < pairs[i][0]:
                    dp[i] = max(dp[i], dp[j] + 1)
        return max(dp)
Explanation:
dp[i] = longest chain ending at pair i; extend when prior end < current start.

Time: O(n²)  |  Space: O(n)

Problem 5: Number of Longest Increasing Subsequence (Leetcode:673)#

Problem Statement

Given an integer array nums, return the number of longest increasing subsequences. Since the answer may be large, return it modulo 10⁹ + 7.

Example 1:

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: [1,3,4,7] and [1,3,5,7].

Example 2:

Input: nums = [2,2,2,2,2]
Output: 5

Constraints:

  • 1 <= nums.length <= 2000
  • −10⁶ <= nums[i] <= 10⁶
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        length = [1] * n
        count = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if length[j] + 1 > length[i]:
                        length[i] = length[j] + 1
                        count[i] = count[j]
                    elif length[j] + 1 == length[i]:
                        count[i] = (count[i] + count[j]) % MOD
        max_len = max(length)
        return sum(c for l, c in zip(length, count) if l == max_len) % MOD
Explanation:
Track both LIS length ending at i and count of such LIS. Sum counts where length equals global max.

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def findNumberOfLIS(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        vals = sorted(set(nums))
        rank = {v: i + 1 for i, v in enumerate(vals)}
        n = len(vals)
        bit_len = [0] * (n + 1)
        bit_cnt = [0] * (n + 1)

        def update(i: int, length: int, ways: int) -> None:
            while i <= n:
                if length > bit_len[i]:
                    bit_len[i] = length
                    bit_cnt[i] = ways
                elif length == bit_len[i]:
                    bit_cnt[i] = (bit_cnt[i] + ways) % MOD
                i += i & -i

        def query(i: int) -> tuple[int, int]:
            best_len, best_cnt = 0, 0
            while i > 0:
                if bit_len[i] > best_len:
                    best_len = bit_len[i]
                    best_cnt = bit_cnt[i]
                elif bit_len[i] == best_len:
                    best_cnt = (best_cnt + bit_cnt[i]) % MOD
                i -= i & -i
            return best_len, best_cnt

        max_len, ans = 0, 0
        for x in nums:
            r = rank[x]
            prev_len, prev_cnt = query(r - 1)
            cur_len = prev_len + 1
            cur_cnt = prev_cnt if prev_len else 1
            update(r, cur_len, cur_cnt)
            if cur_len > max_len:
                max_len, ans = cur_len, cur_cnt
            elif cur_len == max_len:
                ans = (ans + cur_cnt) % MOD
        return ans
Explanation:
Process left-to-right; Fenwick tree stores best (length, count) for values < current. O(n log n) for large n.

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

Problem 6: Delete and Earn (Leetcode:740)#

Problem Statement

Given integer array nums, in one move pick any nums[i], earn nums[i] points, and delete all elements equal to nums[i], nums[i]−1, and nums[i]+1. Return the maximum points.

Example 1:

Input: nums = [3,4,2]
Output: 6
Explanation: Delete 4 → earn 4; delete 2 → earn 2.

Example 2:

Input: nums = [2,2,3,3,3,4]
Output: 9
Explanation: Delete all 3's → 9 points.

Constraints:

  • 1 <= nums.length <= 2 × 10⁴
  • 1 <= nums[i] <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        max_val = max(nums)
        earn = [0] * (max_val + 1)
        for x in nums:
            earn[x] += x
        prev2, prev1 = 0, earn[0]
        for v in range(1, max_val + 1):
            cur = max(prev1, prev2 + earn[v])
            prev2, prev1 = prev1, cur
        return prev1
Explanation:
Aggregate points per value. Choosing value v conflicts with v−1; classic House Robber on the value line.

Time: O(n + max_val)  |  Space: O(max_val)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def deleteAndEarn(self, nums: list[int]) -> int:
        from functools import cache

        max_val = max(nums)
        earn = [0] * (max_val + 1)
        for x in nums:
            earn[x] += x

        @cache
        def dfs(v: int) -> int:
            if v > max_val:
                return 0
            return max(dfs(v + 1), earn[v] + dfs(v + 2))

        return dfs(0)
Explanation:
At value v, skip or take earn[v] and jump to v+2.

Time: O(max_val)  |  Space: O(max_val)

Problem 7: Longest String Chain (Leetcode:1048)#

Problem Statement

Given an array of words where each word differs from its predecessor by exactly one inserted letter, return the length of the longest such word chain. Each word may be used at most once.

Example 1:

Input: words = ["a","b","ba","bca","bda","bdca"]
Output: 4
Explanation: "a" → "ba" → "bda" → "bdca".

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5

Constraints:

  • 1 <= words.length <= 1000
  • 1 <= words[i].length <= 16
  • All strings are lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        words.sort(key=len)
        dp: dict[str, int] = {w: 1 for w in words}
        best = 1

        def is_predecessor(a: str, b: str) -> bool:
            if len(b) != len(a) + 1:
                return False
            i = j = 0
            while i < len(a) and j < len(b):
                if a[i] == b[j]:
                    i += 1
                j += 1
            return i == len(a)

        for w in words:
            for k in range(len(w)):
                pred = w[:k] + w[k + 1:]
                if pred in dp:
                    dp[w] = max(dp[w], dp[pred] + 1)
            best = max(best, dp[w])
        return best
Explanation:
Sort by length. For each word, try removing one char to find predecessor; extend chain like LIS.

Time: O(n × L²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestStrChain(self, words: list[str]) -> int:
        word_set = set(words)
        memo: dict[str, int] = {}

        def dfs(w: str) -> int:
            if w in memo:
                return memo[w]
            best = 1
            for k in range(len(w)):
                pred = w[:k] + w[k + 1:]
                if pred in word_set:
                    best = max(best, 1 + dfs(pred))
            memo[w] = best
            return best

        return max(dfs(w) for w in words)
Explanation:
Memoized DFS from each word backward via one-char deletions.

Time: O(n × L²)  |  Space: O(n × L)

Matrix Chain Multiplication#

Problem 1: Scramble String (Leetcode:87)#

Problem Statement

Given strings s1 and s2 of the same length, determine if s2 is a scrambled version of s1. A scramble splits s1 into x and y, optionally swaps them, and recursively scrambles each part.

Example 1:

Input: s1 = "great", s2 = "rgeat"
Output: true

Example 2:

Input: s1 = "abcde", s2 = "caebd"
Output: false

Constraints:

  • s1.length == s2.length
  • 1 <= s1.length <= 30
  • s1 and s2 consist of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        n = len(s1)
        dp = [[[False] * (n + 1) for _ in range(n + 1)] for _ in range(n + 1)]
        for i in range(n):
            dp[1][i][i] = s1[i] == s2[i]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                for j in range(n - length + 1):
                    for k in range(1, length):
                        no_swap = dp[k][i][j] and dp[length - k][i + k][j + k]
                        swap = dp[k][i][j + length - k] and dp[length - k][i + k][j]
                        if no_swap or swap:
                            dp[length][i][j] = True
                            break
        return dp[n][0][0]
Explanation:
dp[len][i][j] = is s1[i:i+len] scramble of s2[j:j+len]? Try every split k; match direct or swapped children.

Time: O(n⁴)  |  Space: O(n³)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def isScramble(self, s1: str, s2: str) -> bool:
        from functools import cache

        @cache
        def dfs(a: str, b: str) -> bool:
            if a == b:
                return True
            if sorted(a) != sorted(b):
                return False
            n = len(a)
            for k in range(1, n):
                if (dfs(a[:k], b[:k]) and dfs(a[k:], b[k:])) or (
                    dfs(a[:k], b[n - k:]) and dfs(a[k:], b[: n - k])
                ):
                    return True
            return False

        return dfs(s1, s2)
Explanation:
Same split logic recursively; character-sort prune for early false.

Time: O(n⁴)  |  Space: O(n³)

Problem 2: Super Egg Drop (Leetcode:887)#

Problem Statement

You have k eggs and a building with n floors. Find the minimum number of moves to determine the critical floor (lowest where egg breaks) with optimal strategy.

Example 1:

Input: k = 1, n = 2
Output: 2

Example 2:

Input: k = 2, n = 6
Output: 3

Constraints:

  • 1 <= k <= 100
  • 1 <= n <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [[0] * (n + 1) for _ in range(k + 1)]
        for f in range(1, n + 1):
            dp[1][f] = f
        for eggs in range(2, k + 1):
            for floors in range(1, n + 1):
                lo, hi = 1, floors
                dp[eggs][floors] = floors
                while lo <= hi:
                    mid = (lo + hi) // 2
                    broken = dp[eggs - 1][mid - 1]
                    intact = dp[eggs][floors - mid]
                    worst = 1 + max(broken, intact)
                    dp[eggs][floors] = min(dp[eggs][floors], worst)
                    if broken > intact:
                        hi = mid - 1
                    else:
                        lo = mid + 1
        return dp[k][n]
Explanation:
dp[e][f] = min moves with e eggs and f floors. Drop at mid: worst case is max(break, survive). Binary search optimal mid.

Time: O(k × n log n)  |  Space: O(k × n)

1
2
3
4
5
6
7
8
9
class Solution:
    def superEggDrop(self, k: int, n: int) -> int:
        dp = [0] * (k + 1)
        moves = 0
        while dp[k] < n:
            moves += 1
            for eggs in range(k, 0, -1):
                dp[eggs] = dp[eggs] + dp[eggs - 1] + 1
        return moves
Explanation:
dp[e] = max floors solvable with e eggs in current moves. Increment moves until dp[k] >= n. O(k × answer).

Time: O(k log n)  |  Space: O(k)

Problem 3: Minimum Score Triangulation of Polygon (Leetcode:1039)#

Problem Statement

Given n vertices labeled 0..n-1 with values values[i], triangulate the polygon by adding diagonals. Score of triangle (i,j,k) is values[i]*values[j]*values[k]. Return minimum total score.

Example 1:

Input: values = [1,2,3]
Output: 6

Example 2:

Input: values = [3,7,4,5]
Output: 144

Constraints:

  • n == values.length
  • 3 <= n <= 50
  • 1 <= values[i] <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minScoreTriangulation(self, values: list[int]) -> int:
        n = len(values)
        dp = [[0] * n for _ in range(n)]
        for length in range(3, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = float("inf")
                for k in range(i + 1, j):
                    cost = values[i] * values[k] * values[j]
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + cost)
        return dp[0][n - 1]
Explanation:
dp[i][j] = min score to triangulate polygon slice from vertex i to j. Pick last triangle vertex k between them.

Time: O(n³)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def minScoreTriangulation(self, values: list[int]) -> int:
        from functools import cache

        @cache
        def dfs(i: int, j: int) -> int:
            if j - i + 1 < 3:
                return 0
            best = float("inf")
            for k in range(i + 1, j):
                cost = values[i] * values[k] * values[j]
                best = min(best, dfs(i, k) + dfs(k, j) + cost)
            return best

        return dfs(0, len(values) - 1)
Explanation:
Same recurrence with memo on (i, j) interval.

Time: O(n³)  |  Space: O(n²)

Problem 4: Minimum Cost Tree From Leaf Values (Leetcode:1130)#

Problem Statement

Given positive integers arr, build a binary tree where each node value equals max of its subtree leaves. Cost to merge adjacent nodes is max(left) * max(right). Return minimum total merge cost.

Example 1:

Input: arr = [6,2,4]
Output: 32
Explanation: Merge 2 and 4 (cost 8), then with 6 (cost 48)... optimal gives 32.

Example 2:

Input: arr = [4,11]
Output: 44

Constraints:

  • 2 <= arr.length <= 50
  • 1 <= arr[i] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def mctFromLeafValues(self, arr: list[int]) -> int:
        n = len(arr)
        dp = [[0] * n for _ in range(n)]
        max_in = [[0] * n for _ in range(n)]
        for i in range(n):
            max_in[i][i] = arr[i]
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                max_in[i][j] = max(max_in[i][j - 1], arr[j])
                dp[i][j] = float("inf")
                for k in range(i, j):
                    cost = max_in[i][k] * max_in[k + 1][j]
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + cost)
        return dp[0][n - 1]
Explanation:
Split interval at k; merge cost uses max leaf in each half. Classic matrix-chain pattern on array intervals.

Time: O(n³)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def mctFromLeafValues(self, arr: list[int]) -> int:
        stack: list[int] = []
        res = 0
        for x in arr + [float("inf")]:
            while stack and stack[-1] <= x:
                mid = stack.pop()
                left = stack[-1] if stack else float("inf")
                res += mid * min(left, x)
            stack.append(x)
        return res
Explanation:
Greedy: always merge smaller adjacent max first. Stack tracks decreasing leaf maxima.

Time: O(n)  |  Space: O(n)

Problem 5: Burst Balloons (Leetcode:312)#

Problem Statement

Given n balloons with integers nums, bursting balloon i adds nums[i-1] * nums[i] * nums[i+1] coins (out-of-bounds treated as 1). Return maximum coins obtainable.

Example 1:

Input: nums = [3,1,5,8]
Output: 167

Example 2:

Input: nums = [1,5]
Output: 10

Constraints:

  • 1 <= nums.length <= 500
  • 0 <= nums[i] <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        balloons = [1] + nums + [1]
        n = len(balloons)
        dp = [[0] * n for _ in range(n)]
        for length in range(3, n + 1):
            for left in range(n - length + 1):
                right = left + length - 1
                for k in range(left + 1, right):
                    coins = (
                        balloons[left]
                        * balloons[k]
                        * balloons[right]
                        + dp[left][k]
                        + dp[k][right]
                    )
                    dp[left][right] = max(dp[left][right], coins)
        return dp[0][n - 1]
Explanation:
Pad with 1s. dp[l][r] = max coins in open interval (l,r) excluding boundaries. Choose k as last balloon burst inside interval.

Time: O(n³)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxCoins(self, nums: list[int]) -> int:
        from functools import cache

        balloons = [1] + nums + [1]

        @cache
        def dfs(l: int, r: int) -> int:
            if r - l < 2:
                return 0
            best = 0
            for k in range(l + 1, r):
                best = max(
                    best,
                    balloons[l] * balloons[k] * balloons[r]
                    + dfs(l, k)
                    + dfs(k, r),
                )
            return best

        return dfs(0, len(balloons) - 1)
Explanation:
Same "last burst" recurrence; memo avoids recomputing intervals.

Time: O(n³)  |  Space: O(n²)

Fibonacci#

Problem 1: Climbing Stairs (Leetcode:70)#

Problem Statement

You are climbing a staircase with n steps. Each time you can climb 1 or 2 steps. In how many distinct ways can you reach the top?

Example 1:

Input: n = 2
Output: 2
Explanation: 1+1 or 2.

Example 2:

Input: n = 3
Output: 3

Constraints:

  • 1 <= n <= 45
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 2:
            return n
        prev2, prev1 = 1, 2
        for _ in range(3, n + 1):
            prev2, prev1 = prev1, prev2 + prev1
        return prev1
Explanation:
dp[i] = dp[i-1] + dp[i-2]: reach step i from one or two steps below. Pure Fibonacci.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def climbStairs(self, n: int) -> int:
        def mat_mul(A: list[list[int]], B: list[list[int]]) -> list[list[int]]:
            return [
                [A[0][0] * B[0][0] + A[0][1] * B[1][0],
                 A[0][0] * B[0][1] + A[0][1] * B[1][1]],
                [A[1][0] * B[0][0] + A[1][1] * B[1][0],
                 A[1][0] * B[0][1] + A[1][1] * B[1][1]],
            ]

        def mat_pow(M: list[list[int]], p: int) -> list[list[int]]:
            res = [[1, 0], [0, 1]]
            while p:
                if p & 1:
                    res = mat_mul(res, M)
                M = mat_mul(M, M)
                p >>= 1
            return res

        if n <= 2:
            return n
        M = [[1, 1], [1, 0]]
        res = mat_pow(M, n)
        return res[0][0]
Explanation:
Fibonacci via [[1,1],[1,0]]^n. O(log n) for very large n.

Time: O(log n)  |  Space: O(1)

Problem 2: House Robber I (Leetcode:198)#

Problem Statement

Given non-negative integers representing money in each house, return the maximum amount you can rob without robbing two adjacent houses.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (1) and house 3 (3).

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400
Code and Explanation 

1
2
3
4
5
6
class Solution:
    def rob(self, nums: list[int]) -> int:
        prev2 = prev1 = 0
        for x in nums:
            prev2, prev1 = prev1, max(prev1, prev2 + x)
        return prev1
Explanation:
At each house: rob (prev2 + x) or skip (prev1). Fibonacci-like recurrence on running max.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def rob(self, nums: list[int]) -> int:
        from functools import cache

        @cache
        def dfs(i: int) -> int:
            if i >= len(nums):
                return 0
            return max(nums[i] + dfs(i + 2), dfs(i + 1))

        return dfs(0)
Explanation:
Direct recursion: take house i and jump +2, or skip to i+1.

Time: O(n)  |  Space: O(n)

Problem 3: House Robber II (Leetcode:213)#

Problem Statement

Houses are arranged in a circle — the first and last house are adjacent. Return the maximum rob amount without robbing adjacent houses.

Example 1:

Input: nums = [2,3,2]
Output: 3

Example 2:

Input: nums = [1,2,3,1]
Output: 4

Constraints:

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def rob(self, nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]

        def rob_line(arr: list[int]) -> int:
            prev2 = prev1 = 0
            for x in arr:
                prev2, prev1 = prev1, max(prev1, prev2 + x)
            return prev1

        return max(rob_line(nums[:-1]), rob_line(nums[1:]))
Explanation:
Circle breaks into two cases: exclude first house or exclude last. Run House Robber I on each segment.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def rob(self, nums: list[int]) -> int:
        n = len(nums)
        if n == 1:
            return nums[0]
        dp0 = [0] * n  # cannot take nums[0]
        dp1 = [0] * n  # can take nums[0]
        dp0[0] = 0
        dp1[0] = nums[0]
        for i in range(1, n):
            dp0[i] = max(dp0[i - 1], dp0[i - 2] + nums[i] if i > 1 else nums[i])
            if i < n - 1:
                dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i])
            else:
                dp1[i] = dp1[i - 1]
        return max(dp0[-1], dp1[-1])
Explanation:
Track states with/without first house taken; forbid first+last together at end.

Time: O(n)  |  Space: O(n)

Problem 4: Decode Ways (Leetcode:91)#

Problem Statement

Given a string s containing digits, return the number of ways to decode it ('1'→'A' … '26'→'Z'). A valid decoding maps the whole string.

Example 1:

Input: s = "12"
Output: 2
Explanation: "AB" (1,2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3

Constraints:

  • 1 <= s.length <= 100
  • s contains only digits and may contain leading zeros.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        n = len(s)
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            if s[i - 1] != "0":
                dp[i] += dp[i - 1]
            two = int(s[i - 2 : i])
            if 10 <= two <= 26:
                dp[i] += dp[i - 2]
        return dp[n]
Explanation:
dp[i] = ways to decode prefix length i. Single digit if not '0'; two-digit if 10–26.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def numDecodings(self, s: str) -> int:
        if s[0] == "0":
            return 0
        prev2, prev1 = 1, 1
        for i in range(2, len(s) + 1):
            cur = 0
            if s[i - 1] != "0":
                cur += prev1
            two = int(s[i - 2 : i])
            if 10 <= two <= 26:
                cur += prev2
            prev2, prev1 = prev1, cur
        return prev1
Explanation:
Only need previous two DP values — Fibonacci-like with validity checks.

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

Problem 5: Tribonacci Number (Leetcode:1137)#

Problem Statement

The Tribonacci sequence T(n) satisfies T(0)=0, T(1)=1, T(2)=1, and T(n+3)=T(n)+T(n+1)+T(n+2). Given n, return T(n).

Example 1:

Input: n = 4
Output: 4
Explanation: 0,1,1,2,4.

Example 2:

Input: n = 25
Output: 1389537

Constraints:

  • 0 <= n <= 37
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def tribonacci(self, n: int) -> int:
        if n == 0:
            return 0
        if n <= 2:
            return 1
        t0, t1, t2 = 0, 1, 1
        for _ in range(3, n + 1):
            t0, t1, t2 = t1, t2, t0 + t1 + t2
        return t2
Explanation:
Generalized Fibonacci with three-term recurrence; keep last three values.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def tribonacci(self, n: int) -> int:
        from functools import cache

        @cache
        def dfs(k: int) -> int:
            if k == 0:
                return 0
            if k <= 2:
                return 1
            return dfs(k - 1) + dfs(k - 2) + dfs(k - 3)

        return dfs(n)
Explanation:
Direct memoized recursion; fine for small n ≤ 37.

Time: O(n)  |  Space: O(n)

Kadane's Algorithm#

Problem 1: Maximum Subarray (Leetcode:53)#

Problem Statement

Given an integer array nums, find the contiguous subarray with the largest sum and return its sum.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] sums to 6.

Example 2:

Input: nums = [1]
Output: 1

Constraints:

  • 1 <= nums.length <= 10⁵
  • −10⁴ <= nums[i] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        best = curr = nums[0]
        for x in nums[1:]:
            curr = max(x, curr + x)
            best = max(best, curr)
        return best
Explanation:
curr = max sum ending here; either extend previous subarray or start fresh at x.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxSubArray(self, nums: list[int]) -> int:
        def cross_max(lo: int, mid: int, hi: int) -> int:
            left_sum = float("-inf")
            s = 0
            for i in range(mid, lo - 1, -1):
                s += nums[i]
                left_sum = max(left_sum, s)
            right_sum = float("-inf")
            s = 0
            for i in range(mid + 1, hi + 1):
                s += nums[i]
                right_sum = max(right_sum, s)
            return left_sum + right_sum

        def dc(lo: int, hi: int) -> int:
            if lo == hi:
                return nums[lo]
            mid = (lo + hi) // 2
            return max(dc(lo, mid), dc(mid + 1, hi), cross_max(lo, mid, hi))

        return dc(0, len(nums) - 1)
Explanation:
Max subarray lies entirely left, right, or crossing mid. O(n log n) alternative.

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

Problem 2: Maximum Product Subarray (Leetcode:152)#

Problem Statement

Given an integer array nums, find a contiguous subarray with the largest product and return the product.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6

Example 2:

Input: nums = [-2,0,-1]
Output: 0

Constraints:

  • 1 <= nums.length <= 2 × 10⁴
  • −10 <= nums[i] <= 10
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        best = max_prod = min_prod = nums[0]
        for x in nums[1:]:
            if x < 0:
                max_prod, min_prod = min_prod, max_prod
            max_prod = max(x, max_prod * x)
            min_prod = min(x, min_prod * x)
            best = max(best, max_prod)
        return best
Explanation:
Negative flip makes min product become max. Track both extremes at each step (Kadane variant).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxProduct(self, nums: list[int]) -> int:
        def kadane(arr: list[int]) -> int:
            best = curr = arr[0]
            for x in arr[1:]:
                curr = max(x, curr * x)
                best = max(best, curr)
            return best

        pos = kadane(nums)
        neg = kadane(nums[::-1])
        return max(pos, neg)
Explanation:
Forward pass for positive-heavy max; reverse pass catches products spanning negatives. Handle zeros implicitly.

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

Problem 3: Maximum Absolute Sum of Any Subarray (Leetcode:1749)#

Problem Statement

Given an integer array nums, return the maximum absolute value of the sum of any non-empty subarray.

Example 1:

Input: nums = [1,-3,2,3,-4]
Output: 5
Explanation: Subarray [2,3] has absolute sum 5.

Example 2:

Input: nums = [2,-5,1,-4,3,-3]
Output: 8

Constraints:

  • 1 <= nums.length <= 10⁵
  • −10⁴ <= nums[i] <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        max_sum = min_sum = 0
        curr_max = curr_min = 0
        for x in nums:
            curr_max = max(x, curr_max + x)
            curr_min = min(x, curr_min + x)
            max_sum = max(max_sum, curr_max)
            min_sum = min(min_sum, curr_min)
        return max(abs(max_sum), abs(min_sum))
Explanation:
Run Kadane for maximum and minimum subarray sums; answer is max of their absolute values.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxAbsoluteSum(self, nums: list[int]) -> int:
        prefix = 0
        min_prefix = max_prefix = 0
        best = 0
        for x in nums:
            prefix += x
            min_prefix = min(min_prefix, prefix)
            max_prefix = max(max_prefix, prefix)
            best = max(best, prefix - min_prefix, max_prefix - prefix)
        return best
Explanation:
Subarray sum = prefix[j] − prefix[i]. Track min/max prefix to maximize absolute difference.

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

DP on Trees / Graphs#

Problem 1: Diameter of Binary Tree (Leetcode:543)#

Problem Statement

Given the root of a binary tree, return the length of the diameter — the longest path between any two nodes (path may or may not pass through root).

Example 1:

Input: root = [1,2,3,4,5]
Output: 3
Explanation: Path 4→2→1→3 or 5→2→1→3.

Example 2:

Input: root = [1,2]
Output: 1

Constraints:

  • 1 <= number of nodes <= 10⁴
  • −100 <= Node.val <= 100
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def diameterOfBinaryTree(self, root) -> int:
        self.best = 0

        def height(node) -> int:
            if not node:
                return 0
            left = height(node.left)
            right = height(node.right)
            self.best = max(self.best, left + right)
            return 1 + max(left, right)

        height(root)
        return self.best
Explanation:
At each node, diameter through it = left height + right height. Return height upward; track global max.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def diameterOfBinaryTree(self, root) -> int:
        def dfs(node) -> tuple[int, int]:
            if not node:
                return 0, 0
            lh, ld = dfs(node.left)
            rh, rd = dfs(node.right)
            height = 1 + max(lh, rh)
            diameter = max(ld, rd, lh + rh)
            return height, diameter

        return dfs(root)[1]
Explanation:
Return (subtree_height, best_diameter_in_subtree) from each DFS call.

Time: O(n)  |  Space: O(h)

Problem 2: Maximum Path Sum in Binary Tree (Leetcode:124)#

Problem Statement

Given a binary tree, return the maximum path sum of any non-empty path. A path is any sequence of nodes where adjacent nodes are connected; the path need not pass through the root.

Example 1:

Input: root = [1,2,3]
Output: 6
Explanation: Path 2→1→3.

Example 2:

Input: root = [-10,9,20,null,null,15,7]
Output: 42
Explanation: Path 15→20→7.

Constraints:

  • 1 <= number of nodes <= 3 × 10⁴
  • −1000 <= Node.val <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def maxPathSum(self, root) -> int:
        self.best = float("-inf")

        def gain(node) -> int:
            if not node:
                return 0
            left = max(gain(node.left), 0)
            right = max(gain(node.right), 0)
            self.best = max(self.best, node.val + left + right)
            return node.val + max(left, right)

        gain(root)
        return self.best
Explanation:
gain(node) = max sum of downward path starting at node (for parent). At node, update global with val + left + right; ignore negative child gains.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxPathSum(self, root) -> int:
        def dfs(node) -> tuple[int, int]:
            if not node:
                return 0, float("-inf")
            lg, lb = dfs(node.left)
            rg, rb = dfs(node.right)
            extend = node.val + max(lg, 0, rg, 0)
            through = node.val + max(lg, 0) + max(rg, 0)
            best = max(lb, rb, through)
            return extend, best

        return dfs(root)[1]
Explanation:
Tuple tracks best downward extension and best path entirely in subtree.

Time: O(n)  |  Space: O(h)

Problem 3: Most Frequent Subtree Sum (Leetcode:508)#

Problem Statement

Given the root of a binary tree, return all values with the most frequent subtree sum. Subtree sum includes a node and all descendants.

Example 1:

Input: root = [5,2,-3]
Output: [2,-3,4]

Example 2:

Input: root = [5,2,-5]
Output: [2]

Constraints:

  • 1 <= number of nodes <= 10⁴
  • −10⁵ <= Node.val <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findFrequentTreeSum(self, root) -> list[int]:
        from collections import Counter

        freq = Counter()

        def dfs(node) -> int:
            if not node:
                return 0
            total = node.val + dfs(node.left) + dfs(node.right)
            freq[total] += 1
            return total

        dfs(root)
        max_freq = max(freq.values())
        return [s for s, c in freq.items() if c == max_freq]
Explanation:
Postorder computes subtree sum bottom-up; count frequencies in hash map.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def findFrequentTreeSum(self, root) -> list[int]:
        sums: list[int] = []

        def subtree_sum(node) -> int:
            if not node:
                return 0
            s = node.val + subtree_sum(node.left) + subtree_sum(node.right)
            sums.append(s)
            return s

        subtree_sum(root)
        from collections import Counter

        freq = Counter(sums)
        best = max(freq.values())
        return [s for s, c in freq.items() if c == best]
Explanation:
Collect all subtree sums in list, then frequency count. Same complexity, clearer separation.

Time: O(n)  |  Space: O(n)

Problem 4: Maximum Independent Set in a Tree (GeeksforGeeks)#

Problem Statement

Given an undirected tree with n nodes, find the maximum independent set size — largest subset of nodes with no two adjacent.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]
Output: 4
Explanation: Pick nodes 3,4,5,6.

Example 2:

Input: n = 3, edges = [[0,1],[1,2]]
Output: 2

Constraints:

  • 1 <= n <= 10⁵
  • Tree is connected and acyclic.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def maxIndependentSet(self, n: int, edges: list[list[int]]) -> int:
        from collections import defaultdict

        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        def dfs(node: int, parent: int) -> tuple[int, int]:
            take, skip = 1, 0
            for nei in graph[node]:
                if nei == parent:
                    continue
                child_take, child_skip = dfs(nei, node)
                take += child_skip
                skip += max(child_take, child_skip)
            return take, skip

        return max(dfs(0, -1))
Explanation:
take = include node + best skip of children. skip = exclude node + max(take/skip) of each child. Root at 0.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def maxIndependentSet(self, n: int, edges: list[list[int]]) -> int:
        from collections import defaultdict
        from functools import cache

        graph = defaultdict(list)
        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        @cache
        def dp(node: int, parent: int, included: bool) -> int:
            if included:
                res = 1
                for nei in graph[node]:
                    if nei != parent:
                        res += dp(nei, node, False)
                return res
            best = 0
            for nei in graph[node]:
                if nei != parent:
                    best += max(dp(nei, node, True), dp(nei, node, False))
            return best

        return max(dp(0, -1, True), dp(0, -1, False))
Explanation:
State (node, parent, included) memoized. Same recurrence, explicit boolean flag.

Time: O(n)  |  Space: O(n)

Problem 5: Longest Path in DAG (GeeksforGeeks)#

Problem Statement

Given a weighted directed acyclic graph (DAG) with n nodes and edges [u, v, w], find the longest path (maximum sum of edge weights) in the graph.

Example 1:

Input: n = 6, edges = [[0,1,5],[0,2,3],[1,3,6],[1,2,2],[2,4,4],[2,5,2],[3,4,-1],[4,5,-2]]
Output: 12
Explanation: Path 0→1→3→4→5.

Example 2:

Input: n = 3, edges = [[0,1,1],[1,2,1]]
Output: 2

Constraints:

  • 1 <= n <= 10³
  • Graph is a DAG (no cycles).
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def longestPath(self, n: int, edges: list[list[int]]) -> int:
        from collections import defaultdict, deque

        graph = defaultdict(list)
        indeg = [0] * n
        for u, v, w in edges:
            graph[u].append((v, w))
            indeg[v] += 1
        q = deque(i for i in range(n) if indeg[i] == 0)
        dist = [float("-inf")] * n
        for i in range(n):
            if indeg[i] == 0:
                dist[i] = 0
        while q:
            u = q.popleft()
            for v, w in graph[u]:
                dist[v] = max(dist[v], dist[u] + w)
                indeg[v] -= 1
                if indeg[v] == 0:
                    q.append(v)
        return max(dist)
Explanation:
Process nodes in topological order; relax edges like longest-path DP. Sources start at 0.

Time: O(V + E)  |  Space: O(V + E)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def longestPath(self, n: int, edges: list[list[int]]) -> int:
        from collections import defaultdict
        from functools import cache

        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))

        @cache
        def dfs(u: int) -> int:
            best = 0
            for v, w in graph[u]:
                best = max(best, w + dfs(v))
            return best

        return max((dfs(i) for i in range(n)), default=0)
Explanation:
DAG allows memoized DFS without cycle handling. Try all start nodes; take global max.

Time: O(V + E)  |  Space: O(V + E)

2D DP / Grid‑based#

Problem 1: Unique Paths in Grid (Leetcode:62)#

Problem Statement

There is a robot on an m × n grid. The robot starts at the top-left corner (0, 0) and tries to reach the bottom-right corner (m − 1, n − 1). The robot can only move down or right at any point. Given m and n, return the number of unique paths.

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation: Right→Down→Down, Down→Right→Down, Down→Down→Right.

Constraints:

  • 1 <= m, n <= 100
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[1] * n for _ in range(m)]
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        return dp[m - 1][n - 1]
Explanation:
dp[i][j] = paths to cell (i,j). Only from top or left → sum of those two.

Time: O(m × n)  |  Space: O(m × n)

1
2
3
4
5
6
7
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * n
        for _ in range(1, m):
            for j in range(1, n):
                dp[j] += dp[j - 1]
        return dp[n - 1]
Explanation:
Single row; each cell accumulates paths from left and previous row value.

Time: O(m × n)  |  Space: O(n)

Problem 2: Minimum Path Sum in Grid (Leetcode:64 | GeeksforGeeks)#

Problem Statement

Given an m × n grid filled with non-negative numbers, find a path from top-left to bottom-right which minimizes the sum of all numbers along its path. You may only move down or right.

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Path 1→3→1→1→1 sums to 7.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 200
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        for i in range(m):
            for j in range(n):
                if i == 0 and j == 0:
                    continue
                top = grid[i - 1][j] if i > 0 else float("inf")
                left = grid[i][j - 1] if j > 0 else float("inf")
                grid[i][j] += min(top, left)
        return grid[m - 1][n - 1]
Explanation:
dp[i][j] = min cost to reach (i,j). Overwrite grid in place: add min of top/left neighbor.

Time: O(m × n)  |  Space: O(1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        from functools import cache
        m, n = len(grid), len(grid[0])

        @cache
        def dfs(i: int, j: int) -> int:
            if i == m - 1 and j == n - 1:
                return grid[i][j]
            if i == m - 1:
                return grid[i][j] + dfs(i, j + 1)
            if j == n - 1:
                return grid[i][j] + dfs(i + 1, j)
            return grid[i][j] + min(dfs(i + 1, j), dfs(i, j + 1))

        return dfs(0, 0)
Explanation:
Recursive min path with memo on (i,j); equivalent recurrence to bottom-up.

Time: O(m × n)  |  Space: O(m × n)

Problem 3: Triangle (Leetcode:120)#

Problem Statement

Given a triangle array triangle, return the minimum path sum from top to bottom. Each step you may move to an adjacent number on the row below. Adjacent for index j on row i means indices j or j+1 on row i+1.

Example 1:

Input: triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output: 11
Explanation: 2 + 3 + 5 + 1 = 11.

Example 2:

Input: triangle = [[-10]]
Output: -10

Constraints:

  • 1 <= triangle.length <= 200
  • triangle[0].length == 1
  • triangle[i].length == triangle[i - 1].length + 1
  • −10⁴ <= triangle[i][j] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        dp = triangle[-1][:]
        for row in range(len(triangle) - 2, -1, -1):
            for j in range(len(triangle[row])):
                dp[j] = triangle[row][j] + min(dp[j], dp[j + 1])
        return dp[0]
Explanation:
Start from bottom row; for each cell add min of two children below. Avoids boundary checks.

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minimumTotal(self, triangle: list[list[int]]) -> int:
        from functools import cache

        @cache
        def dfs(i: int, j: int) -> int:
            if i == len(triangle) - 1:
                return triangle[i][j]
            return triangle[i][j] + min(dfs(i + 1, j), dfs(i + 1, j + 1))

        return dfs(0, 0)
Explanation:
dfs(i,j) = min path sum from (i,j) to bottom.

Time: O(n²)  |  Space: O(n²)

Problem 4: Maximal Square (Leetcode:221)#

Problem Statement

Given an m × n binary matrix matrix filled with 0s and 1s, find the largest square containing only 1s and return its area.

Example 1:

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4

Example 2:

Input: matrix = [["0","1"],["1","0"]]
Output: 1

Constraints:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 300
  • matrix[i][j] is '0' or '1'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        best = 0
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == "1":
                    dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
                    best = max(best, dp[i][j])
        return best * best
Explanation:
dp[i][j] = side length of largest square ending at (i−1,j−1). On '1', limited by top, left, and diagonal neighbors.

Time: O(m × n)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maximalSquare(self, matrix: list[list[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        prev = [0] * (n + 1)
        best = 0
        for i in range(1, m + 1):
            curr = [0] * (n + 1)
            for j in range(1, n + 1):
                if matrix[i - 1][j - 1] == "1":
                    curr[j] = 1 + min(prev[j], curr[j - 1], prev[j - 1])
                    best = max(best, curr[j])
            prev = curr
        return best * best
Explanation:
Same recurrence with one previous row stored.

Time: O(m × n)  |  Space: O(n)

Problem 5: Minimum Falling Path Sum (Leetcode:931)#

Problem Statement

Given an n × n array of integers matrix, return the minimum sum of any falling path through the matrix. A falling path starts at any element in the first row and chooses one of the three elements below it (left, center, or right).

Example 1:

Input: matrix = [[2,1,3],[6,5,4],[7,8,9]]
Output: 13
Explanation: 1→5→7.

Example 2:

Input: matrix = [[-19,57],[-40,-5]]
Output: -59

Constraints:

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 200
  • −10⁴ <= matrix[i][j] <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        dp = matrix[0][:]
        n = len(matrix)
        for i in range(1, n):
            new = [0] * n
            for j in range(n):
                left = dp[j - 1] if j > 0 else float("inf")
                mid = dp[j]
                right = dp[j + 1] if j + 1 < n else float("inf")
                new[j] = matrix[i][j] + min(left, mid, right)
            dp = new
        return min(dp)
Explanation:
dp[j] = min falling sum ending at column j in current row. Extend from three parents above.

Time: O(n²)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def minFallingPathSum(self, matrix: list[list[int]]) -> int:
        n = len(matrix)
        for i in range(1, n):
            for j in range(n):
                left = matrix[i - 1][j - 1] if j > 0 else float("inf")
                mid = matrix[i - 1][j]
                right = matrix[i - 1][j + 1] if j + 1 < n else float("inf")
                matrix[i][j] += min(left, mid, right)
        return min(matrix[-1])
Explanation:
Overwrite each row with cumulative min path sums.

Time: O(n²)  |  Space: O(1)

Problem 6: Dungeon Game (Leetcode:174)#

Problem Statement

The demons' dungeon consists of an m × n grid. Each cell has an integer — positive (health gain) or negative (health loss). The knight starts at (0,0) with initial health; he must reach (m−1,n−1) alive. Health must stay strictly positive at all times (including start and end). Return the minimum initial health required.

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: Minimum initial health is 7.

Example 2:

Input: dungeon = [[0]]
Output: 1

Constraints:

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • −1000 <= dungeon[i][j] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [[float("inf")] * (n + 1) for _ in range(m + 1)]
        dp[m][n - 1] = dp[m - 1][n] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j]
                dp[i][j] = max(1, need)
        return dp[0][0]
Explanation:
dp[i][j] = min health needed entering (i,j) to survive to exit. Work backward from princess cell; clamp health to at least 1.

Time: O(m × n)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def calculateMinimumHP(self, dungeon: list[list[int]]) -> int:
        m, n = len(dungeon), len(dungeon[0])
        dp = [float("inf")] * (n + 1)
        dp[n - 1] = 1
        for i in range(m - 1, -1, -1):
            for j in range(n - 1, -1, -1):
                need = min(dp[j], dp[j + 1]) - dungeon[i][j]
                dp[j] = max(1, need)
        return dp[0]
Explanation:
Single row processed right-to-left per row; same reverse recurrence.

Time: O(m × n)  |  Space: O(n)

Problem 7: Cherry Pickup (Leetcode:741)#

Problem Statement

An n × n grid represents a field of cherries. Each cell is one of: 0 (empty), −1 (thorns/block), or a positive integer (cherries). Starting at (0,0), pick cherries and reach (n−1,n−1) moving only right or down. When you pass a cherry cell, cherries there become 0. Return the maximum cherries collectable. Return 0 if no path exists.

Example 1:

Input: grid = [[0,1,-1],[1,0,-1],[1,1,1]]
Output: 5

Example 2:

Input: grid = [[1,1,-1],[1,-1,1],[-1,1,1]]
Output: 0

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 50
  • grid[i][j] is −1, 0, or positive.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        if grid[0][0] == -1 or grid[n - 1][n - 1] == -1:
            return 0

        def max_path(g: list[list[int]]) -> list[list[int]]:
            dp = [[float("-inf")] * n for _ in range(n)]
            dp[0][0] = g[0][0]
            for i in range(n):
                for j in range(n):
                    if g[i][j] == -1:
                        dp[i][j] = float("-inf")
                        continue
                    if i > 0:
                        dp[i][j] = max(dp[i][j], dp[i - 1][j] + g[i][j])
                    if j > 0:
                        dp[i][j] = max(dp[i][j], dp[i][j - 1] + g[i][j])
            return dp

        fwd = max_path(grid)
        bwd = max_path([row[::-1] for row in grid[::-1]])
        ans = 0
        for i in range(n):
            for j in range(n):
                if fwd[i][j] > float("-inf") and bwd[n - 1 - i][n - 1 - j] > float("-inf"):
                    total = fwd[i][j] + bwd[n - 1 - i][n - 1 - j] - grid[i][j]
                    ans = max(ans, total)
        return max(0, ans)
Explanation:
Best forward path to each cell + best backward path from each cell (via reversed grid) − double-counted cell cherry.

Time: O(n²)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def cherryPickup(self, grid: list[list[int]]) -> int:
        n = len(grid)
        dp = [[float("-inf")] * n for _ in range(n)]
        dp[0][0] = grid[0][0]
        for steps in range(1, 2 * n - 1):
            ndp = [[float("-inf")] * n for _ in range(n)]
            for r1 in range(n):
                for r2 in range(n):
                    c1, c2 = steps - r1, steps - r2
                    if min(r1, r2, c1, c2) < 0 or max(r1, r2, c1, c2) >= n:
                        continue
                    if grid[r1][c1] == -1 or grid[r2][c2] == -1:
                        continue
                    gain = grid[r1][c1]
                    if r1 != r2:
                        gain += grid[r2][c2]
                    for pr1 in (r1 - 1, r1):
                        for pr2 in (r2 - 1, r2):
                            if pr1 >= 0 and pr2 >= 0:
                                ndp[r1][r2] = max(ndp[r1][r2], dp[pr1][pr2] + gain)
            dp = ndp
        return max(0, dp[n - 1][n - 1])
Explanation:
Two walkers go start→end simultaneously; state (r1,r2) at fixed step count avoids revisiting cherries. Standard optimal solution for follow-up constraints.

Time: O(n³)  |  Space: O(n²)

String‑based DP (Matching / Patterns)#

Problem 1: Wildcard Matching (Leetcode:44)#

Problem Statement

Given an input string s and a pattern p, implement wildcard pattern matching with support for '?' and '*':

  • '?' Matches any single character.
  • '*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial). Return true if s matches p, else false.

Example 1:

Input: s = "aa", p = "a"
Output: false

Example 2:

Input: s = "aa", p = "*"
Output: true

Example 3:

Input: s = "cb", p = "?a"
Output: false

Constraints:

  • 0 <= s.length, p.length <= 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '?', or '*'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(1, n + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 1]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    dp[i][j] = dp[i][j - 1] or dp[i - 1][j]
                elif p[j - 1] == "?" or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]
Explanation:
dp[i][j] = does s[:i] match p[:j]? * matches empty (dp[i][j-1]) or consumes a char (dp[i-1][j]).

Time: O(m × n)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        i = j = 0
        star_i = star_j = -1
        while i < len(s):
            if j < len(p) and (p[j] == "?" or p[j] == s[i]):
                i += 1
                j += 1
            elif j < len(p) and p[j] == "*":
                star_i, star_j = i, j
                j += 1
            elif star_j != -1:
                star_j += 1
                j = star_j
                star_i += 1
                i = star_i
            else:
                return False
        while j < len(p) and p[j] == "*":
            j += 1
        return j == len(p)
Explanation:
On mismatch, backtrack to last * and try matching one more char from s. Linear scan when few stars.

Time: O(m × n) worst case  |  Space: O(1)

Problem 2: Regular Expression Matching (Leetcode:10)#

Problem Statement

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*':

  • '.' Matches any single character.
  • '*' Matches zero or more of the preceding element.

The matching should cover the entire input string. Return true if s matches p.

Example 1:

Input: s = "aa", p = "a"
Output: false

Example 2:

Input: s = "aa", p = "a*"
Output: true

Example 3:

Input: s = "ab", p = ".*"
Output: true

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 20
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed that for each occurrence of '*', there is a valid preceding character.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m, n = len(s), len(p)
        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0][0] = True
        for j in range(2, n + 1):
            if p[j - 1] == "*":
                dp[0][j] = dp[0][j - 2]

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if p[j - 1] == "*":
                    dp[i][j] = dp[i][j - 2]
                    if p[j - 2] == "." or p[j - 2] == s[i - 1]:
                        dp[i][j] = dp[i][j] or dp[i - 1][j]
                elif p[j - 1] == "." or p[j - 1] == s[i - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
        return dp[m][n]
Explanation:
* at p[j-1]: skip pair (dp[i][j-2]) or use preceding char if it matches current s[i-1] (dp[i-1][j]).

Time: O(m × n)  |  Space: O(m × n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        from functools import cache

        @cache
        def dfs(i: int, j: int) -> bool:
            if j == len(p):
                return i == len(s)
            first_match = i < len(s) and (p[j] == s[i] or p[j] == ".")
            if j + 1 < len(p) and p[j + 1] == "*":
                return dfs(i, j + 2) or (first_match and dfs(i + 1, j))
            return first_match and dfs(i + 1, j + 1)

        return dfs(0, 0)
Explanation:
Mirror tabulation logic recursively; memo on (i,j) indices.

Time: O(m × n)  |  Space: O(m × n)

DP with Bitmask#

Problem 1: Partition to K Equal Sum Subsets (Leetcode:698)#

Problem Statement

Given an integer array nums and an integer k, return true if it is possible to divide nums into k non-empty subsets whose sums are all equal.

Example 1:

Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: [5], [1,4], [2,3], [2,3].

Example 2:

Input: nums = [1,2,3,4], k = 3
Output: false

Constraints:

  • 1 <= k <= nums.length <= 16
  • 1 <= nums[i] <= 10⁴
  • The frequency of each element is in the range [1, 4].
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
        total = sum(nums)
        if total % k:
            return False
        target = total // k
        nums.sort(reverse=True)
        used = [False] * len(nums)

        def dfs(k_left: int, curr: int, start: int) -> bool:
            if k_left == 1:
                return True
            if curr == target:
                return dfs(k_left - 1, 0, 0)
            for i in range(start, len(nums)):
                if used[i] or curr + nums[i] > target:
                    continue
                used[i] = True
                if dfs(k_left, curr + nums[i], i + 1):
                    return True
                used[i] = False
                if curr == 0:
                    break
            return False

        return dfs(k, 0, 0)
Explanation:
Build subsets of sum target; sort descending and skip empty restarts to prune. Bitmask equivalent tracks used array.

Time: O(k × 2^n) worst case  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def canPartitionKSubsets(self, nums: list[int], k: int) -> bool:
        total = sum(nums)
        if total % k:
            return False
        target = total // k
        n = len(nums)
        dp = [False] * (1 << n)
        dp[0] = True
        sums = [0] * (1 << n)
        for mask in range(1 << n):
            if not dp[mask]:
                continue
            for i in range(n):
                if mask & (1 << i):
                    continue
                nmask = mask | (1 << i)
                sums[nmask] = sums[mask] + nums[i]
                if sums[nmask] == target:
                    sums[nmask] = 0
                if sums[nmask] <= target:
                    dp[nmask] = True
        return dp[(1 << n) - 1]
Explanation:
mask = used elements; sums[mask] = current partial subset sum mod target. Transition adds one unused index.

Time: O(n × 2^n)  |  Space: O(2^n)

Problem 2: Traveling Salesman Problem (GeeksforGeeks)#

Problem Statement

Given a complete weighted graph with n cities (vertices), find the minimum cost to visit every city exactly once and return to the starting city. The graph is given as a distance matrix dist[i][j].

Example 1:

Input: dist = [[0,10,15,20],[10,0,35,25],[15,35,0,30],[20,25,30,0]]
Output: 80
Explanation: 0→1→3→2→0 costs 10+25+30+15 = 80.

Constraints:

  • 2 <= n <= 20
  • 0 <= dist[i][j] <= 10³
  • dist[i][i] == 0
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def tsp(self, dist: list[list[int]]) -> int:
        n = len(dist)
        ALL = (1 << n) - 1
        dp = [[float("inf")] * n for _ in range(1 << n)]
        dp[1][0] = 0

        for mask in range(1 << n):
            for u in range(n):
                if not (mask & (1 << u)) or dp[mask][u] == float("inf"):
                    continue
                for v in range(n):
                    if mask & (1 << v):
                        continue
                    nmask = mask | (1 << v)
                    dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + dist[u][v])

        ans = float("inf")
        for u in range(1, n):
            ans = min(ans, dp[ALL][u] + dist[u][0])
        return ans
Explanation:
dp[mask][u] = min cost to visit set mask, ending at u. Start {0} at city 0; add cities one by one; close tour back to 0.

Time: O(n² × 2^n)  |  Space: O(n × 2^n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def tsp(self, dist: list[list[int]]) -> int:
        from functools import cache
        n = len(dist)

        @cache
        def dfs(mask: int, last: int) -> int:
            if mask == (1 << n) - 1:
                return dist[last][0]
            best = float("inf")
            for nxt in range(n):
                if not (mask & (1 << nxt)):
                    best = min(best, dist[last][nxt] + dfs(mask | (1 << nxt), nxt))
            return best

        return dfs(1, 0)
Explanation:
Same state space; recursive form often easier to write in interviews.

Time: O(n² × 2^n)  |  Space: O(n × 2^n)

Problem 3: Shortest Path Visiting All Nodes (Leetcode:847)#

Problem Statement

You are given an undirected graph with n nodes labeled 0..n−1. Return the length of the shortest path that visits every node. You may start and stop at any node and revisit nodes/edges.

Example 1:

Input: graph = [[1,2,3],[0],[0],[0]]
Output: 4
Explanation: Path 0→1→0→2→0→3 visits all nodes.

Example 2:

Input: graph = [[1],[0,2,4],[1],[4],[1,3]]
Output: 4

Constraints:

  • n == graph.length
  • 1 <= n <= 12
  • 0 <= graph[i].length < n
  • graph[i] does not contain i.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        from collections import deque
        n = len(graph)
        ALL = (1 << n) - 1
        q = deque()
        seen = set()
        for i in range(n):
            mask = 1 << i
            q.append((i, mask, 0))
            seen.add((i, mask))
        while q:
            node, mask, dist = q.popleft()
            if mask == ALL:
                return dist
            for nei in graph[node]:
                nmask = mask | (1 << nei)
                if (nei, nmask) not in seen:
                    seen.add((nei, nmask))
                    q.append((nei, nmask, dist + 1))
        return 0
Explanation:
State = current node + bitmask of visited nodes. Multi-source BFS from every start node; first time mask is full wins.

Time: O(n × 2^n + E × 2^n)  |  Space: O(n × 2^n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def shortestPathLength(self, graph: list[list[int]]) -> int:
        n = len(graph)
        dist = [[10**9] * n for _ in range(n)]
        for i in range(n):
            dist[i][i] = 0
            for j in graph[i]:
                dist[i][j] = dist[j][i] = 1
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        dp = [[10**9] * n for _ in range(1 << n)]
        for i in range(n):
            dp[1 << i][i] = 0
        for mask in range(1 << n):
            for u in range(n):
                if dp[mask][u] == 10**9:
                    continue
                for v in range(n):
                    if mask & (1 << v):
                        continue
                    nmask = mask | (1 << v)
                    dp[nmask][v] = min(dp[nmask][v], dp[mask][u] + dist[u][v])
        return min(dp[(1 << n) - 1])
Explanation:
Precompute all-pairs shortest paths, then Held–Karp over visited sets (Hamiltonian path variant, any start/end).

Time: O(n³ + n² × 2^n)  |  Space: O(n × 2^n)

Problem 4: Maximum Students Taking Exam (Leetcode:1349)#

Problem Statement

A classroom is represented as an m × n matrix seats where '.' is an empty seat and '#' is a broken seat. Students refuse to sit if another student is directly in front, behind, left, or right. Return the maximum number of students that can take the exam.

Example 1:

Input: seats = [["#",".","#","#",".","#"],[".","#","#","#","#","."],["#",".","#","#",".","#"]]
Output: 4

Example 2:

Input: seats = [[".","#"],["#","#"],["#","."],["#","#"],[".","#"]]
Output: 10

Constraints:

  • m == seats.length
  • n == seats[i].length
  • 1 <= m <= 8
  • 1 <= n <= 8
  • seats[i][j] is '#' or '.'.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution:
    def maxStudents(self, seats: list[list[str]]) -> int:
        m, n = len(seats), len(seats[0])
        valid = []
        for mask in range(1 << n):
            ok = True
            for j in range(n):
                if (mask >> j) & 1:
                    if seats[0][j] == "#":
                        ok = False
                        break
                    if j > 0 and ((mask >> (j - 1)) & 1):
                        ok = False
                        break
                    if j + 1 < n and ((mask >> (j + 1)) & 1):
                        ok = False
                        break
            if ok:
                valid.append(mask)

        def compatible(prev: int, cur: int) -> bool:
            for j in range(n):
                if (cur >> j) & 1:
                    if (prev >> j) & 1:
                        return False
                    if j and (prev >> (j - 1)) & 1:
                        return False
                    if j + 1 < n and (prev >> (j + 1)) & 1:
                        return False
            return True

        dp = {mask: bin(mask).count("1") for mask in valid}
        for i in range(1, m):
            row_valid = []
            for mask in range(1 << n):
                ok = True
                for j in range(n):
                    if (mask >> j) & 1:
                        if seats[i][j] == "#":
                            ok = False
                            break
                        if j > 0 and ((mask >> (j - 1)) & 1):
                            ok = False
                            break
                        if j + 1 < n and ((mask >> (j + 1)) & 1):
                            ok = False
                            break
                if ok:
                    row_valid.append(mask)
            ndp = {}
            for cur in row_valid:
                best = 0
                for prev in dp:
                    if compatible(prev, cur):
                        best = max(best, dp[prev])
                ndp[cur] = best + bin(cur).count("1")
            dp = ndp
        return max(dp.values(), default=0)
Explanation:
Each row placement is a bitmask (which seats filled). DP over rows; transition if no vertical/horizontal conflict with previous row.

Time: O(m × 3^n × 2^n) practical  |  Space: O(2^n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution:
    def maxStudents(self, seats: list[list[str]]) -> int:
        m, n = len(seats), len(seats[0])

        def row_masks(r: int) -> list[int]:
            out = []
            for mask in range(1 << n):
                if any((mask >> j) & 1 and seats[r][j] == "#" for j in range(n)):
                    continue
                if any((mask >> j) & 1 and (mask >> (j - 1)) & 1 for j in range(1, n)):
                    continue
                if any((mask >> j) & 1 and (mask >> (j + 1)) & 1 for j in range(n - 1)):
                    continue
                out.append(mask)
            return out

        def ok(prev: int, cur: int) -> bool:
            for j in range(n):
                if (cur >> j) & 1:
                    if (prev >> j) & 1:
                        return False
                    if j and (prev >> (j - 1)) & 1:
                        return False
                    if j + 1 < n and (prev >> (j + 1)) & 1:
                        return False
            return True

        dp = {mask: mask.bit_count() for mask in row_masks(0)}
        for r in range(1, m):
            ndp = {}
            for cur in row_masks(r):
                ndp[cur] = max(
                    (dp[p] + cur.bit_count() for p in dp if ok(p, cur)),
                    default=0,
                )
            dp = ndp
        return max(dp.values(), default=0)
Explanation:
Same idea with helper functions; bit_count() gives students placed in row.

Time: O(m × V²) where V = valid masks per row  |  Space: O(V)

Problem 5: Find the Shortest Superstring (Leetcode:943)#

Problem Statement

Given an array of strings words, return the shortest string that contains each word as a substring. If multiple answers exist, return any of them.

Example 1:

Input: words = ["alex","loves","leetcode"]
Output: "alexlovesleetcode"

Example 2:

Input: words = ["catg","ctaagt","gca","catc","gc","gcatg","gctaagt","catgc","gca","gcatgc","gctaagt","gctaagt"]
Output: "gctaagtcatgc"

Constraints:

  • 1 <= words.length <= 12
  • 1 <= words[i].length <= 20
  • words[i] consists of lowercase English letters.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution:
    def shortestSuperstring(self, words: list[str]) -> str:
        n = len(words)
        overlap = [[0] * n for _ in range(n)]
        for i in range(n):
            for j in range(n):
                if i == j:
                    continue
                m = min(len(words[i]), len(words[j]))
                for k in range(m, 0, -1):
                    if words[i].endswith(words[j][:k]):
                        overlap[i][j] = k
                        break

        dp = [[0] * n for _ in range(1 << n)]
        parent = [[(-1, -1)] * n for _ in range(1 << n)]
        for mask in range(1 << n):
            for last in range(n):
                if not (mask & (1 << last)):
                    continue
                prev_mask = mask ^ (1 << last)
                if prev_mask == 0:
                    continue
                for prev in range(n):
                    if not (prev_mask & (1 << prev)):
                        continue
                    val = dp[prev_mask][prev] + overlap[prev][last]
                    if val > dp[mask][last]:
                        dp[mask][last] = val
                        parent[mask][last] = (prev_mask, prev)

        best_mask, best_last = (1 << n) - 1, 0
        best = -1
        for last in range(n):
            if dp[best_mask][last] > best:
                best = dp[best_mask][last]
                best_last = last

        order = []
        mask, last = best_mask, best_last
        while last != -1:
            order.append(last)
            mask, last = parent[mask][last]

        order.reverse()
        if not order:
            order = [0]

        result = words[order[0]]
        for i in range(1, len(order)):
            a, b = order[i - 1], order[i]
            result += words[b][overlap[a][b]:]
        return result
Explanation:
Precompute max overlap when concatenating words[i] then words[j]. TSP-style bitmask DP maximizes total overlap; reconstruct order and build string.

Time: O(n² × 2^n + n² × L)  |  Space: O(n × 2^n)

Problem 6: Minimum Number of Work Sessions to Finish Tasks (Leetcode:1986)#

Problem Statement

You are given tasks[i] = minutes to complete task i and a session time sessionTime. During one session you may work on any subset of tasks, but the total time cannot exceed sessionTime. Return the minimum number of sessions needed to finish all tasks.

Example 1:

Input: tasks = [1,2,3], sessionTime = 3
Output: 2

Example 2:

Input: tasks = [3,1,3,1,3], sessionTime = 8
Output: 2

Constraints:

  • n == tasks.length
  • 1 <= n <= 14
  • 1 <= tasks[i] <= 10
  • 1 <= sessionTime <= 15
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def minSessions(self, tasks: list[int], sessionTime: int) -> int:
        n = len(tasks)
        valid = [False] * (1 << n)
        for mask in range(1 << n):
            if sum(tasks[i] for i in range(n) if mask & (1 << i)) <= sessionTime:
                valid[mask] = True

        dp = [float("inf")] * (1 << n)
        dp[0] = 0
        for mask in range(1 << n):
            if dp[mask] == float("inf"):
                continue
            sub = ((1 << n) - 1) ^ mask
            s = sub
            while s:
                if valid[s]:
                    dp[mask | s] = min(dp[mask | s], dp[mask] + 1)
                s = (s - 1) & sub
        return dp[(1 << n) - 1]
Explanation:
Precompute masks fitting one session. From mask of finished tasks, add any valid subset s of remaining in one session.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def minSessions(self, tasks: list[int], sessionTime: int) -> int:
        from functools import cache
        n = len(tasks)

        @cache
        def dfs(mask: int) -> int:
            if mask == 0:
                return 0
            best = float("inf")
            sub = mask
            while sub:
                if sum(tasks[i] for i in range(n) if sub & (1 << i)) <= sessionTime:
                    best = min(best, 1 + dfs(mask ^ sub))
                sub = (sub - 1) & mask
            return best

        return dfs((1 << n) - 1)
Explanation:
Pick one valid session subset, recurse on rest; memo on remaining bitmask.

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

Problem 7: Number of Ways to Wear Different Hats to Each Other (Leetcode:1434)#

Problem Statement

There are n people and 40 types of hats numbered 1..40. hats[i] lists hat numbers person i can wear. Return the number of ways to assign each person a different hat, modulo 10⁹ + 7. Each person gets exactly one hat.

Example 1:

Input: hats = [[3,4],[4,5],[5]]
Output: 1

Example 2:

Input: hats = [[3,5,1],[3,5]]
Output: 4

Constraints:

  • n == hats.length
  • 1 <= n <= 10
  • 1 <= hats[i].length <= 40
  • 1 <= hats[i][j] <= 40
  • All hat numbers are distinct per person.
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numberWays(self, hats: list[list[int]]) -> int:
        MOD = 10**9 + 7
        n = len(hats)
        hat_to_people = [[] for _ in range(41)]
        for i, lst in enumerate(hats):
            for h in lst:
                hat_to_people[h].append(i)

        dp = [0] * (1 << n)
        dp[0] = 1
        for h in range(1, 41):
            ndp = dp[:]
            for mask in range(1 << n):
                if dp[mask] == 0:
                    continue
                for person in hat_to_people[h]:
                    if mask & (1 << person):
                        continue
                    nmask = mask | (1 << person)
                    ndp[nmask] = (ndp[nmask] + dp[mask]) % MOD
            dp = ndp
        return dp[(1 << n) - 1]
Explanation:
Process hats 1..40; mask = people already assigned. For each hat, assign it to any eligible unassigned person.

Time: O(40 × n × 2^n)  |  Space: O(2^n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def numberWays(self, hats: list[list[int]]) -> int:
        from functools import cache
        MOD = 10**9 + 7
        n = len(hats)
        hat_to_people = [[] for _ in range(41)]
        for i, lst in enumerate(hats):
            for h in lst:
                hat_to_people[h].append(i)

        @cache
        def dfs(h: int, mask: int) -> int:
            if mask == (1 << n) - 1:
                return 1
            if h == 41:
                return 0
            ans = dfs(h + 1, mask)
            for person in hat_to_people[h]:
                if not (mask & (1 << person)):
                    ans = (ans + dfs(h + 1, mask | (1 << person))) % MOD
            return ans

        return dfs(1, 0)
Explanation:
Skip hat or assign to one person; same state space as bottom-up.

Time: O(40 × n × 2^n)  |  Space: O(40 × 2^n)

Problem 8: Fair Distribution of Cookies (Leetcode:2305)#

Problem Statement

You are given an integer array cookies where cookies[i] is the number of cookies in bag i, and an integer k. Distribute all bags to k children so each child gets at least one bag. The unfairness is the maximum total cookies any single child receives. Return the minimum unfairness possible.

Example 1:

Input: cookies = [8,15,10,20,8], k = 2
Output: 31
Explanation: [8,15,8] and [10,20].

Example 2:

Input: cookies = [6,1,3,2,2,4,1,2], k = 3
Output: 7

Constraints:

  • 2 <= k <= cookies.length <= 8
  • 1 <= cookies[i] <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def distributeCookies(self, cookies: list[int], k: int) -> int:
        buckets = [0] * k
        cookies.sort(reverse=True)
        best = float("inf")

        def dfs(i: int) -> None:
            nonlocal best
            if i == len(cookies):
                best = min(best, max(buckets))
                return
            if max(buckets) >= best:
                return
            seen = set()
            for b in range(k):
                if buckets[b] in seen:
                    continue
                seen.add(buckets[b])
                buckets[b] += cookies[i]
                dfs(i + 1)
                buckets[b] -= cookies[i]

        dfs(0)
        return best
Explanation:
Assign each bag to a child; prune when current max already ≥ best. Sort descending for tighter bounds. Small n ≤ 8 makes this feasible.

Time: O(k^n) with pruning  |  Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def distributeCookies(self, cookies: list[int], k: int) -> int:
        n = len(cookies)
        sums = [0] * (1 << n)
        for mask in range(1 << n):
            for i in range(n):
                if mask & (1 << i):
                    sums[mask] += cookies[i]

        @cache
        def dfs(mask: int, children_left: int, limit: int) -> bool:
            if children_left == 0:
                return mask == (1 << n) - 1
            sub = ((1 << n) - 1) ^ mask
            s = sub
            while s:
                if sums[s] <= limit:
                    if dfs(mask | s, children_left - 1, limit):
                        return True
                s = (s - 1) & sub
            return False

        lo, hi = max(cookies), sum(cookies)
        while lo < hi:
            mid = (lo + hi) // 2
            dfs.cache_clear()
            if dfs(0, k, mid):
                hi = mid
            else:
                lo = mid + 1
        return lo
Explanation:
Binary search answer (max load); bitmask checks if remaining bags partition into children_left groups each ≤ limit.

Time: O(log(sum) × 3^n)  |  Space: O(2^n)

Digit DP#

Problem 1: Number of Digit One (Leetcode:233)#

Problem Statement

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example 1:

Input: n = 13
Output: 6
Explanation: Digit 1 appears in 1, 10, 11 (twice), 12, 13.

Example 2:

Input: n = 0
Output: 0

Constraints:

  • 0 <= n <= 10⁹
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def countDigitOne(self, n: int) -> int:
        s = str(n)
        from functools import cache

        @cache
        def dfs(pos: int, count: int, tight: bool) -> int:
            if pos == len(s):
                return count
            limit = int(s[pos]) if tight else 9
            ans = 0
            for d in range(limit + 1):
                ans += dfs(
                    pos + 1,
                    count + (d == 1),
                    tight and d == limit,
                )
            return ans

        return dfs(0, 0, True)
Explanation:
State (pos, count, tight) builds numbers left-to-right. At each position, try digits 0..limit; add to count when digit is 1. tight ensures we never exceed n.

Time: O(log n × 10 × log n)  |  Space: O(log n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def countDigitOne(self, n: int) -> int:
        ans = 0
        factor = 1
        while factor <= n:
            lower = n - n % factor
            higher = n // (factor * 10)
            cur = (n // factor) % 10
            if cur == 0:
                ans += higher * factor
            elif cur == 1:
                ans += higher * factor + (n % factor) + 1
            else:
                ans += (higher + 1) * factor
            factor *= 10
        return ans
Explanation:
For each decimal place, count how many times 1 appears there across all numbers ≤ n using high/cur/low digit decomposition.

Time: O(log n)  |  Space: O(1)

Problem 2: Non-negative Integers without Consecutive Ones (Leetcode:600)#

Problem Statement

Given a positive integer n, return the number of non-negative integers ≤ n whose binary representation contains no two consecutive 1s.

Example 1:

Input: n = 5
Output: 5
Explanation: 0, 1, 2, 4, 5 are valid; 3 (11₂) is not.

Example 2:

Input: n = 1
Output: 2

Constraints:

  • 1 <= n <= 10⁹
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def findIntegers(self, n: int) -> int:
        bits = bin(n)[2:]
        from functools import cache

        @cache
        def dfs(pos: int, prev_one: bool, tight: bool) -> int:
            if pos == len(bits):
                return 1
            limit = int(bits[pos]) if tight else 1
            ans = 0
            for d in range(limit + 1):
                if prev_one and d == 1:
                    continue
                ans += dfs(pos + 1, d == 1, tight and d == limit)
            return ans

        return dfs(0, False, True)
Explanation:
Build binary strings left-to-right. prev_one blocks placing another 1 after a 1. Count all valid numbers ≤ n (including 0).

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def findIntegers(self, n: int) -> int:
        # dp[i] = count of i-bit binary strings with no consecutive 1s
        dp = [0, 2, 3]
        for i in range(3, 32):
            dp.append(dp[-1] + dp[-2])

        bits = bin(n)[2:]
        prev, ans = 0, 0
        for i, b in enumerate(bits):
            if b == "1":
                ans += dp[len(bits) - i - 1]
                if prev:
                    return ans
            prev = b == "1"
        return ans + 1
Explanation:
Valid i-bit strings follow Fibonacci. Walk n's bits; when a 1 is fixed, add counts of all smaller valid prefixes; abort if two consecutive 1s appear.

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

Problem 3: Numbers At Most N Given Digit Set (Leetcode:902)#

Problem Statement

Given an array of digits digits (no duplicates) and an integer n, return the count of positive integers ≤ n whose decimal representation uses only digits from digits.

Example 1:

Input: digits = ["1","3","5","7"], n = 100
Output: 20
Explanation: 1, 3, 5, 7, 11, 13, … up to 77.

Example 2:

Input: digits = ["1","4","9"], n = 1000000000
Output: 29523

Constraints:

  • 1 <= digits.length <= 9
  • digits[i] is a digit in '1'–'9'
  • All digits are distinct
  • 1 <= n <= 10⁹
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def atMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
        allowed = {int(d) for d in digits}
        s = str(n)
        from functools import cache

        @cache
        def dfs(pos: int, tight: bool, started: bool) -> int:
            if pos == len(s):
                return 1 if started else 0
            limit = int(s[pos]) if tight else 9
            ans = 0
            for d in range(limit + 1):
                if d not in allowed:
                    continue
                if not started and d == 0:
                    continue
                ans += dfs(
                    pos + 1,
                    tight and d == limit,
                    started or d != 0,
                )
            return ans

        return dfs(0, True, False)
Explanation:
started skips leading zeros (we need positive integers). Only digits in allowed may be placed. tight caps the current digit by n's prefix.

Time: O(log n × |digits|)  |  Space: O(log n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def atMostNGivenDigitSet(self, digits: list[str], n: int) -> int:
        k = len(digits)
        s = str(n)
        m = len(s)

        # All numbers with fewer digits than n
        ans = sum(k**i for i in range(1, m))

        # Numbers with exactly m digits and <= n
        from functools import cache

        @cache
        def dfs(pos: int, tight: bool) -> int:
            if pos == m:
                return 1
            limit = int(s[pos]) if tight else 9
            total = 0
            for d in digits:
                di = int(d)
                if di > limit:
                    break
                total += dfs(pos + 1, tight and di == limit)
            return total

        return ans + dfs(0, True)
Explanation:
Count all valid numbers with < m digits via k + k² + … + k^(m-1), then digit-DP the m-digit block bounded by n.

Time: O(log n × |digits|)  |  Space: O(log n)

Problem 4: Numbers With Repeated Digits (Leetcode:1012)#

Problem Statement

Given a positive integer n, return the number of positive integers ≤ n that have at least one repeated digit.

Example 1:

Input: n = 20
Output: 1
Explanation: Only 11 has a repeated digit.

Example 2:

Input: n = 100
Output: 10
Explanation: 11, 22, …, 99, 100.

Constraints:

  • 1 <= n <= 10⁹
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        return n - self._count_unique(n)

    def _count_unique(self, n: int) -> int:
        s = str(n)
        from functools import cache

        @cache
        def dfs(pos: int, mask: int, tight: bool, started: bool) -> int:
            if pos == len(s):
                return 1 if started else 0
            limit = int(s[pos]) if tight else 9
            ans = 0
            for d in range(limit + 1):
                if not started and d == 0:
                    ans += dfs(pos + 1, mask, tight and d == limit, False)
                    continue
                if mask & (1 << d):
                    continue
                ans += dfs(
                    pos + 1,
                    mask | (1 << d),
                    tight and d == limit,
                    True,
                )
            return ans

        return dfs(0, 0, True, False)
Explanation:
Answer = n − (count of numbers ≤ n with all distinct digits). mask tracks used digits; skip any digit already in mask.

Time: O(log n × 10 × 2¹⁰)  |  Space: O(log n × 2¹⁰)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def numDupDigitsAtMostN(self, n: int) -> int:
        return n - self._count_unique(n)

    def _count_unique(self, n: int) -> int:
        s = str(n)
        m = len(s)
        # All unique-digit numbers with fewer than m digits
        unique = 0
        for length in range(1, m):
            unique += 9 * self._perm(9, length - 1)

        # Unique numbers with exactly m digits and <= n
        from functools import cache

        @cache
        def dfs(pos: int, mask: int, tight: bool) -> int:
            if pos == m:
                return 1
            start = 1 if pos == 0 else 0
            limit = int(s[pos]) if tight else 9
            total = 0
            for d in range(start, limit + 1):
                if mask >> d & 1:
                    continue
                total += dfs(pos + 1, mask | (1 << d), tight and d == limit)
            return total

        return unique + dfs(0, 0, True)

    def _perm(self, n: int, k: int) -> int:
        ans = 1
        for i in range(k):
            ans *= n - i
        return ans
Explanation:
Numbers with all distinct digits: for length L < m, first digit 1–9 and remaining L−1 from 9 unused digits (permutation). For length m, digit-DP the prefix bounded by n.

Time: O(log n × 10 × 2¹⁰)  |  Space: O(log n × 2¹⁰)

Probability DP#

Problem 1: Knight Probability in Chessboard (Leetcode:688)#

Problem Statement

On an n × n chessboard, a knight starts at (row, column) and makes exactly k moves. Each move is uniformly chosen among up to 8 L-shaped jumps. Return the probability the knight remains on the board after k moves.

Example 1:

Input: n = 3, k = 2, row = 0, column = 0
Output: 0.0625
Explanation: 2 of 32 equally likely paths stay on the board.

Example 2:

Input: n = 1, k = 0, row = 0, column = 0
Output: 1.0

Constraints:

  • 1 <= n <= 25
  • 0 <= k <= 100
  • 0 <= row, column <= n - 1
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def knightProbability(
        self, n: int, k: int, row: int, column: int
    ) -> float:
        dirs = (
            (2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2),
        )
        dp = [[0.0] * n for _ in range(n)]
        dp[row][column] = 1.0
        for _ in range(k):
            ndp = [[0.0] * n for _ in range(n)]
            for r in range(n):
                for c in range(n):
                    if dp[r][c] == 0:
                        continue
                    for dr, dc in dirs:
                        nr, nc = r + dr, c + dc
                        if 0 <= nr < n and 0 <= nc < n:
                            ndp[nr][nc] += dp[r][c] / 8.0
            dp = ndp
        return sum(map(sum, dp))
Explanation:
dp[r][c] = probability knight is at (r,c) after current number of moves. Each move spreads 1/8 of probability to reachable neighbors.

Time: O(k × n²)  |  Space: O(n²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def knightProbability(
        self, n: int, k: int, row: int, column: int
    ) -> float:
        dirs = (
            (2, 1), (2, -1), (-2, 1), (-2, -1),
            (1, 2), (1, -2), (-1, 2), (-1, -2),
        )
        from functools import cache

        @cache
        def dfs(r: int, c: int, moves: int) -> float:
            if moves == 0:
                return 1.0
            prob = 0.0
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < n and 0 <= nc < n:
                    prob += dfs(nr, nc, moves - 1) / 8.0
            return prob

        return dfs(row, column, k)
Explanation:
dfs(r,c,m) = probability of staying on board from (r,c) with m moves left. Same recurrence, computed lazily.

Time: O(k × n²)  |  Space: O(k × n²)

Problem 2: Soup Servings (Leetcode:808)#

Problem Statement

Two soups A and B start with n ml each. Each turn, one of four serve operations is chosen uniformly at random (each with probability 1/4). The first soup to empty (including simultaneous empty) determines the outcome. Return the probability that A empties before B, plus half the probability they empty together.

Example 1:

Input: n = 50
Output: 0.625

Example 2:

Input: n = 100
Output: 0.71875

Constraints:

  • 0 <= n <= 10⁹
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def soupServings(self, n: int) -> float:
        m = (n + 24) // 25
        from functools import cache

        @cache
        def dfs(a: int, b: int) -> float:
            if a <= 0 and b <= 0:
                return 0.5
            if a <= 0:
                return 1.0
            if b <= 0:
                return 0.0
            return 0.25 * (
                dfs(a - 4, b)
                + dfs(a - 3, b - 1)
                + dfs(a - 2, b - 2)
                + dfs(a - 1, b - 3)
            )

        if m > 4800:
            return 1.0
        return dfs(m, m)
Explanation:
Scale n by 25 ml per unit. dfs(a,b) = probability A wins from remaining (a,b). Base cases handle A-first, B-first, and tie. For large n, answer → 1 (empirical cutoff).

Time: O(m²)  |  Space: O(m²)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def soupServings(self, n: int) -> float:
        m = (n + 24) // 25
        if m > 4800:
            return 1.0
        dp = [[0.0] * (m + 1) for _ in range(m + 1)]
        for a in range(m + 1):
            for b in range(m + 1):
                if a == 0 and b == 0:
                    dp[a][b] = 0.5
                elif a == 0:
                    dp[a][b] = 1.0
                elif b == 0:
                    dp[a][b] = 0.0
                else:
                    dp[a][b] = 0.25 * (
                        dp[a - 4][b]
                        + dp[a - 3][b - 1]
                        + dp[a - 2][b - 2]
                        + dp[a - 1][b - 3]
                    )
        return dp[m][m]
Explanation:
Fill table for all (a,b) with a,b ≥ 0; clamp negative indices to base rows/columns (handled by iteration order from small to large).

Time: O(m²)  |  Space: O(m²)

Problem 3: New 21 Game (Leetcode:837)#

Problem Statement

Alice plays a game: she starts with 0 points and draws numbers 1..maxPts uniformly at random (each with probability 1/maxPts) until she stops at ≥ k points or reaches n. She stops as soon as points ≥ k. Return the probability her final score is ≤ n.

Example 1:

Input: n = 10, k = 1, maxPts = 1
Output: 1.0
Explanation: She immediately reaches k = 1.

Example 2:

Input: n = 6, k = 1, maxPts = 10
Output: 0.6

Example 3:

Input: n = 21, k = 17, maxPts = 10
Output: 0.73278

Constraints:

  • 0 <= k <= n <= 10⁴
  • 1 <= maxPts <= 10⁴
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        window = 1.0
        for i in range(1, n + 1):
            dp[i] = window / maxPts
            if i < k:
                window += dp[i]
            if i - maxPts >= 0 and i - maxPts < k:
                window -= dp[i - maxPts]
        return sum(dp[k: n + 1])
Explanation:
dp[i] = probability of reaching exactly i points while still drawing (i < k). Each step averages the last maxPts reachable states via sliding window.

Time: O(n)  |  Space: O(n)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if k == 0 or n >= k + maxPts - 1:
            return 1.0
        dp = [0.0] * (n + 1)
        dp[0] = 1.0
        for i in range(k):
            for pts in range(1, maxPts + 1):
                if i + pts <= n:
                    dp[i + pts] += dp[i] / maxPts
        return sum(dp[k: n + 1])
Explanation:
From each score < k, spread probability to i + pts. Sum probabilities for final scores in [k, n].

Time: O(k × maxPts)  |  Space: O(n)

Problem 4: Dice Throw / Probability to Reach a Score (GeeksforGeeks)#

Problem Statement

Given d identical dice, each showing 1..6 uniformly, and a target sum x, count the number of ways to roll a total of exactly x. The probability of sum x is ways / 6^d.

Example 1:

Input: d = 2, x = 7
Output: 6
Explanation: (1,6), (2,5), (3,4), (4,3), (5,2), (6,1).

Example 2:

Input: d = 3, x = 8
Output: 21

Constraints:

  • 1 <= d <= 30
  • d <= x <= 6d
Code and Explanation 

1
2
3
4
5
6
7
8
9
def count_dice_ways(d: int, x: int) -> int:
    dp = [[0] * (x + 1) for _ in range(d + 1)]
    dp[0][0] = 1
    for i in range(1, d + 1):
        for s in range(1, x + 1):
            for face in range(1, 7):
                if s - face >= 0:
                    dp[i][s] += dp[i - 1][s - face]
    return dp[d][x]
Explanation:
dp[i][s] = ways to get sum s with i dice. Each die adds face 1..6 to prior sums.

Time: O(d × x × 6)  |  Space: O(d × x)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def count_dice_ways(d: int, x: int) -> int:
    dp = [0] * (x + 1)
    dp[0] = 1
    for _ in range(d):
        ndp = [0] * (x + 1)
        for s in range(x, -1, -1):
            if dp[s] == 0:
                continue
            for face in range(1, 7):
                if s + face <= x:
                    ndp[s + face] += dp[s]
        dp = ndp
    return dp[x]

def dice_probability(d: int, x: int) -> float:
    return count_dice_ways(d, x) / (6**d)
Explanation:
Space-optimized version; probability is favorable outcomes divided by 6^d total outcomes.

Time: O(d × x × 6)  |  Space: O(x)

Problem 5: Probability of a Random Walk Reaching a Point (GeeksforGeeks)#

Problem Statement

A person starts at position 0 on a number line. At each step they move +1 or −1 with equal probability 1/2. After exactly n steps, return the probability of being at position x.

Example 1:

Input: n = 4, x = 0
Output: 0.375
Explanation: 6 of 16 paths return to 0: C(4,2)/2⁴ = 6/16.

Example 2:

Input: n = 3, x = 1
Output: 0.375
Explanation: C(3,2)/2³ = 3/8.

Constraints:

  • 1 <= n <= 30
  • |x| <= n and n − x is even (otherwise probability is 0)
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
def random_walk_prob(n: int, x: int) -> float:
    if (n - x) % 2 or abs(x) > n:
        return 0.0
    dp = [0.0] * (n + 1)
    dp[0] = 1.0
    for _ in range(n):
        ndp = [0.0] * (n + 1)
        for pos in range(-n, n + 1):
            idx = pos + n
            if not (0 <= idx < len(dp)):
                continue
            if dp[idx] == 0:
                continue
            if idx + 1 < len(ndp):
                ndp[idx + 1] += dp[idx] * 0.5
            if idx - 1 >= 0:
                ndp[idx - 1] += dp[idx] * 0.5
        dp = ndp
    return dp[x + n]
Explanation:
dp[pos] = probability at position pos after current steps. Each step splits mass equally to neighbors.

Time: O(n²)  |  Space: O(n)

1
2
3
4
5
6
7
from math import comb

def random_walk_prob(n: int, x: int) -> float:
    if (n - x) % 2 or abs(x) > n:
        return 0.0
    right = (n + x) // 2
    return comb(n, right) / (2**n)
Explanation:
Need right steps of +1 and left = n - right steps of −1. Count paths C(n, right) and divide by 2^n equally likely paths.

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

State Machine DP#

Problem 1: Best Time to Buy and Sell Stock (Leetcode:121)#

Problem Statement

You are given an array prices where prices[i] is the price of a stock on day i. You may buy once and sell once (sell after buy). Return the maximum profit. If no profit is possible, return 0.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 5
Explanation: Buy day 2 (price 1), sell day 5 (price 6).

Example 2:

Input: prices = [7,6,4,3,1]
Output: 0

Constraints:

  • 1 <= prices.length <= 10⁵
  • 0 <= prices[i] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
8
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        min_price = float("inf")
        best = 0
        for p in prices:
            min_price = min(min_price, p)
            best = max(best, p - min_price)
        return best
Explanation:
State: cheapest buy price seen. Each day update profit if selling today.

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

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        hold, sold = float("-inf"), 0
        for p in prices:
            hold = max(hold, -p)
            sold = max(sold, hold + p)
        return sold
Explanation:
hold = max cash after buying; sold = max after selling. One transaction caps transitions.

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

Problem 2: Best Time to Buy and Sell Stock II (Leetcode:122)#

Problem Statement

Given prices, you may complete as many transactions as you like (buy one and sell one share multiple times). You may not hold more than one share at a time. Return the maximum profit.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: (1,5)+(3,6) = 4+3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4

Constraints:

  • 1 <= prices.length <= 3 × 10⁴
  • 0 <= prices[i] <= 10⁴
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        profit = 0
        for i in range(1, len(prices)):
            if prices[i] > prices[i - 1]:
                profit += prices[i] - prices[i - 1]
        return profit
Explanation:
Sum all positive day-over-day deltas — equivalent to buying every local min and selling every local max.

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

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        hold, cash = float("-inf"), 0
        for p in prices:
            hold = max(hold, cash - p)
            cash = max(cash, hold + p)
        return cash
Explanation:
Unlimited trades: always pick best of holding vs cash each day.

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

Problem 3: Best Time to Buy and Sell Stock III (Leetcode:123)#

Problem Statement

Given prices, find the maximum profit with at most two transactions. You may not hold more than one share at a time.

Example 1:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: (0,3)+(1,4) = 3+3 = 6.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4

Constraints:

  • 1 <= prices.length <= 10⁵
  • 0 <= prices[i] <= 10⁵
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        buy1 = buy2 = float("-inf")
        sell1 = sell2 = 0
        for p in prices:
            buy1 = max(buy1, -p)
            sell1 = max(sell1, buy1 + p)
            buy2 = max(buy2, sell1 - p)
            sell2 = max(sell2, buy2 + p)
        return sell2
Explanation:
buy1/sell1 = first transaction; buy2/sell2 = second after first completes. Chain states left to right.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        k = 2
        n = len(prices)
        dp = [[[0, 0] for _ in range(n)] for _ in range(k + 1)]
        for t in range(1, k + 1):
            dp[t][0][1] = -prices[0]
            for i in range(1, n):
                dp[t][i][0] = max(dp[t][i - 1][0], dp[t][i - 1][1] + prices[i])
                dp[t][i][1] = max(dp[t][i - 1][1], dp[t - 1][i - 1][0] - prices[i])
        return dp[k][n - 1][0]
Explanation:
dp[t][i][0/1] = max profit on day i with ≤ t transactions, not holding / holding stock.

Time: O(k × n)  |  Space: O(k × n)

Problem 4: Best Time to Buy and Sell Stock IV (Leetcode:188)#

Problem Statement

Given integer k and array prices, return the maximum profit with at most k transactions. Same rules as Stock III.

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7

Constraints:

  • 0 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        if k == 0 or not prices:
            return 0
        n = len(prices)
        if k >= n // 2:
            return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))

        buy = [float("-inf")] * k
        sell = [0] * k
        for p in prices:
            for t in range(k):
                buy[t] = max(buy[t], (sell[t - 1] if t else 0) - p)
                sell[t] = max(sell[t], buy[t] + p)
        return sell[k - 1]
Explanation:
Same chained buy/sell arrays as Stock III, loop t = 0..k−1. If k ≥ n/2, unlimited-trade greedy applies.

Time: O(k × n)  |  Space: O(k)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def maxProfit(self, k: int, prices: list[int]) -> int:
        if not prices:
            return 0
        n = len(prices)
        if k >= n // 2:
            return sum(max(0, prices[i] - prices[i - 1]) for i in range(1, n))
        dp = [[0, 0] for _ in range(k + 1)]
        for p in prices:
            for t in range(1, k + 1):
                dp[t][1] = max(dp[t][1], dp[t][0] - p)
                dp[t][0] = max(dp[t][0], dp[t][1] + p)
        return dp[k][0]
Explanation:
Rolling per-transaction hold/cash states updated each price.

Time: O(k × n)  |  Space: O(k)

Problem 5: Best Time to Buy and Sell Stock with Cooldown (Leetcode:309)#

Problem Statement

Given prices, maximize profit with unlimited transactions, but after you sell your stock, you cannot buy on the next day (one-day cooldown). You may not hold more than one share.

Example 1:

Input: prices = [1,2,3,0,2]
Output: 3
Explanation: buy 1 sell 2, cooldown, buy 0 sell 2.

Example 2:

Input: prices = [1]
Output: 0

Constraints:

  • 1 <= prices.length <= 5000
  • 0 <= prices[i] <= 1000
Code and Explanation 

1
2
3
4
5
6
7
8
9
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        hold, sold, rest = float("-inf"), 0, 0
        for p in prices:
            prev_sold = sold
            hold = max(hold, rest - p)
            sold = hold + p
            rest = max(rest, prev_sold)
        return max(sold, rest)
Explanation:
hold = holding stock; sold = just sold today; rest = not holding (cooldown cleared). Sell transitions from hold; rest takes max idle or post-sell cooldown.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def maxProfit(self, prices: list[int]) -> int:
        n = len(prices)
        dp = [[0, 0] for _ in range(n)]
        dp[0][1] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i])
            if i >= 2:
                dp[i][1] = max(dp[i - 1][1], dp[i - 2][0] - prices[i])
            else:
                dp[i][1] = max(dp[i - 1][1], -prices[i])
        return dp[n - 1][0]
Explanation:
Buy only from state two days ago (cooldown after sell on day i−1).

Time: O(n)  |  Space: O(n)

Problem 6: Best Time to Buy and Sell Stock with Transaction Fee (Leetcode:714)#

Problem Statement

Given prices and integer fee, return the maximum profit with unlimited transactions. Each transaction pays fee when you sell. You may not hold more than one share.

Example 1:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

Example 2:

Input: prices = [1,3,7,5,10,3], fee = 3
Output: 6

Constraints:

  • 1 <= prices.length <= 5 × 10⁴
  • 1 <= prices[i] <= 5 × 10⁴
  • 0 <= fee <= 5 × 10⁴
Code and Explanation 

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        cash, hold = 0, -prices[0]
        for p in prices[1:]:
            cash = max(cash, hold + p - fee)
            hold = max(hold, cash - p)
        return cash
Explanation:
cash = max profit not holding; hold = max profit holding. Fee deducted on sell (hold + p - fee).

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

1
2
3
4
5
6
7
class Solution:
    def maxProfit(self, prices: list[int], fee: int) -> int:
        hold, cash = float("-inf"), 0
        for p in prices:
            hold = max(hold, cash - p - fee)
            cash = max(cash, hold + p)
        return cash
Explanation:
Paying fee on buy instead of sell gives identical optimal profit (shift by constant).

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

Problem 7: Binary Tree Cameras (Leetcode:968)#

Problem Statement

You are given the root of a binary tree. Install cameras on nodes to monitor all nodes. Each camera at a node monitors its node, parent, and immediate children. Return the minimum number of cameras needed.

Example 1:

Input: root = [0,0,null,0,0]
Output: 1

Example 2:

Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2

Constraints:

  • The number of nodes is in [1, 1000].
  • Node.val == 0
Code and Explanation 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution:
    def minCameraCover(self, root: "TreeNode | None") -> int:
        UNCOVERED, COVERED, CAMERA = 0, 1, 2

        def dfs(node: "TreeNode | None") -> tuple[int, int]:
            if not node:
                return 0, COVERED
            left_cam, left_state = dfs(node.left)
            right_cam, right_state = dfs(node.right)
            if left_state == UNCOVERED or right_state == UNCOVERED:
                return left_cam + right_cam + 1, CAMERA
            if left_state == CAMERA or right_state == CAMERA:
                return left_cam + right_cam, COVERED
            return left_cam + right_cam, UNCOVERED

        cameras, state = dfs(root)
        return cameras + (1 if state == UNCOVERED else 0)
Explanation:
Post-order returns (cameras, state): uncovered needs parent camera; child uncovered forces camera here; if any child has camera, this node is covered.

Time: O(n)  |  Space: O(h)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minCameraCover(self, root: "TreeNode | None") -> int:
        cameras = 0
        covered = {None}

        def dfs(node: "TreeNode | None") -> None:
            nonlocal cameras
            if not node:
                return
            dfs(node.left)
            dfs(node.right)
            if node.left not in covered or node.right not in covered:
                cameras += 1
                covered.add(node)
                covered.add(node.left)
                covered.add(node.right)

        dfs(root)
        return cameras if root in covered else cameras + 1
Explanation:
After processing children, if either child is uncovered, place a camera on the current node (covers node, both children, and parent). If root ends uncovered, add one more camera.

Time: O(n)  |  Space: O(h)