[解決済み] 動的計画法を用いてコイン列の問題を解くには？

質問内容

コイン列問題：ある正の整数C0, C2, ... を値とするn枚のコインの列がある。Cn-1であり，必ずしも異なるとは限らない．目標は，最初の列で隣り合っている2枚のコインを拾うことができないという制約のもとで， 最大限の金額を拾い集めることである．

下のコードで、nは配列Cのサイズ（またはコインの数）です。このコードは、値[10, 2, 4, 6, 3, 9, 5]に対して正しい結果を返しました（正しい結果は25です）。しかし、同じコードを値 [3, 12, 10] または [3, 12, 10, 2] に対して実行すると、間違った結果が返されました。(一連の値に対して、結果はそれぞれ13と14であるべきです)。

私のコードを修正するのを手伝ってください。

int max(int a, int b) {
  if(a > b) return a;
  return b;
}

int coin_row(int[] C, int n) {
  if(n==1) return C[0];
  if(n==2) return max(C[0],C[1];

  int F[n], i;
  F[0] = 0; F[1] = C[0];

  for(i = 2;i < n;i++) {
    F[i] = max(C[i] + F[i-2], F[i-1]);
  }

  return F[n-1];
}

解決方法は？

アルゴリズムは正しいのですが、実装にいくつかバグがあります。 i=2 からループを開始しているので、C[1]の値をスキップしています。 F配列に0枚のコインケースを入れているので、F[n]が存在するためにはn+1のサイズが必要です。以上の修正で、次のようになります。

int max(int a, int b) {
  if(a > b) return a;
  return b;
}

int coin_row(int* C, int n) {
  if(n==1) return C[0];
  if(n==2) return max(C[0],C[1]);

  int F[n+1], i;
  F[0] = 0; F[1] = C[0];

  for(i = 2 ; i <= n + 1 ; i++) {
    F[i] = max(C[i-1] + F[i-2], F[i-1]);
  }
  return F[n];
}