【DP】動的計画法をRubyで学ぶ

はじめに

競技プログラミング的なものに少し手を付け始めている中、解けそうで解きにくい（工夫orゴリ押しでなんとか解けるような）カテゴリーの問題があった。どうやら、そいつはDPというアルゴリズムを用いると解きやすいようで、競プロ初心者がブチ当たる壁でもあるらしい。調べてみると難しそうなのと、Rubyを用いた参考例があまり見当たらないので、本記事にアウトプットしながら少しずつ理解を深めていく。

DPとは

動的計画法（Dynamic Programming）

対象となる問題を複数の部分問題に分割し、部分問題の計算結果の記録を利用して全体の問題を解く手法を総称してこう呼ぶ。

動的計画法（Dynamic Programming）は、複雑な問題をよりシンプルな部分問題に分割し、それぞれの部分問題の解を再利用することで全体の解を求めるアルゴリズムです。

動的計画法は、再帰呼び出しやループを使って、問題を小さな部分問題に分解します。また、部分問題の解をメモしておくことで、同じ部分問題が複数回計算されることを避けることができます。

メモ化再帰（Memoization）は、再帰的なアルゴリズムを使って動的計画法を実装する方法の一つです。メモ化再帰では、再帰呼び出しの結果をメモしておき、同じ引数での再帰呼び出しの結果を再計算せずに再利用します。

ふむふむ。つまり↓

• 問題を小さな部分問題に分割し、それらを解決することで元の問題を解決する
• 部分問題の結果を保存（メモ化）することで、同じ計算を繰り返すことを避け、効率的に解を求めることが出来る手法

DP でフィボナッチ数を求める

フィボナッチ数列とは

フィボナッチ数列は、直前の2つの項の数を足したものが次の項の数になる数列です。

2つの実装コードを比較

メモ化再帰 ver

def fibonacci(n, memo = {})
  return n if n <= 1
  return memo[n] if memo.key?(n)
  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
  # p memo # {2=>1, 3=>2, 4=>3, 5=>5, 6=>8, 7=>13, 8=>21, 9=>34, 10=>55}

  memo[n]
end

p fibonacci(10) # 55

メモ化再帰では、計算した結果をハッシュに保存することで、同じ引数 n に対する再計算を避けている。これにより、計算効率が向上している。

引数 n が非常に大きい場合には、計算済みの結果を保持するためのハッシュが増えるため、多くのメモリを消費する可能性がある。
※ただし、一般的なプログラムで問題になるほどの量ではない。

反復アプローチ ver

def fibonacci(n)
  return n if n <= 1

  prev2 = 0
  prev1 = 1

  (n - 1).times do
    val = prev1 + prev2
    prev2 = prev1
    prev1 = val
  end

  prev1
end

p fibonacci(10) # 55

反復的なアプローチでは、直前の2つのフィボナッチ数の和を計算している。
必要最低限の変数だけで計算を行っているため、メモ化再帰よりもメモリ使用量が少ない。

実際に問題を解いてみる

やはり、もっと色々と実装しないとイメージが湧きにくいので、問題を解きます。
今回はPaizaのレベルアップ問題集 > DPメニュー > 問題一覧　Ruby編から、幾つか問題をピックアップしました。

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

とあるので、解答コード（仮）を公開します。

※以降の記事は、まだ解いていない方にはネタバレになってしまうので、先に解きたい方は上記のリンク先から問題を選択し、解いてみてください。

問題＆解答コード（仮）

2項間漸化式①

https://paiza.jp/works/mondai/dp_primer/dp_primer_recursive_formula_step0

整数 x, d, k が与えられます。
次のように定められた数列の k 項目の値を出力してください。

・ a_1 = x
・ a_n = a_{n-1} + d (n ≧ 2)

$a_k = x + (k - 1) \times d$
という式を使えば求めることが出来ますが、問題にもある通りDPで求めてみます。

x, d, k = gets.split.map(&:to_i) # 0, 7, 9

a = [x]

(1...k).each do |i| # 1, 2, 3, 4, 5, 6, 7, 8
  a[i] = a[i - 1] + d
end

# p a # [0, 7, 14, 21, 28, 35, 42, 49, 56]

