超簡単な実例から桁DPを学ぶ

#想定する読者

　桁DPの解説を読んだけどよくわからんという人

#桁DP（動的計画法）とは

　「ある数K以下に含まれる～な数を求めよ」という時に使われる手法で、先頭の桁から、あり得る数字を列挙していくもの。実装がやや複雑だが、数字を文字列として扱えるため巨大な数などに対応しやすい。

#簡単な例1：数え上げ

**Q：456以下の整数に含まれる1以上の整数の数を述べよ**

　**456であることは0.1秒でわかりますが**、あえてこれを桁DPで求めます。
　まず1桁目にとれる数は0～4の5種類です。1や2から始まる3桁の数字が456以下であることは自明なので、こいつらは次の桁も0～9の10種類を自由にとれます。3桁目も同様です。

　しかし4から始まる数字だと、460とかは取れないので、そこは制限がある訳です。

　まとめると、

- 4未満の数字で始まる数字4種類 -> やりたい放題
- 4から始まるが、次は5未満の数字から始まる数字5種類 -> やりたい放題
- 45から始まる数字 -> 0～6の7種類

　ということになります。$4*100+50*10+7 = 457$という計算結果がでますが、これは「000」を含むので、1を引いて456が最終的な答えです。

　図でまとめるとこんな感じです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/1851b357-5841-841f-458b-49ccca055af3.png)

　これをdpとして表にまとめる方法を考えます。今の桁にどれぐらいの候補があるか、とは別に、

- 自由に動ける余裕があるか？
- 自由に動ける余裕がないか？

　という情報を配列に持たせる必要があります。
　遷移の様子を示すと下表のようになります。（iは桁数）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/f9082b6f-163f-6074-4c92-bdfd9175f20d.png)

##例1の実装

　c++で実装します。

```c++
int main(){
  int k;
  cin >> k;
  vector<int> digit = {0,4,5,6}; //上限の指定
  int dp[4][2] = {0};//2つ目の[2]は「余裕があるかないか」の判定
  dp[0][1] = 0;
  dp[0][0] = 1;//0桁目の0は余裕がない組
  rep(i,3){
    //余裕ある組
    rep(j,10) dp[i+1][1] += dp[i][1];
    //余裕ない組
    rep(j,digit[i+1]) dp[i+1][1] += dp[i][0];
    dp[i+1][0] += dp[i][0];
  }
  cout << dp[3][1] + dp[3][0] - 1 << endl;//出力456
}
```

　`i`は今の桁、`j`は次の桁の候補としてあげる数を示しています。余裕がある組は`rep(j,10)`まで回せますが、そうでない組は`rep(j,digit[i+1])`までしか回せないことがミソです。

#簡単な例2：3を含む数

**Q：999以下の整数の中に含まれる、少なくとも1つは3を含む数を求めよ**

　$10^3 -9^3 = 271$が答えであることは3秒でわかりますが、これも桁DPで求めます。

　ある桁に3が出てきた時点で、次の桁に何がこよう構いません。組み合わせを考えると、

- 3から始まる数字1種類 -> やりたい放題
- 3じゃない数字から始まるが、次の桁は3から始まる数字9種類 -> やりたい放題
- 3じゃない数字が2つ続いたもの81種類 -> 最後に3をあてるしかない

　ということになります。$100+9*10+81 = 271$が答えです。

　図で整理します。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/4cec94ea-db8d-14d4-b2e6-c628c4b62b53.png)

　dpの表は以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/970751bd-fd22-bff1-ca3f-535432560d52.png)

##例2の実装

　上限を999にしたのは、例1のような上限の処理が必要ないからです。そのため、dpの次元数は、桁数と「3を含むかどうか？」の2次元で済みます。

```c++

int main(){
  int k;
  cin >> k;
  int dp[4][2] = {0};//2つ目の[2]は「3を含むかどうか」の判定
  dp[0][1] = 0;
  dp[0][0] = 1;//0桁目の0は3を含んでいない
  rep(i,3){
    //3を含んでいる組
    rep(j,10) dp[i+1][1] += dp[i][1];
    //3を含んでいない組
    rep(j,10){
      if(j==3) dp[i+1][1] += dp[i][0];
      if(j!=3) dp[i+1][0] += dp[i][0];
    }
  }
  cout << dp[3][1] << endl;//出力271
}
```

#応用例：上記2つの組み合わせ

**Q：123以下の整数の中で、少なくとも1つは3があるものの数を求めよ**

　いよいよ本番です。今回は**「余裕があるかどうか」**と**「3を含むかどうか」**の2つの条件を気にする必要があるので、dpの次元数は3になります。3次元！　この3次元の遷移をうまくイメージできるかどうかが、桁DPに親しむことができるかの試金石ではないでしょうか。

　しかし、「余裕があるかどうか」と「3を含むかどうか」は、それぞれTRUE/FALSEを総当たりしても4通りです。ここは地道に考えていきます。

###余裕もないし3も含んでいない

　ゴミです。一番どうしようもないやつです。次の桁のループは上限までしか回せません。うまく上限未満の数を引き当てるか、または3を引き当てるかして、抜け出さなくてはいけません。

###余裕はないが3を含んでいる

　生産力はないですが血筋は高貴です。次の桁のループは上限までしか回せませんが、生まれてくる子供はすべて3を含んでいるグループになります。

