Ottimizzazione dello spazio per la DP 2D

Perché lo spazio è importante nel DP 2D

# Full 2D DP: O(mn) space
# LCS for 1000-char strings
m, n = 1000, 1000
dp_2d_size = m * n * 8  # bytes (64-bit ints)
print(f'2D table: {dp_2d_size:,} bytes = {dp_2d_size//1024} KB')

# 1D rolling array: O(n) space
dp_1d_size = n * 8
print(f'1D array: {dp_1d_size:,} bytes = {dp_1d_size} bytes')
print(f'Space saving: {dp_2d_size // dp_1d_size}x')

Schema dell’array scorrevole

# Rolling array template for 2D DP
# Before update: dp[j] holds dp[i-1][j] (previous row)
# After update: dp[j] holds dp[i][j] (current row)

def rolling_array_template(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * (n + 1)  # represents one row
    for i in range(1, m + 1):
        diag = 0  # stores dp[i-1][j-1] before overwrite
        for j in range(1, n + 1):
            temp = dp[j]  # save dp[i-1][j] before overwriting
            # compute dp[i][j] using dp[j] (above) and dp[j-1] (left) and diag
            dp[j] = diag + dp[j] + dp[j-1]  # placeholder logic
            diag = temp
    return dp[n]

LCS con spazio O(min m,n)

def lcs_space_opt(text1, text2):
    # Ensure text2 is the shorter one
    if len(text1) < len(text2):
        text1, text2 = text2, text1
    m, n = len(text1), len(text2)
    dp = [0] * (n + 1)
    for i in range(1, m + 1):
        diag = 0
        for j in range(1, n + 1):
            temp = dp[j]  # dp[i-1][j]
            if text1[i-1] == text2[j-1]:
                dp[j] = diag + 1
            else:
                dp[j] = max(dp[j], dp[j-1])
            diag = temp
    return dp[n]

print(lcs_space_opt('ABCBDAB', 'BDCABA'))  # 4
print(lcs_space_opt('AGGTAB', 'GXTXAYB')) # 4

Distanza di modifica con spazio O(n)

def edit_dist_opt(s, t):
    m, n = len(s), len(t)
    dp = list(range(n + 1))   # row 0: dp[0][j] = j
    for i in range(1, m + 1):
        diag = dp[0]           # dp[i-1][0] before dp[0] update
        dp[0] = i              # dp[i][0] = i
        for j in range(1, n + 1):
            temp = dp[j]       # dp[i-1][j]
            cost = 0 if s[i-1] == t[j-1] else 1
            dp[j] = min(
                dp[j-1] + 1,  # insert
                dp[j] + 1,    # delete
                diag + cost   # replace or match
            )
            diag = temp
    return dp[n]

print(edit_dist_opt('horse', 'ros'))  # 3
print(edit_dist_opt('intention', 'execution'))  # 5

Somma minima del percorso con spazio O(n)

def min_path_sum_opt(grid):
    m, n = len(grid), len(grid[0])
    dp = [float('inf')] * n
    dp[0] = 0
    for i in range(m):
        # Update first column (only from above)
        dp[0] += grid[i][0]
        for j in range(1, n):
            # min of above (dp[j] = old) and left (dp[j-1] = updated)
            dp[j] = grid[i][j] + min(dp[j], dp[j-1])
    return dp[n-1]

grid = [[1,3,1],[1,5,1],[4,2,1]]
print(min_path_sum_opt(grid))  # 7

Quando è necessario accedere alla diagonale

# Recap: the diagonal save pattern
# Without it: dp[j-1] updated (left) and dp[j] about to be overwritten
# With it:

def show_diagonal_pattern(s1, s2):
    n = len(s2)
    dp = [0] * (n + 1)
    for ch1 in s1:
        diag = 0  # was dp[i-1][0] = 0 for LCS
        for j, ch2 in enumerate(s2, 1):
            temp = dp[j]  # SAVE before overwrite
            if ch1 == ch2:
                dp[j] = diag + 1  # use saved diagonal
            else:
                dp[j] = max(dp[j], dp[j-1])
            diag = temp  # advance diagonal
    return dp[n]

print(show_diagonal_pattern('ABCBDAB', 'BDCABA'))  # 4

Ottimizzazione dello spazio dello zaino 2D

def knapsack_01(weights, values, capacity):
    dp = [0] * (capacity + 1)
    for w, v in zip(weights, values):
        # Reverse order: prevents using the same item twice
        for c in range(capacity, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[capacity]

weights = [1, 3, 4, 5]
values  = [1, 4, 5, 7]
cap = 7
print(knapsack_01(weights, values, cap))  # 9 (items 3+4: weight 3+4=7, value 4+5=9)

Iterazione in avanti e all'indietro

# 0/1 Knapsack: each item used AT MOST ONCE → iterate reverse
def knapsack_01_demo(weights, values, cap):
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w-1, -1):  # REVERSE
            dp[c] = max(dp[c], dp[c-w] + v)
    return dp[cap]

# Unbounded Knapsack: items can be reused → iterate forward
def knapsack_unbounded(weights, values, cap):
    dp = [0] * (cap + 1)
    for c in range(1, cap + 1):
        for w, v in zip(weights, values):
            if c >= w:
                dp[c] = max(dp[c], dp[c-w] + v)  # FORWARD
    return dp[cap]

print(knapsack_01_demo([2,3],[3,4],5))     # 7
print(knapsack_unbounded([2,3],[3,4],5))   # 8 (use weight-2 twice: 3+3=6? or 4+... )

Percorsi unici con spazio O(n)

def unique_paths_opt(m, n):
    dp = [1] * n  # first row: all 1s
    for i in range(1, m):
        for j in range(1, n):
            dp[j] += dp[j-1]  # above (dp[j]) + left (dp[j-1])
    return dp[n-1]

# With obstacles
def unique_paths_obstacles_opt(grid):
    m, n = len(grid), len(grid[0])
    dp = [0] * n
    dp[0] = 1
    for i in range(m):
        if grid[i][0] == 1: dp[0] = 0  # blocked column
        for j in range(1, n):
            if grid[i][j] == 1: dp[j] = 0  # blocked
            else: dp[j] += dp[j-1]
    return dp[n-1]

print(unique_paths_opt(3, 7))  # 28
print(unique_paths_obstacles_opt([[0,0,0],[0,1,0],[0,0,0]]))  # 2

Buffer a due righe per ricorrenze complesse

def lcs_two_row_buffer(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)  # dp[i-1]
    curr = [0] * (n + 1)  # dp[i]
    for i in range(1, m + 1):
        curr[0] = 0
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, prev  # swap (curr becomes prev)
    return prev[n]  # after swap, prev holds the last computed row

print(lcs_two_row_buffer('ABCBDAB', 'BDCABA'))  # 4

Quando l'ottimizzazione dello spazio non è possibile

# When reconstruction needed: must keep full table or use Hirschberg
# Hirschberg's idea: compute LCS length in O(n) space at midpoint of s1,
# recurse on left and right halves. O(mn) time, O(n) space + reconstruction.

# For interview: mention the trade-off
# 'I can reduce to O(n) space if only the value is needed.
#  To also reconstruct the sequence, I need the full O(mn) table
#  or a more complex divide-and-conquer approach.'

print('Space opt: O(n) for length only')
print('Full table: O(mn) needed for reconstruction')

Verifica rapida

Riepilogo della lezione