数え上げ系の DP について説明する。 この記事は DP 初心者を対象にしている。DP やるだけみたいなことを一度でも考えたことがある人は対象にしていない。 例題 次の問題を考えてみよう。 N 桁以下の 3 の倍数はいくつあるか。 N が小さければ全列挙できる。i 桁の数がすべて列挙できていれば、その後ろに 0~9 を付け足せば i+1 桁の数をすべて列挙できることを使う。 dp[i] := leading zero を含めて i 桁のすべての非負整数の集合 #include <iostream> #include <string> #include <vector> using namespace std; int modulo(string s, int mod) { int ret = 0; for (char c : s) ret = (ret * 10 + (c - '0'))
![動的計画法入門(数え上げ) - ペケンペイのブログ](https://cdn-ak-scissors.b.st-hatena.com/image/square/06a15c64ba0ceec233d86d71001ebb29a9dcbf5d/height=288;version=1;width=512/https%3A%2F%2Fcdn.blog.st-hatena.com%2Fimages%2Ftheme%2Fog-image-1500.png)