Перевести этот код из рекурсивного в итеративный 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; 
}

Прямо сейчас это рекурсивная memoized функция, но я хочу перевести это на итеративный эквивалент DP, если это возможно. Или это единственный способ сделать это?Перевести этот код из рекурсивного в итеративный DP

источник

2013-08-02 user78793

Букет из 'goto' и' stack' может эмулировать рекурсию. – Shivam

Трудно, не зная содержимого x и константы N. – Sylwester

N - целое число, может достигать 206 или около того, x - массив произвольных целых чисел. – user78793

В теории вы можете преобразовать любой рекурсивный метод в итеративный. Итак, да, этот код тоже может.

Подробнее об этом в этой теме: https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

источник

2013-08-02 14:54:29

Я знаю, что каждая рекурсия может быть переведена, но я спрашиваю, как этот можно перевести, если это имеет смысл, извините, если мой английский плохой – user78793

Я ответил на вторую часть вашего вопроса. Но если вы хотите, чтобы мы сделали для вас всю работу, чем ... это может быть проблемой. Этот сайт больше связан с «Я пытался решить это, но я застрял здесь», чем «решить это для меня». Покажите нам, что вы уже сделали, определенная проблема, поскольку вы уже знаете, что ее можно перевести на итерацию :) –

если бы я знал, что делать, я бы не задал этот вопрос. – user78793

Поскольку х может содержать произвольные целые числа, вы должны действительно вычислить 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 может помочь улучшить результат.

источник

2013-08-02 20:59:55 MAnyKey

Перевести этот код из рекурсивного в итеративный DP

ответ

Смежные вопросы