貰うDPと配るDPの違い

まとめ

	貰う	配る
考え方	過去を見て今を更新	今を見て未来を更新
更新箇所	1つ	2つ以上
dp 全体の初期化	不要	無限大
前準備	やや面倒なときがある	普通
はみ出がちなのは配列の	前側	後ろ側

具体的なコードの違い

A16 - Dungeon 1 をそれぞれの方法で解く。

まず貰う場合は、

N = gets.to_i                   # => 5
A = gets.split.collect(&:to_i)  # => [2, 4, 1, 3]
B = gets.split.collect(&:to_i)  # => [5, 3, 7]
dp = Array.new(N)               # => [nil, nil, nil, nil, nil]
dp[0], dp[1] = 0, A.first
(2...N).each do |i|
  a = dp[i - 1] + A[i - 1]      # => 6, 6, 8
  b = dp[i - 2] + B[i - 2]      # => 5, 5, 12
  dp[i] = [a, b].min            # => 5, 5, 8
end
p dp[N.pred]                    # => 8

でよいが小細工が入っているので公平に、

• dp の先頭の初期化は dp[0] = 0 のみ
• ループは必ず N 回

とすれば、

貰う

N = gets.to_i                                    # => 5
A = gets.split.collect(&:to_i)                   # => [2, 4, 1, 3]
B = gets.split.collect(&:to_i)                   # => [5, 3, 7]
dp = Array.new(N)                                # => [nil, nil, nil, nil, nil]
dp[0] = 0
N.times do |i|
  a = (i - 1 >= 0) ? dp[i - 1] + A[i - 1] : nil  # => nil, 2, 6, 6, 8
  b = (i - 2 >= 0) ? dp[i - 2] + B[i - 2] : nil  # => nil, nil, 5, 5, 12
  if a || b
    dp[i] = [a, b].compact.min
  end
end
dp                                               # => [0, 2, 5, 5, 8]
p dp[N.pred]                                     # => 8

配る

N = gets.to_i                       # => 5
A = gets.split.collect(&:to_i)      # => [2, 4, 1, 3]
B = gets.split.collect(&:to_i)      # => [5, 3, 7]
dp = Array.new(N, Float::INFINITY)  # => [Infinity, Infinity, Infinity, Infinity, Infinity]
dp[0] = 0
N.times do |i|
  i + 1 < N and dp[i + 1] = [dp[i + 1], dp[i] + A[i]].min
  i + 2 < N and dp[i + 2] = [dp[i + 2], dp[i] + B[i]].min
end
dp                                  # => [0, 2, 5, 5, 8]
p dp[N.pred]                        # => 8

となる。

貰うなら前を、配るなら後ろを、はみ出ないように気にかけないといけないのがわかる。