Rubyで動的計画法を解いてみた

2022年 03月 18日#Atcorder

動的計画法の基本問題を Ruby で解いてみました。

Ruby で解いている記事がそれほど多くなかったので記録として残しておきます。

導入

解いた問題は以下の問題です。

公式の DP の問題集の最初の問題ですね。この問題から DP を始めた方も多いのではないでしょうか。

Editorial - AtCoder Beginner Contest 243

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

https://atcoder.jp/contests/abc243/editorial/3542

解答

まずは自分の解答から載せておきます。

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 初心者ですが、先人たちの知恵を借りてなんとか解くことができました。

以下参考にした記事になります。

https://qiita.com/drken/items/fd4e5e3630d0f5859067