동적 계획법

fib(5) → fib(3)
fib(5) → fib(4) → fib(3)

def fib_dp(n):
    if n < 0:
        raise ValueError("n must be nonnegative")
    if n < 2:
        return n
    table = [0] * (n + 1)
    table[1] = 1
    for i in range(2, n + 1):
        table[i] = table[i - 1] + table[i - 2]
    return table[n]


def fib_memo(n, cache=None):
    if n < 0:
        raise ValueError("n must be nonnegative")
    if cache is None:
        cache = {}
    if n in cache:
        return cache[n]
    if n < 2:
        cache[n] = n
    else:
        cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]


def main():
    calls = 0

    def naive(n):
        nonlocal calls
        calls += 1
        return n if n < 2 else naive(n - 1) + naive(n - 2)

    assert naive(5) == 5 and calls == 15
    print(f"naive fib(5): value=5; calls={calls}")
    cache = {}
    assert fib_memo(5, cache) == 5 and len(cache) == 6
    print(f"memo fib(5): value=5; stored states={len(cache)}")
    assert fib_dp(5) == 5
    print("table fib(5): value=5")
    for n, answer in [(0, 0), (1, 1), (10, 55), (50, 12586269025)]:
        assert fib_memo(n) == fib_dp(n) == answer
        print(f"memo/table fib({n}): {answer}")
    for function in (fib_dp, fib_memo):
        try:
            function(-1)
        except ValueError:
            pass
        else:
            raise AssertionError("negative n was accepted")
    print("negative n: rejected; all checks passed")


if __name__ == "__main__":
    main()

naive fib(5): value=5; calls=15
memo fib(5): value=5; stored states=6
table fib(5): value=5
memo/table fib(0): 0
memo/table fib(1): 1
memo/table fib(10): 55
memo/table fib(50): 12586269025
negative n: rejected; all checks passed

dp(cur, visited)
  = cur에서 출발해 아직 방문하지 않은 도시를 모두 방문하고
    0으로 돌아가는 데 필요한 최소 추가 비용

cost[cur][nxt] + dp(nxt, visited | (1 << nxt))

from itertools import permutations
from math import inf


def tsp(cost):
    n = len(cost)
    if n == 0 or any(len(row) != n for row in cost):
        raise ValueError("cost must be a nonempty square matrix")
    if any(type(value) is not int or value < 0 for row in cost for value in row):
        raise ValueError("costs must be nonnegative integers; 0 means no edge")
    if n == 1:
        return 0
    full = (1 << n) - 1
    memo = [[None] * (1 << n) for _ in range(n)]

    def dfs(cur, visited):
        if visited == full:
            return cost[cur][0] if cost[cur][0] != 0 else inf
        if memo[cur][visited] is not None:
            return memo[cur][visited]
        best = inf
        for nxt in range(n):
            if visited & (1 << nxt) or cost[cur][nxt] == 0:
                continue
            remaining = dfs(nxt, visited | (1 << nxt))
            if remaining != inf:
                best = min(best, cost[cur][nxt] + remaining)
        memo[cur][visited] = best
        return best

    result = dfs(0, 1)
    return None if result == inf else result


# 작은 입력의 답은 DP 상태를 쓰지 않는 순열 탐색과 대조한다.
def brute_tsp(cost):
    if len(cost) == 1:
        return 0
    best = inf
    for order in permutations(range(1, len(cost))):
        route = (0,) + order + (0,)
        edges = [cost[a][b] for a, b in zip(route, route[1:])]
        if all(edge != 0 for edge in edges):
            best = min(best, sum(edges))
    return None if best == inf else best


def main():
    cases = [
        ("one city", [[0]], 0),
        ("two cities", [[0, 3], [5, 0]], 8),
        ("no return edge", [[0, 3], [0, 0]], None),
        ("four cities", [[0, 10, 15, 20], [5, 0, 9, 10],
                         [6, 13, 0, 12], [8, 8, 9, 0]], 35),
        ("five cities", [[0 if i == j else 1 for j in range(5)]
                         for i in range(5)], 5),
        ("large costs", [[0, 10**15], [10**15, 0]], 2 * 10**15),
        ("disconnected", [[0, 1, 0], [1, 0, 0], [0, 0, 0]], None),
    ]
    for name, cost, answer in cases:
        before = [row[:] for row in cost]
        assert tsp(cost) == brute_tsp(cost) == answer
        assert cost == before
        print(f"{name}: {answer}")
    for invalid in ([], [[0, 1]], [[0, -1], [1, 0]]):
        try:
            tsp(invalid)
        except ValueError:
            pass
        else:
            raise AssertionError("invalid matrix was accepted")
    print("invalid matrix: rejected; all checks passed")


if __name__ == "__main__":
    main()

one city: 0
two cities: 8
no return edge: None
four cities: 35
five cities: 5
large costs: 2000000000000000
disconnected: None
invalid matrix: rejected; all checks passed