【ABC369】D - Bonus EXP のイメージベース解説(動的計画法の基本が理解できる)

目的

AtCoder公式解説を見て動的計画法の基本が理解できたので、復習用にイメージベースで解説

問題

解き方

1. モンスターを倒した回数が偶数回だった場合の経験値の合計の最大値(evenExp)と奇数回だった場合の経験値の合計の最大値(oddExp)を求める
   
   ※evenExpは今回の経験値 * 2 + oddExpと計算前のevenExpの最大値
   ※oddExpはevenExp + 今回の経験値と計算前のoddExpの最大値
   1-1. evenExpを0でoddExpを-Infinity(初回のevenExpの計算結果を0にするため)で初期化
   
   1-2. 1回目のevenExpとoddExpの計算
   
   ※初回の戦闘なので、evenExp=0でoddExp=1になる
   1-3. 2回目のevenExpとoddExpの計算
   
   ※evenExpは5 * 2 + 1で11となり、計算前の0より大きいので11
   ※oddExpは5 + 0で5となり、計算前の1より大きいので、5
   1-4. 3回目のevenExpとoddExpの計算
   
   ※evenExpは3 * 2 + 5で11となり、計算前の11と同じなので、11
   ※oddExpは11 + 3で14となり、計算前の5より大きいので、14
   1-5. 4回目のevenExpとoddExpの計算
   
   ※evenExpは2 * 2 + 14で18となり、計算前の11より大きいので、18
   ※oddExpは11 + 2で13となり、計算前の14より小さいので、14
   1-6. 5回目のevenExpとoddExpの計算
   
   ※evenExpは7 * 2 + 14で28となり、計算前の18より大きいので、28
   ※oddExpは18 + 7で25となり、計算前の14より大きいので、25
2. evenExpとoddExpの最大値である28が答え

コード

N, _ = gets.split.map(&:to_i)
A = gets.split.map(&:to_i)

# モンスターを倒した回数が偶数回だった時の経験値の合計の最大値
evenExp = 0

# モンスターを倒した回数が奇数回だった時の経験値の合計の最大値
oddExp = -Float::INFINITY # 初回のevenExpの計算結果を0にするため、-Float::INFINITYで初期化

A.each{|exp|
  oldEvenExp = evenExp

  # `今回の経験値 * 2 + oddExp`と`計算前のevenExp`の最大値
  evenExp = [exp * 2 + oddExp, evenExp].max()

  # `evenExp + 今回の経験値`と`計算前のoddExp`の最大値
  oddExp = [oldEvenExp + exp, oddExp].max()
}
puts [evenExp, oddExp].max()