如何使用动态规划解决硬币行问题？

Question

硬币行问题：有一行n枚硬币，其值为一些正整数C0，C2，Cn-1，不一定不同。目标是提取最大金额的货币，但受限制，不能提取初始行中相邻的两个硬币。

在下面的代码中，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];
}

Answer 1

您的算法是正确的，但在实现中存在一些错误。当循环从i=2开始时，跳过C[1]处的值。由于在F数组中包含0个硬币盒，因此F[n]的大小必须为n1。根据上述更正，我们得出：

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];
}

Answer 2

所有数字都将是正数的说法让事情变得简单了一点。从这些信息中，我们可以确定我们永远不想跳过两个连续的数字。我们只需使用第一个数字计算可能的最佳序列，并将其与使用第二个数字可能的最佳序列进行比较。这是递归的理想选择。

int coin_row(int *C, int n) 
{
    int first_total;
    int second_total;

    if (n == 0) return 0;
    if (n == 1) return *C;
    if (n == 2) return max(*C, *(C+1));

    first_total = *C + coin_row(C+2, n-2);
    second_total = *(C+1) + coin_row(C+3, n-3);
    return(max(first_total, second_total));
}

通过将问题分解为一系列对，我们将列表视为一棵大的二叉树。在每一对中，您可以选择第一个或第二个数字。计算每个子树的总数并返回最大值。例如{10,2,4,6,3,9,5}的路径是：

          10                    2
          /\                   /\
         4  6                 6  3
        /\  /\               /\  /\
       3  9 9 5             9  5 5 -