動的計画法の勉強 - プログラミング勉強日記

動的計画法がよく分からないので、お勉強しました。
Haskellで書いてます。

コードです。

main = do
    _ <- getLine
    sushi <- getLine
    let sushiList = map read (words sushi) :: [Int]
    let dpt = dp sushiList
    putStrLn $ show $ head dpt

-- DP table create
dp :: [Int] -> [Int]
dp dt = foldl (\(d1:d2:dx) x -> (max d1 (d2 + x)):d1:d2:dx) [0,0] dt

動的計画法を使って解きました。
正解のようですけど、これ本当にあってるのか不安になりました。

漸化式がこれでいいのか確かめてみます。

===============================================

X_n : n番目のお寿司
M_n : n番目のお寿司を取った、もしくは取らなかったときの、最大累計美味しさポイント

まず、M_nを考えてみます。
X_nを取る、取らないの2パターンが考えられます。

取るとき : 1個前のお寿司は取れない。
取らないとき : 1個前のお寿司を取っても良い。

まず、X_nを取ったときのパターンを考えます。
X_nを取ったときは、X_n-1を取っていません。
ということは、1個前のお寿司が流れてきたときには美味しさポイントが増えてないということです。
つまり、M_n-2 >= M_n-1
ということは、X_nを取ったときの M_nは、X_n + M_n-2と言えそうですね。

次に、X_nを取らなかったときのパターンを考えます。
お寿司を取らなかったということは、1個前のお寿司が流れてきたときと美味しさポイントが変わっていないということです。
なので、X_nを取らなかったときのM_nは、X_n-1と言えそうですね。

ここで、
M_n = X_n + M_n-2
M_n = X_n-1
の、2パターンの式が出ました。
求めたいのは、最大のM_nなので、

M_n = max(X_n + M_n-2, M_n-1)

ということになります。

===============================================

こんな感じでしょうか。
正確に証明できていないような気がします。
あと、Haskellの書き方ももっと良い方法がありそうな気がします。

コメントなどで指摘してもらえると、嬉しいです。