This problem can be solved by dynamic programming. Let dp[i][j] represent number of ways of arrangement such that in a stack of i pancakes the maximum radius is j. hence dp[i][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.
No, the answer should’nt be the catalan number because when n=4 Cn=14 but the answer is 15 .
`
public class Solution {
public static void main(String[] args) {
// TODO Auto-generated method stub
int n=5;
// i'm using n-1 here is because at the bottom of the stack one pankcake of radius 1 is fixed,
//where as max represents the maximum radius upto this number
System.out.println(fun(n-1,1));
}
static long fun(int n, int max) {
if(n==0) {
return 1;
}
if(n<0) {
return 0;
}
long ans=0;
for(int i=1;i<=max+1;i++) {
ans+=fun(n-1,Math.max(i, max));
}
return ans;