FE SUBJECT B
基本情報技術者 科目Bの問題解説
問題
隣り合う要素を同時に選ばないという条件で，選んだ要素の合計の最大値を求める。戻り値はどれか。配列の要素番号は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
正解：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番目まで見たときの最大値」であり，選ぶ場合と選ばない場合の比較になる。単に大きい要素を足すだけでは，隣接制約を破る可能性がある。
この問題について
公開問題・サンプル問題の形式、擬似言語記法、アルゴリズム読解・トレース・空欄補充・セキュリティ事例判断の傾向を参考にした独自問題です。本文・数値・選択肢は新規作成しています。
公式試験問題、公開問題、市販教材、外部問題サイトの問題文を転載・改題したものではありません。