p a[k - 1] # 56

DPを考える際には、まず漸化式を考えるとよいです。
漸化式は、数列の各項をその前の項を用いて記述した式です。

漸化式（ぜんかしき）とは

2項間漸化式②

https://paiza.jp/works/mondai/dp_primer/dp_primer_recursive_formula_step1

整数 x, d, Q と Q 個の整数 k_1, k_2, ... , k_Q が与えられます。
次のように定められた数列の k_i 項目の値を順に出力してください。

・ a_1 = x
・ a_n = a_{n-1} + d (n ≧ 2)

こちらも解いてみます。

x, d = gets.split.map(&:to_i) # 0, 7

q = gets.to_i # 5
arr = q.times.map { gets.to_i } # [1, 2, 3, 4, 5]

# DP用のハッシュを初期化
dp = {1 => x}

arr.each do |k|
  (2..k).each do |i|
    dp[i] = dp[i - 1] + d unless dp.key?(i)
  end
    
  p dp[k]
end

# p dp # {1=>0, 2=>7, 3=>14, 4=>21, 5=>28}

階段の上り方

https://paiza.jp/works/mondai/dp_primer/dp_primer_stairs_step0

整数 n が与えられます。
階段を上るのに、1 歩で 1 段または 2 段を上ることができるとき、n 段の階段を上る方法は何通りあるでしょうか。

ヒントに記載のあるコードを参考に、DPで実装。

def ways_to_climb_stairs(n)
  # DP配列の初期化
  dp = Array.new(n + 1, 0) # [0, 0, 0, 0]

  # 0段の階段を上る方法が1通り (何もしない)
  dp[0] = 1

  # p dp # [1, 0, 0, 0]

  (1..n).each do |i| # 1, 2, 3
    dp[i] += dp[i - 1] if i >= 1  # i-1 段目から1段上って i 段へ到達
    dp[i] += dp[i - 2] if i >= 2  # i-2 段目から2段上って i 段へ到達
  end

  # p dp # [1, 1, 2, 3]

  dp[n] # n段の階段を上る方法の数
end

n = gets.to_i # 3

p ways_to_climb_stairs(n) # 3

最安値を求める

https://paiza.jp/works/mondai/dp_primer/dp_primer_apples_step0

八百屋にて、りんご1個が a 円で、りんご2個が b 円で売られています。

りんごの買い方を工夫したとき、n 個のりんごを手に入れるために必要な金額の最小値はいくらでしょうか。なお、買い方を工夫した結果、買ったりんごが n+1 個以上になってもよいものとします。

疑似コードに従い、DPで実装。

def min_cost_to_buy_apples(n, a, b)
  dp = Array.new(n + 1, 0) # [0, 0, 0, 0, 0, 0]
  dp[1] = a if n >= 1 # [0, 100, 0, 0, 0, 0]

  (2..n).each do |i|
    dp[i] = [dp[i - 1] + a, dp[i - 2] + b].min
  end

  # p dp # [0, 100, 150, 250, 300, 400]

  dp[n]
end

n, a, b = gets.split.map(&:to_i) # 5, 100, 150

p min_cost_to_buy_apples(n, a, b) # 400

最長増加連続部分列

https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_continuous_step0

n 人が横一列に並んでいます。左から i 番目の人を人 i と呼ぶことにします。人 i の身長は a_i [cm]です。
人 l ,人 l+1, ... , 人 r からなる区間 [l, r] について、すべての l ≦ i < r に対して a_i ≦ a_{i+1} が成り立っているとき、区間 [l, r] は背の順であると呼ぶことにします。また、区間 [l, r] の長さを r-l+1 とします。
背の順であるような区間のうち、最長であるものの長さを出力してください。

疑似コードを参考に、DPで実装。

n = gets.to_i # 5
heights = n.times.map { gets.to_i } # [160, 178, 170, 190, 190]

dp = Array.new(n, 1) # [1, 1, 1, 1, 1]

(1...n).each do |i| # 1, 2, 3, 4
  if heights[i - 1] <= heights[i]
    dp[i] = dp[i - 1] + 1
  else
    dp[i] = 1
  end
