看到别人写的又双叒叕是千篇一律的题解， 我又双叒叕来提出自己的想法
emm 我也看了y总的视频，大家题解都是学的y总的吧. 不过y总的dp并不是最优的
这里提供一种一维dp[] 的思路
初始条件 dp[0] = 1, dp[1] = 9;
(dp[0] 属于边界问题, dp[1] 就是只有1位的时候， 就是9个 [0, 9] 除去 4)
直接令 dp[i] 表示 前i 位任意选择的符合的个数

那么dp[i] 就等于考虑第i 位的选择 然后由i - 1 更新过来
考虑第 i 位的选择

• 如果是 4 那么就不用更新

• 如果不是4 同时不是 6 就 等于 dp[i - 1]

• 如果是 6 那么就等于 dp[i - 1] - dp[i - 2] （相当于这一位是 6 然后下一位随便选的个数， 减去下一位是2的个数）

结合上述考虑得到

dp[i] = dp[i - 1] * 9 - dp[i - 2];

这不比 y 总的 dp 简单吗？？？

之后只需要按照 y 总的 数位dp的思想去 递推求解即可!

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int maxn = 20;
int dp[maxn];
void init() {
    // 考虑边界会用到 dp[0] 就比如 62 dp[2] 会用到 dp[0] 这个时候减去的值就是1 所以dp[0] 需要是 1
    dp[0] = 1;
    // [0, 9] 不包括4
    dp[1] = 9;
    for (int i = 2; i <= 12; ++i) {
        dp[i] = dp[i - 1] * 9 - dp[i - 2];
    }
}
int get(int x) {
    if (!x) return 1;
    vector <int> v;
    while (x) v.push_back(x % 10), x /= 10;
    int res, last;
    res = last = 0;
    for (int i = v.size() - 1; i >= 0; --i) {
        int z = v[i];
        for (int j = 0; j < z; ++j) {
            if (j == 4) continue;
            if (last == 6 && j == 2) continue;
            if (j == 6) {
                if (!i) res++;
                else res += dp[i] - dp[i - 1];
            } else res += dp[i];
        }
        if (z == 4) break;
        if (last == 6 && z == 2) break;
        last = z;
        if (!i)  res++;
    }
    return res;
}
int main() {
    init();
    int l, r;
    while (cin >> l >> r, l + r) {
        cout << get(r) - get(l - 1) << endl;
    }
    return 0;
}