Advanced Dynamic Programming

def held_karp(distance: list[list[int]]) -> int:
    """Minimum Hamiltonian cycle starting and ending at vertex 0."""
    n = len(distance)
    if n == 0:
        return 0
    if n > 20 or any(len(row) != n for row in distance):
        raise ValueError("expected a square matrix with at most 20 cities")
    if n == 1:
        return 0

    infinity = float("inf")
    dp = [[infinity] * n for _ in range(1 << n)]
    dp[1][0] = 0

    for mask in range(1 << n):
        if (mask & 1) == 0:
            continue
        for last in range(n):
            if dp[mask][last] == infinity:
                continue
            for nxt in range(n):
                if mask & (1 << nxt):
                    continue
                next_mask = mask | (1 << nxt)
                dp[next_mask][nxt] = min(
                    dp[next_mask][nxt], dp[mask][last] + distance[last][nxt]
                )

    full = (1 << n) - 1
    return min(dp[full][last] + distance[last][0] for last in range(n))

graph = [
    [0, 10, 15, 20], [10, 0, 35, 25],
    [15, 35, 0, 30], [20, 25, 30, 0],
]
assert held_karp(graph) == 80
assert held_karp([[7]]) == 0

import java.util.Arrays;

public class BitmaskTsp {
    static long heldKarp(long[][] distance) {
        int n = distance.length;
        if (n == 0) return 0L;
        if (n > 20) throw new IllegalArgumentException("at most 20 cities");
        for (long[] row : distance) {
            if (row.length != n) throw new IllegalArgumentException("matrix must be square");
        }
        if (n == 1) return 0L;

        long infinity = Long.MAX_VALUE;
        long[][] dp = new long[1 << n][n];
        for (long[] row : dp) Arrays.fill(row, infinity);
        dp[1][0] = 0L;

        for (int mask = 0; mask < (1 << n); mask++) {
            if ((mask & 1) == 0) continue;
            for (int last = 0; last < n; last++) {
                if (dp[mask][last] == infinity) continue;
                for (int next = 0; next < n; next++) {
                    if ((mask & (1 << next)) != 0) continue;
                    int nextMask = mask | (1 << next);
                    long candidate = Math.addExact(dp[mask][last], distance[last][next]);
                    dp[nextMask][next] = Math.min(dp[nextMask][next], candidate);
                }
            }
        }

        int full = (1 << n) - 1;
        long answer = infinity;
        for (int last = 0; last < n; last++) {
            if (dp[full][last] == infinity) continue;
            answer = Math.min(answer, Math.addExact(dp[full][last], distance[last][0]));
        }
        return answer;
    }

    public static void main(String[] args) {
        long[][] graph = {
            {0,10,15,20}, {10,0,35,25}, {15,35,0,30}, {20,25,30,0}
        };
        if (heldKarp(graph) != 80L || heldKarp(new long[][]{{7}}) != 0L) {
            throw new AssertionError();
        }
    }
}

from functools import cache

def count_with_digit_sum(bound: int, target: int) -> int:
    if bound < 0 or target < 0:
        return 0
    digits = [int(ch) for ch in str(bound)]

    @cache
    def dp(position: int, total: int, tight: bool) -> int:
        if total > target:
            return 0
        if position == len(digits):
            return int(total == target)
        limit = digits[position] if tight else 9
        return sum(
            dp(position + 1, total + digit, tight and digit == limit)
            for digit in range(limit + 1)
        )

    return dp(0, 0, True)

def count_range(left: int, right: int, target: int) -> int:
    if left < 0 or left > right:
        raise ValueError("expected 0 <= left <= right")
    return count_with_digit_sum(right, target) - count_with_digit_sum(left - 1, target)

assert count_range(1, 20, 2) == 3  # 2, 11, 20

import java.util.Arrays;

public class DigitSumDP {
    private final int[] digits;
    private final int target;
    private final long[][] memo;

    private DigitSumDP(long bound, int target) {
        this.digits = Long.toString(bound).chars().map(ch -> ch - '0').toArray();
        this.target = target;
        this.memo = new long[digits.length][target + 1];
        for (long[] row : memo) Arrays.fill(row, -1L);
    }

    private long solve(int position, int sum, boolean tight) {
        if (sum > target) return 0L;
        if (position == digits.length) return sum == target ? 1L : 0L;
        if (!tight && memo[position][sum] != -1L) return memo[position][sum];
        int limit = tight ? digits[position] : 9;
        long result = 0L;
        for (int digit = 0; digit <= limit; digit++) {
            result = Math.addExact(result,
                solve(position + 1, sum + digit, tight && digit == limit));
        }
        if (!tight) memo[position][sum] = result;
        return result;
    }

    static long countUpTo(long bound, int target) {
        if (bound < 0 || target < 0) return 0L;
        if (target > 9 * Long.toString(bound).length()) return 0L;
        return new DigitSumDP(bound, target).solve(0, 0, true);
    }

    static long countRange(long left, long right, int target) {
        if (left < 0 || left > right) throw new IllegalArgumentException("bad range");
        return Math.subtractExact(countUpTo(right, target), countUpTo(left - 1, target));
    }

    public static void main(String[] args) {
        if (countRange(1, 20, 2) != 3L) throw new AssertionError();
    }
}