Декодирование способов и подсчёт путей

Задача о декодировании

# Encoding: A=1, B=2, ..., Z=26
# '12' → 'AB' or 'L' → 2 ways
# '226' → 'BZ' or 'VF' or 'BBF' → 3 ways
# '06' → invalid (no letter for '0')
# '10' → 'J' only → 1 way (only valid as 10, not 1+0)

s = '226'
print('Decodings for', s, ':', 3)  # Expected: 3

Формулировка DP для декодирования

def num_decodings(s):
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1  # empty prefix
    dp[1] = 0 if s[0] == '0' else 1
    
    for i in range(2, n + 1):
        # Single digit decode
        if s[i-1] != '0':
            dp[i] += dp[i-1]
        # Two digit decode
        two_digit = int(s[i-2:i])
        if 10 <= two_digit <= 26:
            dp[i] += dp[i-2]
    return dp[n]

print(num_decodings('12'))   # 2
print(num_decodings('226'))  # 3
print(num_decodings('06'))   # 0

Ловушка ведущего нуля

def num_decodings(s):
    if not s or s[0] == '0': return 0
    n = len(s)
    dp = [0] * (n + 1)
    dp[0] = 1
    dp[1] = 1  # s[0] != '0' guaranteed by guard above
    for i in range(2, n + 1):
        one = int(s[i-1])
        two = int(s[i-2:i])
        if one != 0: dp[i] += dp[i-1]  # valid single digit
        if 10 <= two <= 26: dp[i] += dp[i-2]  # valid two digits
    return dp[n]

print(num_decodings('10'))   # 1 (only 'J')
print(num_decodings('30'))   # 0 (30 > 26, '0' alone invalid)
print(num_decodings('100'))  # 0 (dp[2]=1 then '00' invalid, single '0' invalid)

Декодирование способов с оптимизацией памяти

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

print(num_decodings_o1('226'))   # 3
print(num_decodings_o1('12'))    # 2
print(num_decodings_o1('0'))     # 0

Подсчёт путей на лестнице

def climb_stairs(n):
    if n <= 2: return n
    prev2, prev1 = 1, 2
    for _ in range(3, n + 1):
        prev2, prev1 = prev1, prev1 + prev2
    return prev1

for i in range(1, 8):
    print(f'climb_stairs({i}) = {climb_stairs(i)}')
# 1, 2, 3, 5, 8, 13, 21 — Fibonacci!

Подъём по лестнице с переменным числом шагов

def count_ways(n, steps):
    dp = [0] * (n + 1)
    dp[0] = 1  # one way to stay at ground
    for i in range(1, n + 1):
        for step in steps:
            if i >= step:
                dp[i] += dp[i - step]
    return dp[n]

# Steps of 1 or 2 (classic climbing stairs)
print(count_ways(5, [1, 2]))    # 8
# Steps of 1, 3, or 5
print(count_ways(5, [1, 3, 5])) # 5
# Steps of 2 or 3
print(count_ways(6, [2, 3]))    # 3 (2+2+2, 3+3, 2+4-invalid, 2+2+2, 3+3, 3+2+1-no...)

Подъём по лестнице с минимальной стоимостью

def min_cost_climbing(cost):
    n = len(cost)
    if n == 1: return cost[0]
    dp = [0] * n
    dp[0] = cost[0]
    dp[1] = cost[1]
    for i in range(2, n):
        dp[i] = cost[i] + min(dp[i-1], dp[i-2])
    return min(dp[-1], dp[-2])  # can start from step 0 or 1

print(min_cost_climbing([10, 15, 20]))      # 15
print(min_cost_climbing([1, 100, 1, 1, 1, 100, 1, 1, 100, 1]))  # 6

Декодирование способов II: символ подстановки

def num_decodings_ii(s):
    MOD = 10**9 + 7
    prev2, prev1 = 1, 9 if s[0] == '*' else (0 if s[0] == '0' else 1)
    for i in range(1, len(s)):
        curr = 0
        c, p = s[i], s[i-1]
        # Single digit
        if c == '*': curr += 9 * prev1
        elif c != '0': curr += prev1
        # Two digits
        if p == '*' and c == '*': curr += 15 * prev2  # 11-19(9) + 21-26(6)
        elif p == '*': curr += (2 if c <= '6' else 1) * prev2
        elif c == '*': curr += (9 if p == '1' else (6 if p == '2' else 0)) * prev2
        else:
            two = int(p + c)
            if 10 <= two <= 26: curr += prev2
        prev2, prev1 = prev1, curr % MOD
    return prev1 % MOD

print(num_decodings_ii('*'))   # 9
print(num_decodings_ii('1*'))  # 18

Связь с Фибоначчи

# Fibonacci family: dp[i] = f(dp[i-1], dp[i-2])
# Fibonacci itself:        dp[i] = dp[i-1] + dp[i-2]
# Climbing stairs:         dp[i] = dp[i-1] + dp[i-2]
# Decode ways:             dp[i] = (dp[i-1] if one_valid) + (dp[i-2] if two_valid)
# Min cost stairs:         dp[i] = cost[i] + min(dp[i-1], dp[i-2])
# House robber:            dp[i] = max(dp[i-1], nums[i] + dp[i-2])

# All solved with 2 rolling variables:
prev2, prev1 = 0, 1
for _ in range(10):
    prev2, prev1 = prev1, prev1 + prev2
print('Fibonacci F(10):', prev1)  # 89

Подсчёт путей в таблице

def unique_paths(m, n):
    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]

# Or use math for O(1) solution
import math
def unique_paths_math(m, n):
    return math.comb(m + n - 2, m - 1)

print(unique_paths(3, 7))         # 28
print(unique_paths_math(3, 7))    # 28
print(unique_paths(3, 3))         # 6

Итоги типичных ошибок на собеседовании

# Common bug: checking two_digit <= 26 without >= 10
def buggy_decode(s):
    dp = [0] * (len(s) + 1)
    dp[0] = dp[1] = 1
    for i in range(2, len(s) + 1):
        if s[i-1] != '0': dp[i] += dp[i-1]
        two = int(s[i-2:i])
        # BUG: '07' gives two=7, and 7 <= 26 would add dp[i-2]
        # Fix: require two >= 10
        if 10 <= two <= 26: dp[i] += dp[i-2]  # CORRECT
    return dp[len(s)]

print(buggy_decode('06'))   # 0 (correct, '0' alone invalid)
print(buggy_decode('07'))   # 0 (correct, '07' not valid, '0' alone invalid)
print(buggy_decode('27'))   # 1 (only 'BG', 27>26 so no two-digit)

Быстрая проверка

Итоги урока