動的計画法を利用した問題

Question

上記の問題についてi番目のブロックを開始地点とした時の最小操作回数をdp[i]としてテーブルを作って考えたのですが漸化式が立ちません。　上手い方針があれば教えていただきたいです。

Answer 1

話を簡単にするために、最初から同じ色が連続している部分はないものとすると
dp[i][j] (i <= j) をiからjのブロックが「開始時点のブロックと連結しているブロック」である状態からの最小操作回数とすれば

dp[0][N - 1] = 0
dp[i][j] = if ci-1 == cj+1 => dp[i - 1][j + 1] + 1
           otherwise => min(dp[i - 1][j] + 1, dp[i][j + 1] + 1)

ざっくりとこんな感じで漸化式がたてられます。そして最初にi番目のブロックを選ぶ場合の最小操作回数はdp[i][i]になります。

Comments

[saikao]

回答ありがとうございます。無事実装できました。