動的計画法の問題を解決するには、それを繰り返しサブソリューションに分割する必要があります。
問題を A(n, k) として定義するとします。これは、n から k 桁を削除して可能な最大数を返します。
これから単純な再帰アルゴリズムを定義できます。
あなたの例を使用すると、 A(12345, 3) = max { A(2345, 2), A(1345, 2), A(1245, 2), A(1234, 2) }
より一般的には、 A(n, k) = max { A(n から 1 桁を削除、k - 1) }
そして、基本ケースは A(n, 0) = n です。
このアプローチを使用すると、n と k の値をキャッシュするテーブルを作成できます。
int A(int n, int k)
{
typedef std::pair<int, int> input;
static std::map<input, int> cache;
if (k == 0) return n;
input i(n, k);
if (cache.find(i) != cache.end())
return cache[i];
cache[i] = /* ... as above ... */
return cache[i];
}
これは簡単な解決策ですが、非常に小さな 1 次元キャッシュで動作するより良い解決策があります。この質問を次のように言い換えることを検討してください:「文字列 n と整数 k が与えられた場合、長さ k の n で辞書編集的に最大のサブシーケンスを見つける」。これが本質的にあなたの問題であり、解決策ははるかに簡単です。
nの最初のi桁のみを使用して(つまり、最初のi桁からj桁を削除して)、長さ(i - j)の最大の辞書式シーケンスを与える別の関数B(i, j)を定義できるようになりました。 nの)。
あなたの例をもう一度使用すると、次のようになります。
B(1, 0) = 1
B(2, 0) = 12
B(3, 0) = 123
B(3, 1) = 23
B(3, 2) = 3
等
少し考えれば、再帰関係を見つけることができます。
B(i, j) = max( 10B(i-1, j) + n i , B(i-1, j-1) )
または、j = iの場合、B(i, j) = B(i-1, j-1)
およびB(0, 0) = 0
そして、上記と非常によく似た方法でコーディングできます。