Zigzag (AOJ 1294)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1294

問題

図のように折れ線でn個の点を結んでいく。ただし、途中の線分には2つ以上の点が乗っていなければならない。折れ曲がり回数の最小値とその時の線分の長さの合計の最小値を求めよ。
n<=10

解法

すでに通った点と直前の線分を作る際に使った点を2つ使ってメモ化再帰をしたら解ける。UVa Live Archiveだと通らないと思うので、次の状態への移行を計算する部分でもメモ化を使って高速化すれば良い。
メモ化が1重の場合の計算量は係数項が大きめのO(n^5*2^n)、2重にメモ化するとO(n^4*2^n)になる。