Translate this code from recursive to iterative 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;
}

Right now this is a recursive memoized function but I want to translate this to iterative equivalent DP if possible. Or is this the only way I can do it?

It's difficult without knowing the contents of x and the constant N. — Sylwester, Aug 02 '13 at 15:27
N is an integer, can go up to 206 or so, x is array of arbitrary integers — user78793, Aug 02 '13 at 15:31

score 0 · Accepted Answer · edited May 23 '17 at 11:50

0

In theory, you can convert any recursive method in to an iterative one. So, yes, this code can too.

More about it is in this thread: https://stackoverflow.com/questions/931762/can-every-recursion-be-converted-into-iteration

edited May 23 '17 at 11:50

Community

1
1

answered Aug 02 '13 at 14:54

tomi.lee.jones

1,563
1
15
22

I know every recursion can be translated, but I am asking how this one can be translated if that makes sense, sorry if my English is bad – user78793 Aug 02 '13 at 14:55
I answered the second part of your question. But if you want us to do all the work for you than...this may be a problem though. This site is more about "i tried to solve this but i am stuck here" than "solve this for me". Show us what you have done already, a specific problem, as you already know it can be translated to iteration :) – tomi.lee.jones Aug 02 '13 at 15:01
if I knew what to do I wouldn't have asked this question. – user78793 Aug 02 '13 at 15:06
no, not homework. i've tried recreating it by not recursing but problem is that i don't know the end values because i need to calculate them by stepping through everything else in the first place, so not sure what the flow is – user78793 Aug 02 '13 at 15:10

score 0 · Answer 2 · answered Aug 02 '13 at 20:59

Since x can contain arbitrary integers, you should really compute R for any value of c where i is fixed. Some code to explain:

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

Maybe some restrictions on values of x can help to improve result.

Translate this code from recursive to iterative DP

2 Answers2