Перевести этот код из рекурсивного в итеративный DP
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, если это возможно. Или это единственный способ, которым я могу это сделать?
Решение
Теоретически вы можете преобразовать любой рекурсивный метод в итеративный. Так что да, этот код тоже может.
Подробнее об этом есть в этой теме: https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration
Другие решения
Поскольку x может содержать произвольные целые числа, вы должны действительно вычислить R за любой ценность c где i фиксированный.
Некоторый код для объяснения:
// 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 может помочь улучшить результат.