ABC #007 D : 禁止された数字

問題リンク : D: 禁止された数字 - AtCoder Beginner Contest 007 | AtCoder

問題概要 :
A以上B以下の整数で４か９を含むものの数を求めよ

解法：
桁DP
dp[桁][ぎりぎりかどうかをboolでもつ] := 総数
間違えて４も９も含まない数字を数え上げてしまったので全体から引いた

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

typedef long long ll;

ll dp[30][2]; // dp[桁][ぎりぎりか]
int digit[] = {0,1,2,3,5,6,7,8};

ll compute(string s,ll lls){
  rep(i,30) rep(j,2) dp[i][j] = 0;
  dp[0][1] = 1LL;
  rep(i,s.size()){
    rep(j,2){
      if( dp[i][j] == 0LL ) continue;
      rep(k,8){
        if( j && s[i]-'0' < digit[k] ) continue;
        bool nj = j;
        if( j && s[i]-'0' > digit[k] ) nj = false;
        dp[i+1][nj] += dp[i][j];
      }
    }
  }
  return lls - ( dp[s.size()][0] + dp[s.size()][1] - 1LL );
}

string lltos(ll i) { stringstream ss; ss << i; return ss.str(); } 

int main(){
  ll llA,llB;
  cin >> llA >> llB;
  --llA;
  string A = lltos(llA), B = lltos(llB);
  cout << compute(B,llB) - compute(A,llA) << endl;
  return 0;
}