概要

一列に並んだ花壇に美しさの異なる花を植えるが、隣り合う花壇には同時に植えることができない。植える花壇をうまく選んで、得られる美しさの合計を最大化する問題。

考察

この問題では、「隣り合う花壇に同時に花を植えることはできない」という制約があるため、すべての花壇に花を植えるわけにはいきません。貪欲に大きい順に選ぶ、といった単純な方法では正しい答えを得られません。例えば、入力が [2, 7, 9, 3, 1] のとき、一番大きな 9 を選ぶと、隣の 7 と 3 は選べなくなります。しかし、7 と 3 の和の方が 9 よりも大きいため、最適ではありません。

このように「選択によって次への影響が出る」タイプの最適化問題に対しては、動的計画法（DP）が有効です。ある花壇まで見たときに「最後に選んだか選ばなかったか」によって、次の選択肢が変わるという点に注目します。

DPテーブルとして以下のように定義します： - \(dp[i]\) := \(i\) 番目までの花壇で得られる美しさの最大値

遷移としては、 - \(i\) 番目の花壇を選ばない場合：前の状態 \(dp[i-1]\) を引き継ぐ - \(i\) 番目の花壇を選ぶ場合：\(i-1\) 番目は選べないので \(dp[i-2] + A[i]\) となる

したがって、 $\( dp[i] = \max(dp[i-1],\ dp[i-2] + A[i]) \)$ という漸化式が成り立ちます。

初期条件としては、 - \(dp[0] = A[0]\) - \(dp[1] = \max(A[0], A[1])\)

とすれば、以降の計算が自然に行えます。

アルゴリズム

動的計画法を用いて、各花壇について「選ぶ場合」と「選ばない場合」の最大値を更新していきます。

具体的な手順は以下の通りです： 1. 入力を受け取り配列 \(A\) に格納 2. DP配列 \(dp\) を用意し、初期値を設定 3. 漸化式 \(dp[i] = \max(dp[i-1],\ dp[i-2] + A[i])\) に従って計算 4. 最終的な答えは \(dp[N-1]\) に格納されている

計算量

• 時間計算量: \(O(N)\)
• 空間計算量: \(O(N)\)

※ 空間をさらに節約して \(O(1)\) にすることも可能ですが、ここでは基本的なDPによる解法を示しています。

実装のポイント

• 配列のインデックスに注意し、範囲外アクセスにならないよう気をつける

• \(N=1\) の場合だけ例外処理を入れておくと安全

• DPテーブルの初期化を正しく行う（特に最初の2要素）

  ソースコード

n = int(input())
a = list(map(int, input().split()))

if n == 1:
    print(a[0])
else:
    dp = [0] * n
    dp[0] = a[0]
    dp[1] = max(a[0], a[1])
    
    for i in range(2, n):
        dp[i] = max(dp[i-1], dp[i-2] + a[i])
    
    print(dp[n-1])

---

この解説は qwen3-coder-480b によって生成されました。