Dynamic Programming

You are climbing a staircase that takes n steps to reach the top. Each time you can climb either 1 or 2 steps. Return the number of distinct ways you can climb to the top.

To stand on step \(i\), you came from step \(i-1\) (one step) or step \(i-2\) (two steps), so \(\text{ways}(i) = \text{ways}(i-1) + \text{ways}(i-2)\), which is the Fibonacci recurrence. Since each value only depends on the previous two, keep just two variables instead of a full DP array.

def climbStairs(n: int) -> int:
    prev, curr = 1, 1  # ways(0), ways(1)
    for _ in range(n - 1):
        prev, curr = curr, prev + curr
    return curr
    

Given an array coins of different denominations and an integer amount, return the fewest number of coins needed to make up that amount, or -1 if it cannot be made. You have an infinite supply of each coin.

Greedy fails here (for example, coins [1, 3, 4] and amount 6), so use bottom-up DP. Let dp[a] be the fewest coins needed for amount a. Then \(dp[a] = \min_{c \le a}(dp[a - c] + 1)\) over all coins c, with dp[0] = 0. Amounts that are unreachable stay at infinity. Here \(A\) is the amount and \(C\) is the number of coin types.

def coinChange(coins: list[int], amount: int) -> int:
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a:
                dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] != float('inf') else -1
    

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

The classic DP is \(O(N^2)\). The optimal approach keeps an array tails where tails[i] is the smallest possible tail value of an increasing subsequence of length i + 1. This array is always sorted, so for each number use binary search (bisect_left) to find the first tail that is greater than or equal to it and replace that tail; if the number is larger than every tail, append it. Replacing keeps tails as small as possible, leaving more room to extend later. The length of tails is the answer. Note that tails itself is not necessarily a valid subsequence, only its length is meaningful.

from bisect import bisect_left

def lengthOfLIS(nums: list[int]) -> int:
    tails = []
    for x in nums:
        i = bisect_left(tails, x)
        if i == len(tails):
            tails.append(x)
        else:
            tails[i] = x
    return len(tails)
    

Given two strings text1 and text2, return the length of their longest common subsequence. If there is no common subsequence, return 0.

Let dp[i][j] be the LCS length of the first i characters of text1 and the first j characters of text2. If the characters match, extend the diagonal: \(dp[i][j] = dp[i-1][j-1] + 1\). Otherwise take the better of dropping one character from either string: \(dp[i][j] = \max(dp[i-1][j], dp[i][j-1])\). Each row only depends on the previous row, so keep just two rows, and make the shorter string the column dimension to get \(O(\min(M, N))\) space.

def longestCommonSubsequence(text1: str, text2: str) -> int:
    # Make text2 the shorter string so rows are as small as possible
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    n = len(text2)

    prev = [0] * (n + 1)
    for i in range(1, len(text1) + 1):
        curr = [0] * (n + 1)
        for j in range(1, n + 1):
            if text1[i - 1] == text2[j - 1]:
                curr[j] = prev[j - 1] + 1
            else:
                curr[j] = max(prev[j], curr[j - 1])
        prev = curr
    return prev[n]
    

Given a string s and a dictionary of strings wordDict, return True if s can be segmented into a space-separated sequence of one or more dictionary words. The same word may be reused multiple times.

Let dp[i] be True if the prefix s[:i] can be segmented. dp[0] is True (empty prefix). For each position i, check whether some last word s[i-l:i] is in the dictionary while the prefix before it, dp[i-l], is also segmentable. Store the words in a set for \(O(1)\) average lookups, and only try lengths up to the longest dictionary word \(L\), since longer pieces can never match. Slicing and hashing each substring costs \(O(L)\), which gives the \(O(N \cdot L^2)\) bound, where \(W\) is the total number of characters in the dictionary.

def wordBreak(s: str, wordDict: list[str]) -> bool:
    words = set(wordDict)
    max_len = max(len(w) for w in words)
    n = len(s)

    dp = [False] * (n + 1)
    dp[0] = True
    for i in range(1, n + 1):
        for l in range(1, min(i, max_len) + 1):
            if dp[i - l] and s[i - l:i] in words:
                dp[i] = True
                break
    return dp[n]
    

Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target. Sequences with a different order are counted as different combinations.

Because order matters, this really counts permutations. Let dp[t] be the number of ordered sequences that sum to t, with dp[0] = 1 (the empty sequence). Then \(dp[t] = \sum dp[t - \text{num}]\) over every num that fits. The loop order is important: put the target in the outer loop and the numbers in the inner loop so every number can be the last element at each sum. Swapping the loops would count each set of numbers only once (as in Coin Change II). Here \(T\) is the target and \(N\) is the length of nums.

