SRM150 DIV1 500(DP)

色んな色のストライプが与えられて、上塗りを許可したときに最小何回の動作で塗れるかという問題。考え方は、ある区間を何色で塗ったら最小何回だったという情報を持たせてDP or メモ化探索。

• 左端が塗ってる同じ色だったら[l+1,r,color]で再帰
• 右端が塗ってる色と同じだったら[l,r-1,color]で再帰
• 左端が塗ってる色と違ったら、正しい左端の色で[l,i,本当のcolor],[i+1,r,塗っているcolor]で再帰して返値に+1

todo: 今度ボトムアップに書き換えてみる。