def dfs(node, parent, tree):
    dp[node] = base_case
    for child in tree[node]:
        if child != parent:
            dfs(child, node, tree)
            dp[node] = combine(dp[node], dp[child])

from functools import lru_cache

def count(num_str):
    @lru_cache(maxsize=None)
    def dp(pos, tight, started, state):
        if pos == len(num_str):
            return 1 if started else 0
        limit = int(num_str[pos]) if tight else 9
        result = 0
        for d in range(0, limit + 1):
            result += dp(
                pos + 1,
                tight and d == limit,
                started or d > 0,
                next_state(state, d)
            )
        return result
    return dp(0, True, False, initial_state)

# Example: Travelling Salesman Problem
@lru_cache(maxsize=None)
def dp(mask, pos):
    if mask == (1 << n) - 1:  # all cities visited
        return dist[pos][0]
    result = float('inf')
    for next_city in range(n):
        if not (mask & (1 << next_city)):
            result = min(result, dist[pos][next_city] + dp(mask | (1 << next_city), next_city))
    return result