リンク1は間違えたコード。 この問題のポイントは、部分最適が全体最適にならないところ。 4 1 5 3 2 1 という例を考える。部分最適にするなら (1 + 1) + 3 + 2 + 1 = 8 となる。 全体最適にするなら 1 * 4 + 1 * 3 = 7 となる。 1を4つ作って3回魔法を使う…