倒霉倒霉倒霉

离结束四十多分钟的时候就写完最后一题的数位 $dp$了，但是忘记清空记忆化数组。。。

我一直以为我 $dp$ 写丑了，就没想过是没清空。。。

贴一下这题的代码，其实非常板，和 hdoj 2089 几乎没有区别，只不过航电oj的这题不用特地判断前导0。

6957. 统计范围内的步进数字数目

class Solution {
public:
    int f[105][10][10][2], a[2000];
    const int mod = 1e9 + 7;
    int dfs(int pos, int lim, int last, int zero)
    {
        if (pos == 0) return 1;
        if (f[pos][lim][last][zero] != -1) return f[pos][lim][last][zero];
        f[pos][lim][last][zero] = 0;
        int k;
        if (lim) k = a[pos];
        else k = 9;
        for (int i = 0; i <= k; i++)
        {
            if (abs(i - last) != 1 && zero == 0) continue;
            (f[pos][lim][last][zero] += dfs(pos - 1, lim & (i == k), i, zero & (i == 0))) %= mod;
        }
        return f[pos][lim][last][zero];
    }
    int calc(string x)
    {
        memset(f, -1, sizeof(f));
        int cnt = 0;
        int n = x.size();
        for (int i = n - 1; i >= 0; i--) {
            a[++cnt] = x[i] - '0';
        }
        return dfs(cnt, 1, 0, 1);
    }
    int countSteppingNumbers(string low, string high) {
        int ans = (calc(high) - calc(low)) % mod;
        int n = low.size();
        bool ok = 1;
        for (int i = 0; i + 1 < n; i++) {
            if (abs(low[i] - low[i + 1]) != 1) {
                ok = 0;
                break;
            }
        }
        return ((ans + ok) % mod + mod) % mod;
    }
};