1D Dynamic Programming

In one-dimensional DP, the state is defined by a single index (or value) and the solution builds on previous states linearly. These problems typically involve a linear sequence (array or string) where each state dp[i] represents an optimal result for a subproblem ending at index i.

House Robber (Linear Street, No Adjacent Houses)

Problem: Given a list of non-negative integers representing money in houses along a street, determine the maximum amount you can rob without robbing two adjacent houses. (LeetCode #198 House Robber)

Idea:

Use DP to decide for each house whether to rob it or skip it. Let dp[i] be the maximum loot from houses 0...i. For each house i, either rob it (and add money from house i plus dp[i-2] since you must skip the immediate previous) or skip it (take dp[i-1]).

• State: dp[i] = max money from 0 to i.
• Recurrence: dp[i] = max(nums[i] + dp[i-2], dp[i-1])
• Base Cases: dp[0] = nums[0], dp[1] = max(nums[0], nums[1]).

Bottom-Up (Tabulation) Implementation:

def rob_linear(nums):
    n = len(nums)
    if n == 0: return 0
    if n == 1: return nums[0]
    dp = [0] * n
    dp[0] = nums[0]
    dp[1] = max(nums[0], nums[1])
    for i in range(2, n):
        dp[i] = max(nums[i] + dp[i-2], dp[i-1])
    return dp[n-1]

Top-Down (Memoized) Implementation:

from functools import lru_cache
def rob_linear_td(nums):
    n = len(nums)
    @lru_cache(None)
    def f(i):
        if i < 0: return 0
        if i == 0: return nums[0]
        return max(nums[i] + f(i-2), f(i-1))
    return f(n-1) if n > 0 else 0

House Robber with Circular Constraint (Circular Street)

Problem: Houses are arranged in a circle. Find max loot without robbing adjacent houses, considering circular adjacency. (LeetCode #213 House Robber II)

Modification:

Cannot rob both first and last. Break into two linear cases:

1. Ignore the first house, rob from houses 1 to n-1.
2. Ignore the last house, rob from houses 0 to n-2.

def rob_circular(nums):
    n = len(nums)
    if n == 0: return 0
    if n == 1: return nums[0]
    
    def rob_range(arr): # O(1) space linear robber
        prev1, prev2 = 0, 0 # dp[i-1], dp[i-2]
        for num in arr:
            current_max = max(num + prev2, prev1)
            prev2 = prev1
            prev1 = current_max
        return prev1
        
    # Case 1: Rob houses 0 to n-2 (exclude last)
    max1 = rob_range(nums[:-1])
    # Case 2: Rob houses 1 to n-1 (exclude first)
    max2 = rob_range(nums[1:])
    
    return max(max1, max2)

Word Break (String Segmentation Problem)

Problem: Given a string and a dictionary, can the string be segmented into space-separated dictionary words? (LeetCode #139 Word Break)

Idea:

dp[i] = True if s[0:i] can be segmented. Transition: dp[i] is True if there exists j < i such that dp[j] is True AND s[j:i] is in wordDict. Base: dp[0] = True.

def word_break(s, wordDict):
    n = len(s)
    wordSet = set(wordDict)
    dp = [False] * (n+1)
    dp[0] = True
    for i in range(1, n+1):
        for j in range(i):
            if dp[j] and s[j:i] in wordSet:
                dp[i] = True
                break
    return dp[n]

Decode Ways (Digit String Decoding)

Problem: Message encoded 'A'->1, ..., 'Z'->26. Given digit string, count ways to decode. (LeetCode #91 Decode Ways)

Idea:

dp[i] = ways to decode prefix of length i. Recurrence: dp[i] = 0; if s[i-1] != '0', dp[i] += dp[i-1]. If "10" <= s[i-2:i] <= "26", dp[i] += dp[i-2]. Base: dp[0]=1, dp[1]=1 if s[0]!='0' else 0.

def num_decodings(s: str) -> int:
    n = len(s)
    if n == 0: return 0
    dp = [0] * (n+1)
    dp[0] = 1
    dp[1] = 1 if s[0] != '0' else 0
    for i in range(2, n+1):
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        two_digits = int(s[i-2:i])
        if 10 <= two_digits <= 26:
            dp[i] += dp[i-2]
    return dp[n]

Coin Change (Minimum Coins Needed)

Problem: Given coin denominations and target amount, find fewest coins for amount. (LeetCode #322 Coin Change)

Idea:

dp[x] = min coins for amount x. Init dp[0]=0, others inf. Transition: For each coin c, for each amount x from c to target: dp[x] = min(dp[x], dp[x-c] + 1).

def coin_change(coins, amount):
    INF = float('inf')
    dp = [INF] * (amount + 1)
    dp[0] = 0
    for coin in coins:
        for x in range(coin, amount+1):
            if dp[x-coin] != INF: # Check if subproblem is solvable
                 dp[x] = min(dp[x], dp[x-coin] + 1)
    return dp[amount] if dp[amount] != INF else -1

2D Dynamic Programming

Two-dimensional DP typically involves a state defined by two indices (e.g., positions in two sequences, or grid coordinates). Uses a 2D table dp[i][j].

Unique Paths (Grid Traversal without Obstacles)

Problem: Robot at top-left of m x n grid, moves right/down. Unique paths to bottom-right? (LeetCode #62)

Idea:

dp[i][j] = paths to cell (i,j). Recurrence: dp[i][j] = dp[i-1][j] + dp[i][j-1]. Base: First row/col cells have 1 path.

def unique_paths(m, n):
    dp = [[0]*n for _ in range(m)]
    for i in range(m): dp[i][0] = 1
    for j in range(n): dp[0][j] = 1
    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]

Unique Paths with Obstacles (Grid with Blocks)

Problem: Grid has obstacles (1). Find unique paths avoiding obstacles. (LeetCode #63)

Idea:

If grid[i][j] == 1, dp[i][j] = 0. Else, dp[i][j] = dp[i-1][j] + dp[i][j-1] (if non-obstacle neighbors).

def unique_paths_with_obstacles(grid):
    m, n = len(grid), len(grid[0])
    dp = [[0]*n for _ in range(m)]
    if grid[0][0] == 1: return 0
    dp[0][0] = 1
    for i in range(1, m): dp[i][0] = 0 if grid[i][0] == 1 else dp[i-1][0]
    for j in range(1, n): dp[0][j] = 0 if grid[0][j] == 1 else dp[0][j-1]
    for i in range(1, m):
        for j in range(1, n):
            if grid[i][j] == 1: dp[i][j] = 0
            else: dp[i][j] = dp[i-1][j] + dp[i][j-1]
    return dp[m-1][n-1]

Longest Common Subsequence (LCS of Two Strings)

Problem: Given two strings, find length of their longest common subsequence. (LeetCode #1143)

Idea:

dp[i][j] = LCS length for text1[:i] and text2[:j]. If text1[i-1] == text2[j-1], dp[i][j] = dp[i-1][j-1] + 1. Else, dp[i][j] = max(dp[i-1][j], dp[i][j-1]).

def longest_common_subsequence(text1, text2):
    n, m = len(text1), len(text2)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

Edit Distance (Minimum String Edit)

Problem: Min operations (insert, delete, replace) to convert word1 to word2. (LeetCode #72)

Idea:

dp[i][j] = min edits for word1[:i] to word2[:j]. If word1[i-1] == word2[j-1], dp[i][j] = dp[i-1][j-1]. Else, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]).

def min_distance(word1, word2):
    n, m = len(word1), len(word2)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = i
    for j in range(m+1): dp[0][j] = j
    
    for i in range(1, n+1):
        for j in range(1, m+1):
            if word1[i-1] == word2[j-1]:
                dp[i][j] = dp[i-1][j-1]
            else:
                dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

Longest Palindromic Subsequence (LPS in a String)

Problem: Given string s, find length of its longest palindromic subsequence. (LeetCode #516)

Idea:

dp[i][j] = length of LPS in s[i..j]. If s[i] == s[j], dp[i][j] = dp[i+1][j-1] + 2. Else, dp[i][j] = max(dp[i+1][j], dp[i][j-1]). Base: dp[i][i]=1.

def longest_palindromic_subseq(s: str) -> int:
    n = len(s)
    if n == 0: return 0
    dp = [[0]*n for _ in range(n)]
    for i in range(n): dp[i][i] = 1
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = 2 + (dp[i+1][j-1] if length > 2 else 0)
            else:
                dp[i][j] = max(dp[i+1][j], dp[i][j-1])
    return dp[0][n-1]

Interactive Animation (House Robber - Linear)

This animation demonstrates the 1D Dynamic Programming approach for the "House Robber" problem. Given an array of money in houses, it calculates the maximum amount that can be robbed without robbing adjacent houses.