帰納法による O(n) 提案。うーん、今ウィキを読んで、それが動的プログラミングとしてカウントされることがわかりました。実に広い用語です。以前は、動的計画法について別の理解がありました。
用語集
所々にN
コインがあります。N
コインの値はa[i]
です0 <= i < N
。各コインは、 と のシーケンスとして表現される選択または選択解除される可能性が0
あり1
ます。
アルゴリズムの説明
00
問題の制約に違反するため、どの場所でも無効なシーケンスです。111
最適ではないため、無効でもあり、101
常に優れています。
すべての場所i
について、3 つのコードの 3 つの最適な合計を順次計算します: 01
、10
、11
. コードは、最後の 2 つのコイン、つまり と の設定から取得されi-1
ますi
。したがって、変数b01
、b02
、に最適な (最小) 合計がありますb11
。
確かなことから始めなければならないので、アルゴリズムを2回適用します。1 つはプレース 0 セットのコイン用で、もう 1 つはセット解除用です。
0
最初に、場所を試して、直接1
開始b
します。b01 = a[1]
, b10 = a[0]
, b11 = a[0] + a[1]
. ただし、これがセット解除する最初のコインを選択するラウンドである場合、ソリューションのみを受け入れることができb01
ます。b10
そのため、とに大きな数を割り当てb11
ます。これらのソリューションは、次のアルゴリズム ステップですぐに削除されます。b01
2 番目のラウンドでは、反対のことを行います。最初のビットを設定する必要があるため、大きな数値を に割り当てます。
ステップで、 s のi
場所に最適な合計が得られます。place の最適な合計である sを計算します。i-1
b
c
i
c01 = b10 + a[i] // 101 (10 -> 01)
c10 = min(b01, b11) // 010 (01 -> 10) or 110 (11 -> 10)
c11 = b01 + a[i] // 011 (01 -> 11)
それは次の可能性から来ています。
010 - b01 -> c10
011 - b01 -> c11
100 - invalid
101 - b10 -> c01
110 - b11 -> c10
111 - invalid
もちろん、最良の合計をb
s に割り当てて各ステップを終了します。
すべてのコインを処理したら、最初の仮定と矛盾するソリューションを削除する必要があります。Bitsi-2
でi-1
あり0
、有効なシーケンスを生成する必要があります。
これは123456
シーケンスの実行例です。
A. 最初のビットを想定0
1 a[1] = 2: b01 = 2, b10 = 999, b11 = 999
2 a[2] = 3: b01 = 1002, b10 = 2, b11 = 5
3 a[3] = 4: b01 = 6, b10 = 9, b11 = 1006
4 a[4] = 5: b01 = 13, b10 = 6, b11 = 11
5 a[5] = 6: b01 = 12, b10 = 13, b11 = 19
b10
b01
は受け入れられないので、とからより適切なものを選択しますb11
。これは 12 です。
B. 最初のビットを想定1
1 a[1] = 2: b01 = 999, b10 = 1, b11 = 3
2 a[2] = 3: b01 = 4, b10 = 3, b11 = 1002
3 a[3] = 4: b01 = 7, b10 = 4, b11 = 8
4 a[4] = 5: b01 = 9, b10 = 12, b11 = 12
5 a[5] = 6: b01 = 18, b10 = 9, b11 = 15
を生成するため、 Nowb11
は無効111
です。ステップ A では 12、ステップ B では 9 が得られました。9 の方が優れていますb01
。b10
これが結果です。
上記は手計算なので、間違っていたらすみません。ただし、最初のコインのセット解除では 2+4+6 を計算し、最初のコインのセットでは結果は 1+3+5 でした。正しいようです。