Rubyで動的計画法を解いてみた
動的計画法の基本問題を Ruby で解いてみました。
Ruby で解いている記事がそれほど多くなかったので記録として残しておきます。
導入
解いた問題は以下の問題です。
公式の DP の問題集の最初の問題ですね。この問題から DP を始めた方も多いのではないでしょうか。
解答
まずは自分の解答から載せておきます。
N=gets.to_i
h=gets.split.map(&:to_i)
if N==2
puts (h[0]-h[1]).abs
exit
end
dp=[0,(h[1]-h[0]).abs]
2.upto(N-1){|n|
if dp[n-1]+(h[n]-h[n-1]).abs >= dp[n-2]+(h[n]-h[n-2]).abs
dp[n]=dp[n-2]+(h[n]-h[n-2]).abs
else
dp[n]=dp[n-1]+(h[n]-h[n-1]).abs
end
}
puts dp[N-1]dp[n] は n 回ジャンプした時のコストの最小値です。
dp[0]はジャンプしていない状態を表すので 0になります。dp[1]は 2 つ前の足場が存在しないので(h[1]-h[0]).absとなります。
よって初期条件として以下の値が入っていきます。
dp=[0,(h[1]-h[0]).abs]そして重要になるのは以下のコード
2.upto(N-1){|n|
if dp[n-1]+(h[n]-h[n-1]).abs >= dp[n-2]+(h[n]-h[n-2]).abs
dp[n]=dp[n-2]+(h[n]-h[n-2]).abs
else
dp[n]=dp[n-1]+(h[n]-h[n-1]).abs
end
}この時比較しているのは
「1 つ前の着地点までのコストの最小値と 1 つ前の着地点と現在の着地点の差」の和
と
「2 つ前の着地点までのコストの最小値と 2 つ前の着地点と現在の着地点の差」の和
になります。
比較した結果小さいものがdp[n]となります。
これを繰り返すことによって目標地点までのコストの最小値を求めることができます。
感想
Atcorder 初心者ですが、先人たちの知恵を借りてなんとか解くことができました。
以下参考にした記事になります。