end

# p dp # [1, 2, 1, 2, 3]

p dp.max # 3

最長部分増加列(Longest Increasing Subsequence)

https://paiza.jp/works/mondai/dp_primer/dp_primer_lis_step0

n 本の木が横一列に並んでいます。左から i 番目の木を木 i と呼ぶことにします。木 i の高さは a_i [cm] です。
あなたは、何本かの木を伐採することによって、残った木を左から順に見ると高さが単調増加になっているようにしたいと考えています。つまり、残った木を左から 木 k_1, 木 k_2, ... , 木 k_m とすると、a_{k_1} < a_{k_2} < ... < a_{k_m} が満たされているようにしたいです。なるべく多くの木が残るように、伐採する木を工夫して選んだとき、伐採されずに残る木の本数が最大でいくつになるか求めてください。
なお、最初から n 本の木が単調増加に並んでいる場合は、1本も伐採しなくてよいものとします。

疑似コードを参考に、DPで実装。

def max_increasing_subsequence(n, heights)
  # DP配列の初期化
  dp = Array.new(n, 1) # [1, 1, 1, 1, 1]

  (1...n).each do |i| # 1, 2, 3, 4
    (0...i).each do |j| # 0 -> 0 1 -> 0 1 2 -> 0 1 2 3
      if heights[j] < heights[i]
        dp[i] = [dp[i], dp[j] + 1].max # 最後が木 j であるような増加部分列の末尾に木 i をくっつける
      end
    end

    # p dp
    # i = 1 の時: [1, 2, 1, 1, 1]
    # i = 2 の時: [1, 2, 2, 1, 1]
    # i = 3 の時: [1, 2, 2, 1, 1]
    # i = 4 の時: [1, 2, 2, 1, 3]
  end

  # p dp # [1, 2, 2, 1, 3]

  dp.max
end

n = gets.to_i # 5
heights = n.times.map { gets.to_i } # [100, 102, 101 ,91 ,199]

p max_increasing_subsequence(n, heights) # 3

部分和問題

https://paiza.jp/works/mondai/dp_primer/dp_primer_partial_sums_step0

1 ~ n の番号がついた n 個のおもりがあり、おもり i の重さは a_i です。
おもりを何個か選んで重さの和が x となるようにすることができるかどうか判定してください。なお、同じおもりを2個以上選ぶことはできません。

疑似コードを参考に、DPで実装。

def sum_to_x(n, x, weights)
  # DP配列の初期化
  dp = Array.new(x + 1, false) # [false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false]
  dp[0] = true  # 重さの和が0となる方法は何も選ばない場合のみ

  (1..n).each do |i| # 1, 2, 3, 4, 5
    weight = weights[i - 1] # 7 -> 18 -> 5 -> 4 -> 8
    # 逆向きに更新することで、同じおもりを複数回選ぶことができない条件を満たす
    (x).downto(weight) do |j|
      dp[j] ||= dp[j - weight]
    end

    # p dp
    # i = 1 の時: [true, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false, false]
    # i = 2 の時: [true, false, false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, true, false]
    # i = 3 の時: [true, false, false, false, false, true, false, true, false, false, false, false, true, false, false, false, false, false, true, false]
    # i = 4 の時: [true, false, false, false, true, true, false, true, false, true, false, true, true, false, false, false, true, false, true, false]
    # i = 5 の時: [true, false, false, false, true, true, false, true, true, true, false, true, true, true, false, true, true, true, true, true]
  end

  # p dp # [true, false, false, false, true, true, false, true, true, true, false, true, true, true, false, true, true, true, true, true]

  dp[x] ? "yes" : "no"
end

n, x = gets.split.map(&:to_i) # 5, 19
weights = n.times.map { gets.to_i } # [7, 18, 5, 4, 8]

puts sum_to_x(n, x, weights) # yes

感想

初見の感想。問題にもよるけど処理が複雑！
ここで競プロから遠ざかる気持ち少し分かるわ〜
様々な問題を解いて慣れていくしかなさそう。ただ、良い意味で考え方が変わってきた。

こういったアルゴリズムを定着させることで、実装する際のアイディアが増えそう。