Digit DP 入門 - torus711 のアレ
はじめに 動的計画法のパターンの一つで，「Digit DP」とか「桁 DP」と呼ばれているものがあります．問題によって異なってくる部分もありますが，問題によらず共通している部分がかなりあるので，その部分を中心に解説してみたいと思います． Digit DP とは？ 「ある整数 以下の非負整数であって，ある条件を満たすものの個数を求めよ」といったタイプの数え上げ問題を解くときにしばしば使われる手法です．Digit DP は，整数の各桁に入る値を 1 桁ずつ決めていくという全探索を DP 化したものです．「ある条件」の部分はとりあえず置いておいて，「 以下の非負整数を数える」というのを例にしてみようと思います．答えは当然 ですが，これを Digit DP で求めることで Digit DP の本質的なアイデアが見えてくると思います．また，求める整数は 10 進表記であるとします． Digit DP
動的計画法入門（数え上げ） - ペケンペイのブログ
数え上げ系の 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'))
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
