数位 DP：按位构造的计数艺术

// 模板：统计 [0, n] 中满足条件的数的个数
public int countNumbers(int n) {
    char[] digits = String.valueOf(n).toCharArray();
    int len = digits.length;
    int[][] memo = new int[len][/* 状态维度 */];
    for (int[] row : memo) Arrays.fill(row, -1);

    return dfs(digits, 0, /* 初始状态 */, true, memo);
}

// pos: 当前处理到第几位
// state: 题目相关状态（如前一位数字、数字和等）
// tight: 是否受上限约束
int dfs(char[] digits, int pos, int state, boolean tight, int[][] memo) {
    if (pos == digits.length) return 1; // 成功构造一个数

    if (!tight && memo[pos][state] != -1) return memo[pos][state];

    int limit = tight ? digits[pos] - '0' : 9;
    int count = 0;

    for (int d = 0; d <= limit; d++) {
        // 剪枝：跳过不合法的数字
        if (!isValid(d, state)) continue;

        int nextState = transition(state, d);
        count += dfs(digits, pos + 1, nextState, tight && (d == limit), memo);
    }

    if (!tight) memo[pos][state] = count;
    return count;
}

// 统计 [1, n] 中不含数字 4 的正整数个数
public int countWithout4(int n) {
    char[] digits = String.valueOf(n).toCharArray();
    int[][] memo = new int[digits.length][1];
    for (int[] row : memo) Arrays.fill(row, -1);
    return dfs(digits, 0, true, memo) - 1; // 减去 0
}

int dfs(char[] digits, int pos, boolean tight, int[][] memo) {
    if (pos == digits.length) return 1;
    if (!tight && memo[pos][0] != -1) return memo[pos][0];

    int limit = tight ? digits[pos] - '0' : 9;
    int count = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == 4) continue; // 跳过 4
        count += dfs(digits, pos + 1, tight && (d == limit), memo);
    }
    if (!tight) memo[pos][0] = count;
    return count;
}

// 状态：pos + 剩余需要的数字和
int dfs(char[] digits, int pos, int remain, boolean tight, int[][] memo) {
    if (pos == digits.length) return remain == 0 ? 1 : 0;
    if (remain < 0) return 0;
    if (!tight && memo[pos][remain] != -1) return memo[pos][remain];

    int limit = tight ? digits[pos] - '0' : 9;
    int count = 0;
    for (int d = 0; d <= limit; d++) {
        count += dfs(digits, pos + 1, remain - d, tight && (d == limit), memo);
    }
    if (!tight) memo[pos][remain] = count;
    return count;
}

// 状态：pos + 前一位数字（0-9, 10表示首位）
int dfs(char[] digits, int pos, int prev, boolean tight, int[][] memo) {
    if (pos == digits.length) return 1;
    if (!tight && memo[pos][prev] != -1) return memo[pos][prev];

    int limit = tight ? digits[pos] - '0' : 9;
    int count = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == prev) continue; // 相邻不重复
        count += dfs(digits, pos + 1, d, tight && (d == limit), memo);
    }
    if (!tight) memo[pos][prev] = count;
    return count;
}

int answer = count(R) - count(L - 1);