## 10198 - Counting

Moderator: Board moderators

Testment
New poster
Posts: 3
Joined: Sun Nov 16, 2014 4:06 am

### Re: 10198 - Counting HELP!

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

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 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

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);
}
``````
that is easy to build a table with
as written
f:=2; f:=5; f:=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