Блог пользователя TheAiro

Автор TheAiro, история, 12 месяцев назад, По-английски

Hi, I am having difficutlties with this CSES problem "Book Shop". Firstly I implemented it recursively, but it gave me TLE. (Link). I've also been trying to get into iterative dp, so I tried it too and it worked! (Link)

However, I don't understand why recursive approach doesn't pass. Maybe I have implemented it poorly?

Also, it seems that there is an approach with $$$O(x)$$$ space complexity, but I have no clue how it works.

  • Проголосовать: нравится
  • -5
  • Проголосовать: не нравится

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It might be because recursive functions use up the call stack and that can get expensive enough to get a TLE.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Well, recently I've had a dilemma whether to use iterative approach, or a recursive one. Iterative seems to get an upper hand here. But there got to be a way for recursive approach to pass...