桁 DP

これはステージング環境です。5 秒後に自動的に本番環境 (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /tenkei/keta-dp#noredirect を利用してください。
このページは下書きです。5 秒後に自動的にトップページ (https://dic.kimiyuki.net) にリダイレクトされます。リダイレクトを抑止したい場合は #noredirect を付けた URL /tenkei/keta-dp#noredirect を利用してください。
name
桁 DP
short description
桁 DP とは、自然数の \(10\) 進数展開などを桁ごとに決定していくような DP のこと。状態の持ちかたによる DP の分類のひとつ。

桁 DP とは、自然数の (10) 進数展開などを桁ごとに決定していくような DP のこと。おそらくは状態の持ちかたによる DP の分類のひとつ。

特に「自然数 $n \lt L$ であって条件 $\varphi(n)$ を満たすものの個数を求めよ」のような形式の問題の際によく現れる。 このときは「現時点までずっと $L$ と一致している」場合の (あるひとつの) 値と「もう $L$ より真に小さいことが確定した」場合の値たちとを管理すればよい。

例題

厳密な定義について

厳密な定義はかなり揺れる。構成途中の文字列を状態とする DP や、数字列 (あるいは記号の種類数が少ない文字列) 上のオートマトン DP と理解されることもある。 「境界となる自然数 $N より小さくなることが確定したか」のフラグを状態とする DP だと言う人もいる。