PANSTACK: Ace Dynamic Programming, not just memoization

Dear codecheffers,
I’ve few questions to ask and the way you guys approach a problem (esp. w.r.t applying DP). I’ve just started taking competitive programming and finding application of DP tough, throw some insights (like how you approach the problem).

I tried the Stacking Pancakes, which I clearly identified as a DP based problem, but, could only manage to apply memoization . Here’s my code

#include <stdio.h>
#include <string.h>
#define MOD 1000000007
unsigned int memo[1001][1001];

unsigned int N;

unsigned int getCount(unsigned int level,unsigned  int max){
	register unsigned  int i,total=0;
	if( level == N-1  && N > 2){
		memo[level][max] = max+1;
		memo[level][max+1] = max+2;
		return max+1;
	}
	if( level >= N){
		return 1;
	}

	if( memo[level][max] != 0 ){
		return memo[level][max];
	}


	for(i=1;i<=max+1; ++i){
		if( i < max ){
			if( memo[level+1][max ] != 0 ){
				total = total + memo[level+1][max];
			}else{
				total = total + getCount(level+1,max);
			}
		}
		else{
			if( memo[level+1][i] != 0 ){
				total = total + memo[level+1][i];
			}else{
				total = total + getCount(level+1,i);
			}

		}

		total=total%MOD;
	}

	memo[level][max] = total;
	return total;
}


int main() {
	unsigned int T;
	scanf("%d",&T);
	unsigned int d=0;
	memset(memo,0,sizeof(unsigned int)*1001*1001);

	while(T){
		memset(memo,0,sizeof(unsigned int)*1001*1001);

		scanf("%d",&N);
		d = getCount(1,1);
		printf("%d\n", d);
		T-=1;
	}
	return 0;
}

I know my program is still exponential ( pls check) , but, it was a great improvement over plain recursive algo. As I tried the overlapping calculations at each level ( number of digits ), but, it was not sufficient to break the 1s time limit and i got TLE.

Could someone who got AC (I know many, admins, someone) pls help! A little more than the editorial would help!

thanks

1 Like

as you said you “clearly identified it’s a DP problem”, the only remaining step is to find the formula behind the problem. thus, the solution implementation is simply a loop iterating over this formula. in this specific problem, the formula is the following one :

DP[0][0] = 1
DP[r][0] = (DP[r-1][r-1])
DP[r][c] = (DP[r-1][c-1] + DP[r][c-1]) % 1000000007

it can be guessed on small inputs (stack with only a few pancakes), that you can generate yourself, for instance, and solve by hand. actually, it consists in computing the Bell Numbers. i can show you my simple answer in Python. hope it helps.

3 Likes

identifying the formula is the real core of DP, i guess. I think practicing few problems would help there. Do share the similar problems you’ve solved (DP based) that will be gr8.

thanks bud!

that’s right. the main thing (that can be achieved with practice) is to find the correct formula for a specific problem. sometimes, it can be simply derived from a recurrence relation, sometimes it’s not so simple. the tutorial section can help you, giving you a few examples. good luck :slight_smile:

Excelente aporte, gracias y un saludo.