c++ - 硬币行算法

Question

我被困在这个算法问题上，我得到了这个概念，但我很难想象它的实现。硬币排问题 有一排 n 个硬币，其值为正整数 c1, c2, 。. . , cn，不一定不同。目标是在初始行中没有两个相邻的硬币不能被拾取的约束下，拾取最大数量的钱。我这里有一个基本算法。

F[0]←0; F[1]←C[1]
for i ← 2 to n do
    F [i] ← max(C[i] + F [i − 2], F [i − 1]) 
return F [n]

有人可以让我开始建立一个基本的实现。谢谢。

Answer 1

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

int coin_row(int[] C, int n) {
  int F[n+1], i;
  F[0] = 0; F[1] = C[1];

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

  return F[n];
}

Answer 2

根据你的算法，你想要这样的东西：

int coin_row(int[] array, int index, int length)
{
    if (index >= length) //beyond last coin
    {
        return 0;
    }

    int value = array[index];
    if (index >= length - 1) //last coin
    {
        return value;
    }
    else if (index >= length - 2) //second last coin
    {
        return max(value, coin+row(array, index+1);
    }

    return max(value+coin_row(array, index+2), coin_row(array, index+1));
}

打电话给

coin_row(array, 0, length of array);