10198 - Counting

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10198 - Counting HELP!

Post by 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;
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
Post Reply

Return to “Volume 101 (10100-10199)”