### Re: 10198 - Counting HELP!

Posted:

**Tue Dec 16, 2014 9:22 am**hey all

all of the discussions in this thread are about BigInteger and a bottom up approach

However, it can be solved using top down approach as my function below
i was supposed to solve this using bottom up

i first wrote this recursive function that's accepted then tried to convert it using table method but couldn't

until i saw this thread and found a new recurrence as
that is easy to build a table with

as written

f[1]:=2; f[2]:=5; f[3]:=13;

f[n]:=2*f[n-1]+f[n-2]+f[n-3];

/////

my question is can we build a table for my first recursive function

in general, can we build a table for any recurrence or not

if so, how ?

and can any one give me any source to improve my "building tables with DP technique" (bottom up approach technique) ?

i'm really having a hard time understanding how it should be or how does it really works and why !

thanks in advanced and sorry for this long post

all of the discussions in this thread are about BigInteger and a bottom up approach

However, it can be solved using top down approach as my function below

Code: Select all

```
#define nNum 4
int val[nNum] = {1, 1, 2, 3};
BigInteger count(int ind, int rem)
{
if(rem == 0)
return one;
if(ind == nNum || rem < val[ind])
return zero;
return count(ind+1, rem) + count(0, rem-val[ind]);
}
```

i first wrote this recursive function that's accepted then tried to convert it using table method but couldn't

until i saw this thread and found a new recurrence as

Code: Select all

```
BigInteger count1(int rem)
{
if(rem == 0)
return one;
if(rem < 0)
return zero;
return 2*count1(rem-1)+count1(rem-2)+count1(rem-3);
}
```

as written

f[1]:=2; f[2]:=5; f[3]:=13;

f[n]:=2*f[n-1]+f[n-2]+f[n-3];

/////

my question is can we build a table for my first recursive function

in general, can we build a table for any recurrence or not

if so, how ?

and can any one give me any source to improve my "building tables with DP technique" (bottom up approach technique) ?

i'm really having a hard time understanding how it should be or how does it really works and why !

thanks in advanced and sorry for this long post