10198 - Counting

[Testment]

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