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

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;
}
```