FUNDAMENTAL INFORMATION TECHNOLOGY ENGINEER
基本情報技術者の問題解説：隣り合う要素を同時に選ばないという条件で、選んだ要素の合計の…
問題
隣り合う要素を同時に選ばないという条件で、選んだ要素の合計の最大値を求める。戻り値はどれか。配列の要素番号は1から始まる。
整数型の配列: a ← {4, 1, 7, 3, 6}
整数型の配列: dp
dp[1] ← a[1]
dp[2] ← max(a[1], a[2])
for (i を 3 から aの要素数 まで 1 ずつ増やす)
dp[i] ← max(dp[i - 1], dp[i - 2] ＋ a[i])
endfor
return dp[5]- ア 13
- イ 15
- ウ 17（正解）
- エ 18
出典：オリジナル問題｜参考範囲：試験要綱Ver.5.5 / FEシラバスVer.9.2 科目B範囲
正解と解説
正解：17
dp[i]はi番目まで見たときの最大値です。i番目を選ばないdp[i-1]と、i番目を選ぶdp[i-2]+a[i]を比較します。
dp[1]=4，dp[2]=4，dp[3]=max(4,11)=11，dp[4]=max(11,7)=11，dp[5]=max(11,17)=17となります。7と6は隣接していないため同時に選べます。
Hardでの確認点：DPでは、dp[i]が何を表すかを先に決めましょう。今回なら「i番目まで見たときの最大値」であり、選ぶ場合と選ばない場合の比較になります。単に大きい要素を足すだけでは、隣接制約を破る可能性があります。
このアルゴリズムの正体：これは「隣接する要素を選べない」制約付き最大和を求める動的計画法で、各要素を見るたびに前の結果を再利用するため計算量はO(n)です。dp[i-1]だけでなくdp[i-2]+a[i]と比べるのが要で、a[i]を選ぶ直前のi-1を飛ばしてi-2の最適値に積み上げることで隣接違反を防いでいます。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。