c++ - 将此代码从递归转换为迭代 DP

Question

double R(int N, int x[206], int i, int c){
    if (memo[i][c] != 0) return memo[i][c];

    if (i==N){
        if (c>=23) return 1;
        else return 0;
    }

    double s;
    s = R(N,x,i+1,c+x[i]);
    s += R(N,x,i+1,c-x[i]);
    memo[i][c] = s;
    return s;
}

现在这是一个递归记忆函数，但如果可能的话，我想将其转换为迭代等效 DP。或者这是我能做到的唯一方法？

Answer 1

理论上，您可以将任何递归方法转换为迭代方法。所以，是的，这段代码也可以。

有关它的更多信息在此线程中：https ://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

Answer 2

由于 x 可以包含任意整数，因此您应该真正计算where是固定R的任何值。一些代码来解释：ci

// case where i == N
for (int c = INT_MIN; c < INT_MAX; ++c) {
   memo[N][c] = (c>=23) ? 1 : 0;
}

for (int k = N - 1; k >= i; --k) {
  for (int c_ = INT_MIN; c_ < INT_MAX; ++c_) {
     memo[k][c_] = memo[k+1][c_ + x[k]] + memo[k+1][c_ - x[k]];
  }
}
return memo[i][c];

也许对值的一些限制x可以帮助改善结果。