ソースコード
DPの漸化式の立て方を間違えました。最初は
dp[i] = Math.Max(dp[i - 1], dp[i - 2] + donations[i]);
だと思ったんですが、2つ飛ばしても最大になる場合があるのでこれではだめですね。
最後の家から寄付をもらうケースをどう扱うかについてもわかりませんでした。
初期値が複数パターンある場合、DPを複数回やらないとだめですね。
using System; using System.Collections.Generic; using System.Text; public class BadNeighbors { public int maxDonations(int[] donations) { int n = donations.Length; int[] dp = new int[n]; dp[0] = donations[0]; dp[1] = donations[1]; for (int i = 2; i < n - 1; i++) dp[i] = Math.Max(max(dp, i - 1), max(dp, i - 2) + donations[i]); int[] dp2 = new int[n]; dp2[1] = donations[1]; for(int i = 2;i < n;i++) dp2[i] = Math.Max(max(dp2, i - 1), max(dp2, i - 2) + donations[i]); return Math.Max(Math.Max(dp[n - 1], dp[n - 2]), Math.Max(dp2[n - 1], dp2[n - 2])); } private int max(int[] num, int idx) { int max = 0; for (int i = 0; i <= idx;i++ ) max = Math.Max(max, num[i]); return max; } }