What will be the recursive approach for this problem.

Правка en2, от spirited_away_, 2019-11-07 17:52:20

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. Can this be solved using recusion + memo? what will be the parameters?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский spirited_away_ 2019-11-07 17:52:20 63
en1 Английский spirited_away_ 2019-11-07 17:50:44 939 Initial revision (published)