###余裕はあるけど3を含んでいない

　生産力はあるタイプです。もう二度と余裕を失うことはありませんし、うまく子供が3を引き当てれば、その子は3を含むグループの仲間入りです。数うちゃあたるタイプですね。

###余裕もあるし3も含んでいる

　エリートです。余裕を失うこともないし、3を含むグループから脱落することもありません。自由に子供を作ってもらってもらいましょう。子供もすべて同じくエリートです。

　図にすると以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/e7dee7e9-4ab8-3bde-b4d7-16ffd9ab8ab7.png)

　表にすると以下のようになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/288125/77684102-5836-fbd8-655b-2c81993bdd0f.png)

##応用例の実装

　今度はdpの次元数が3になります。それに合わせてループが複雑になりますが、上の$2*2=4$通りの組み合わせを落ち着いて列挙していけば大丈夫です。

```c++

int main(){
  vector<int> digit = {0,1,2,3};//上限の指定
  int dp[4][2][2] = {0};//条件が2つあるので計3次元
  dp[0][0][0] = 1;//余裕がなくて3を含んでいない、ゴミ
  dp[0][0][1] = 0;//余裕がないが3を含んでいる
  dp[0][1][0] = 0;//余裕はあるが3を含んでいない
  dp[0][1][1] = 0;//余裕もあるし3も含んでいる、エリート
  
  rep(i,3){
    //余裕もないし3も含んでいない
    rep(j,digit[i+1]){
      if(j == 3) dp[i+1][1][1] += dp[i][0][0];
      if(j != 3) dp[i+1][1][0] += dp[i][0][0];
    }
    if(digit[i+1] == 3) dp[i+1][0][1] += dp[i][0][0];
    if(digit[i+1] != 3) dp[i+1][0][0] += dp[i][0][0];
    //余裕はないが3を含んでいる
    rep(j,digit[i+1]) dp[i+1][1][1] += dp[i][0][1];
    dp[i+1][0][1] += dp[i][0][1];  
    //余裕はあるが3は含んでいない
    rep(j,10){
      if(j==3) dp[i+1][1][1] += dp[i][1][0];
      if(j!=3) dp[i+1][1][0] += dp[i][1][0];
    }
    //余裕があって3も含んでいる
    rep(j,10) dp[i+1][1][1] += dp[i][1][1];  
  }
  cout << dp[3][0][1] << dp[3][1][1] << endl;//出力22
}
```

　`rep(j,10)`や`rep(j,digits[i+1])`といったループはひとまとめにできるので、よりコンパクトにまとめたのが次のコードです。上のコードを見ながらだと理解しやすいと思います。

```c++

int main(){
  vector<int> digit = {0,1,2,3};//上限の指定
  int dp[4][2][2] = {0};
  dp[0][0][0] = 1;//余裕がなくて3を含んでいない、ゴミ
  dp[0][0][1] = 0;//余裕がないが3を含んでいる
  dp[0][1][0] = 0;//余裕はあるが3を含んでいない
  dp[0][1][1] = 0;//余裕もあるし3も含んでいる、エリート
  
  rep(i,3){
    //余裕がない組
    rep(j,digit[i+1]){
      dp[i+1][1][1] += dp[i][0][1];
      if(j == 3) dp[i+1][1][1] += dp[i][0][0];
      if(j != 3) dp[i+1][1][0] += dp[i][0][0];
    }
    dp[i+1][0][1] += dp[i][0][1];
    if(digit[i+1] == 3) dp[i+1][0][1] += dp[i][0][0];
    if(digit[i+1] != 3) dp[i+1][0][0] += dp[i][0][0];
    //余裕がある組
    rep(j,10){
      dp[i+1][1][1] += dp[i][1][1];
      if(j == 3) dp[i+1][1][1] += dp[i][1][0];
      if(j != 3) dp[i+1][1][0] += dp[i][1][0];
    }
  }
  
  cout << dp[3][0][1] + dp[3][1][1] << endl;//出力22
}
```

　if条件とdpの0,1が対応させられることを利用して極限までまとめたり、更にループを強引にまとめたりしたものが以下になります。見た目はきれいですが、いきなりこのコードを見せられても意味不明だと思います。超つよつよマンなら直感的に理解できるかもしれませんが……。

```c++
int main(){
  vector<int> digit = {0,1,2,3};
  int dp[4][2][2] = {0};
  dp[0][0][0] = 1;
  dp[0][0][1] = 0;
  dp[0][1][0] = 0;
  dp[0][1][1] = 0;

  rep(i,3){
    rep(j,10){
      dp[i+1][1][1] += dp[i][1][1];
      dp[i+1][1][j==3] += dp[i][1][0];
      dp[i+1][j<digit[i+1]][1] += dp[i][0][1]*(j<digit[i+1]+1);
      dp[i+1][j<digit[i+1]][j==3] += dp[i][0][0]*(j<digit[i+1]+1);
    }
  }
  cout << dp[3][0][1] + dp[3][1][1] << endl;//出力22
}
```

#結論

　桁DPは場合分けを列挙してそれらがどのように増えていくかを総当たりで考えればなんとかなる。

#参考

　参考にさせてもらったページ。
https://qiita.com/pinokions009/items/1e98252718eeeeb5c9ab
https://qiita.com/murai_mart/items/1a7a4d10abc0c3b5b53f