digits[0] = 6  (个位)
digits[1] = 5  (十位)
digits[2] = 4  (百位)
digits[3] = 3  (千位)

dp[pos][state][tight]

int dp[10][2]; // dp[pos][tight]，-1表示未计算

int digits[10]; // 存储上限数字的每一位，digits[0]是最低位（个位）
int len = 0;
while (x) {
    digits[len++] = x % 10;
    x /= 10;
}
// 此时 digits 是倒序存放的，比如 x=1234，得到 digits[0]=4,digits[1]=3,digits[2]=2,digits[3]=1
// 递归时我们从 len-1 开始（最高位）

int dfs(int pos, bool tight) {
    if (pos == -1) return 1; // 所有位都处理完，说明得到了一个有效数字，返回1
    // 如果当前状态已经算过，直接返回（仅当 tight=false 时才能用记忆，因为 tight=true 的结果只出现一次）
    if (!tight && dp[pos][0] != -1) return dp[pos][0];
    
    int limit = tight ? digits[pos] : 9; // 当前位能填的最大值
    int ans = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == 5) continue; // 跳过数字5
        ans += dfs(pos-1, tight && (d == limit)); // 如果当前位填了上限值，且之前也tight，则继续tight
    }
    // 记忆化：只有不受限的情况才存，因为受限的情况每次上限不同
    if (!tight) dp[pos][0] = ans;
    return ans;
}

int count(int x) {
    if (x < 0) return 0;
    // 拆位（前面已写）
    memset(dp, -1, sizeof dp); // 重置记忆化数组
    return dfs(len-1, true);
}
int main() {
    int L = 1, R = 1000;
    cout << count(R) - count(L-1) << endl; // 区间内个数 = 1~R的个数 - 1~(L-1)的个数
    return 0;
}

#include <iostream>
#include <cstring>
using namespace std;

int dp[10][2];   // dp[pos][tight]，-1表示未计算
int digits[10];  // 存储上限数字的每一位，digits[0]存放个位

// 深度优先搜索：pos是当前处理的位置（从高位到低位，如len-1到0），tight表示前面是否完全等于上限
int dfs(int pos, bool tight) {
    if (pos == -1) return 1; // 所有位都处理完，得到一个有效数，计数1
    // 记忆化：如果 tight=false 并且已经算过，直接返回
    if (!tight && dp[pos][0] != -1) return dp[pos][0];
    
    int limit = tight ? digits[pos] : 9; // 当前位可以填的最大数字
    int ans = 0;
    for (int d = 0; d <= limit; d++) {
        if (d == 5) continue; // 不能包含数字5，跳过
        // 继续递归下一位：新tight = 原tight && (当前位d是否等于limit)
        ans += dfs(pos - 1, tight && (d == limit));
    }
    // 记录记忆化：只记录不受限的情况
    if (!tight) dp[pos][0] = ans;
    return ans;
}

// 计算 1~x 中符合条件的数字个数（x可以是0）
int count(int x) {
    if (x < 0) return 0;
    int len = 0;
    // 将x的每一位存入digits，注意个位在索引0
    while (x) {
        digits[len++] = x % 10;
        x /= 10;
    }
    memset(dp, -1, sizeof dp); // 每次重新计算前清空记忆化数组
    return dfs(len - 1, true);
}

int main() {
    // 测试区间 [1, 1000]
    int L = 1, R = 1000;
    int result = count(R) - count(L - 1);
    cout << "区间[" << L << "," << R << "]中不含5的数字个数: " << result << endl;
    
    // 另外测试几个区间
    cout << "1~10中不含5的个数: " << count(10) - count(0) << endl;   // 10个数中只有5被排除，应输出9
    cout << "1~100中不含5的个数: " << count(100) - count(0) << endl; // 每10个中有一个5，90个？实际81个（因为每10个中有一个5，但50-59有10个含5，所以一共19个含5，100-19=81）
    return 0;
}

区间[1,1000]中不含5的数字个数: 729
1~10中不含5的个数: 9
1~100中不含5的个数: 81