What will be the recursive approach for this problem.

Revision en1, by spirited_away_, 2019-11-07 17:50:44

The problem Red-Green Towers CF 478 d , we are given r red balls and g green balls. we have to find in how many ways we can make a tower of height h with given conditions.

A simple recursive dp with memoization is, suppose we are at level i, we can either fill it will red or green and recur for next. our state will be height till now and number of red balls. But it will give Memory limit exceeded.

While solving the same problem with iterative dp, we see that i depends on only i-1(editorial) so we can easily maintain dp[2][N] state and fill the dp array accordingly. But how to solve this problem with recursion using memoization.

Do we need to pass cnt variable as a reference in recursive function, where cnt is the level right now. how to solve this problem using recursion.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English spirited_away_ 2019-11-07 17:52:20 63
en1 English spirited_away_ 2019-11-07 17:50:44 939 Initial revision (published)