Page 3 of 3

### recursion - memoization

Posted: Thu Jan 12, 2006 10:56 am
i tried to solve it using recursion and dp;
whats wrong with my code? is it my formulation , is my formulation wrong? this is a small code, i hope someone will answer soon...

Code: Select all

``````/*
* 10943 how do you add?
* submission 1 WA
* code finished at 2:20pm on dec25, 05
*
* this is a perfect example for memoization
*
*/

#include <stdio.h>
#include <string.h>

long cache[105][105];

long sum(int N, int K) {
int i;
long summ=0;

if(cache[N][K]!=-1) return cache[N][K];
if(N==0||K==0) return 1;
if(K==1) return N;
if(K==2) return N+1;

for(i=0;i<=N;i++)
summ+=sum(N-i,K-1)%1000000;
cache[N][K]=summ;
return summ;
}

int main() {
int N,K;
int i;
for(i=0;i<101;i++)
memset(cache,-1,sizeof(cache[0])*101);
while(scanf("%d %d",&N,&K)==2) {
if(!N && !K) break;
printf("%ld\n",sum(N,K)%1000000 );
}
return 0;
}
``````

Posted: Thu Jan 12, 2006 11:32 am
On the first sight, the memset part looks wrong to me.
Replace it with memset(cache, -1, sizeof(cache));

Posted: Thu Jan 12, 2006 7:50 pm
thanks, thanks for reply~! though i still have WA...

### Re: recursion - memoization

Posted: Fri Jan 13, 2006 8:48 am
smilitude wrote:whats wrong with my code?
Ya, what's wrong? WA or TLE? I guess WA.
What should be the output for

Code: Select all

``2 1``

### Re: recursion - memoization

Posted: Fri Jan 20, 2006 9:04 am
mamun wrote:
smilitude wrote:whats wrong with my code?
Ya, what's wrong? WA or TLE? I guess WA.
What should be the output for

Code: Select all

``2 1``
you are so helping mamun bhai!
thanks a lott!
i got ac, though i am regreting why didnt i notice that thing before?

Posted: Sun Oct 01, 2006 7:19 am
thanks for the i\o

### WA

Posted: Wed Jun 27, 2007 12:48 pm

Code: Select all

``````#include<stdio.h>
int main()
{
int dp[202][102],i,j;
for(i=0;i<202;dp[i][0]=1,dp[i][1]=i,i++);
for(i=1;i<202;i++)
for(j=2;j<102;j++)
dp[i][j]=(dp[i-1][j]+dp[i-1][j-1])%1000000;
while(1)
{
scanf("%d%d",&i,&j);
if(!i&&!j)
break;
printf("%d\n",dp[i+j-1][i]);
}
return 0;
}
``````
WRONG ANSWER! I have tested this for all inputs on the forum. It gives correct output. Please tell me where the problem could be.

Posted: Wed Jun 27, 2007 10:43 pm
Test the cases.

Input:

Code: Select all

``````2 1
2 2
0 0``````
Output:

Code: Select all

``````1
3``````
Hope these help.

### Re: 10943 - How do you add?

Posted: Fri Mar 25, 2011 8:08 pm
This is a DP problem, and my recurrence relation formula is way[N][K] = sigma 0<=i<=N (way[N-i][K-1])