def combinationSum4(nums: list[int], target: int) -> int:
    dp = [0] * (target + 1)
    dp[0] = 1
    for t in range(1, target + 1):
        for num in nums:
            if num <= t:
                dp[t] += dp[t - num]
    return dp[target]
    

You are a robber planning to rob houses along a street. Each house has a certain amount of money, nums[i], but adjacent houses have connected security systems, so robbing two adjacent houses alerts the police. Return the maximum amount you can rob without alerting the police.

At each house you either skip it (keep the best so far) or rob it (add its value to the best result from two houses back): \(dp[i] = \max(dp[i-1],\; dp[i-2] + \text{nums}[i])\). Only the last two values are needed, so two variables replace the DP array.

def rob(nums: list[int]) -> int:
    prev, curr = 0, 0  # best up to i-2, best up to i-1
    for n in nums:
        prev, curr = curr, max(curr, prev + n)
    return curr
    

Same as House Robber, but all houses are arranged in a circle, so the first and last houses are adjacent. Return the maximum amount you can rob without alerting the police.

The first and last houses cannot both be robbed, so split the circle into two linear problems: rob from houses 0..n-2 (skipping the last) or from houses 1..n-1 (skipping the first), and take the better result. Both cases reuse the House Robber logic. A single house is a special case, since both ranges would be empty. Index ranges are used instead of slicing to avoid copying the array.

def rob(nums: list[int]) -> int:
    if len(nums) == 1:
        return nums[0]

    def rob_range(lo: int, hi: int) -> int:
        prev, curr = 0, 0
        for i in range(lo, hi + 1):
            prev, curr = curr, max(curr, prev + nums[i])
        return curr

    return max(rob_range(0, len(nums) - 2), rob_range(1, len(nums) - 1))
    

A message containing letters from A-Z is encoded to numbers using the mapping 'A' -> 1, 'B' -> 2, ..., 'Z' -> 26. Given a string s containing only digits, return the number of ways to decode it.

Let dp[i] be the number of ways to decode the first i characters. The last piece is either a single digit or a two-digit number. A single digit is valid if it is not '0' and adds dp[i-1]. A two-digit number is valid if it lies between 10 and 26 and adds dp[i-2]. A leading '0' means there are no valid decodings. Only the last two values are needed, so the table is replaced by two variables.

def numDecodings(s: str) -> int:
    if s[0] == '0':
        return 0

    prev2, prev1 = 1, 1  # dp[i-2], dp[i-1]
    for i in range(1, len(s)):
        curr = 0
        if s[i] != '0':
            curr += prev1
        if 10 <= int(s[i - 1:i + 1]) <= 26:
            curr += prev2
        prev2, prev1 = prev1, curr
    return prev1
    

A robot is located at the top-left corner of an m x n grid and can only move either down or right at any point in time. Return the number of unique paths the robot can take to reach the bottom-right corner.

The DP solution \(dp[r][c] = dp[r-1][c] + dp[r][c-1]\) takes \(O(M \cdot N)\) time. Combinatorics gives a direct formula: every path has exactly \(m-1\) down moves and \(n-1\) right moves, \(m+n-2\) moves in total, so the number of paths is the number of ways to choose which of those moves are the down moves:

\[ \binom{m+n-2}{m-1} \]

math.comb computes this using about \(\min(m, n)\) arithmetic operations.

from math import comb

def uniquePaths(m: int, n: int) -> int:
    return comb(m + n - 2, m - 1)
    

You are given an integer array nums. You are initially positioned at the first index, and each element represents your maximum jump length from that position. Return True if you can reach the last index, or False otherwise.

A DP or backtracking solution is unnecessary; a greedy scan is enough. Track reach, the farthest index reachable so far. For each index i, if i > reach then this position cannot be reached at all, so return False. Otherwise update reach = max(reach, i + nums[i]). If the scan finishes, the last index is reachable.

def canJump(nums: list[int]) -> bool:
    reach = 0
    for i, jump in enumerate(nums):
        if i > reach:
            return False
        reach = max(reach, i + jump)
    return True
    

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.

If the total sum is odd, the answer is immediately False. Otherwise the task reduces to the 0/1 knapsack question: is there a subset with sum exactly \(S = \text{total} / 2\)? The usual 1D DP keeps a boolean array and updates it from high to low sums for each number. A faster equivalent uses a bitset stored in a Python integer, where bit \(k\) is set if sum \(k\) is reachable. Taking a number n turns every reachable sum \(k\) into \(k + n\), which is just a left shift: bits |= bits << n. This updates all sums in one word-parallel operation. At the end, check whether bit \(S\) is set.

def canPartition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False
    target = total // 2

    bits = 1  # bit k is set if sum k is reachable; sum 0 is reachable
    for n in nums:
        bits |= bits << n
    return (bits >> target) & 1 == 1