PANSTACK - Editorial

PROBLEM LINKS

Practice
Contest

DIFFICULTY

EASY

EXPLANATION

This problem can be solved by dynamic programming. Let dp*[j] represent number of ways of arrangement such that in a stack of i pancakes the maximum radius is j. hence dp*[j] = dp[i-1][j]*j + dp[i-1][j-1]. The first term is the cases in which you have placed pancakes till size j in the previous position, in those cases you can place any pancake till radius j in the current position. And the second term is the case when you are placing a pancake of radius exactly 1 less than j in all the previous positions and you are allowed to place a pancake of radius j in the current position. For answer of size n, sum over all j <= n for dp[n][j] will be the result.

SETTER’S SOLUTION

Can be found here.

TESTER’S SOLUTION

Can be found here.

4 Likes

Tell me if I am wrong…

The answer of this problem should be Catalan Number

Why it is showing always wrong answer!!!

How to solve it using one D DP?

Can some one explain the solution more clearly?