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

Why not Recursive?
Автор anmolsainiii23, история, 7 месяцев назад, По-английски

Hi I was wondering why can't we use recursive Solution for Coin Piles Solution. This is the Problem

I have tried recursive solution but end up getting TLE and Runtime Error. Can anyone explain whether we can use Recursion or Dynamic Programing. This is my Solution.

This is my Soluion

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

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

See the constraint on a, b (1e9). It seems yours code taking O(ab) time and memory

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

    Yeahh. Ok got it. But the recurrence was correct?

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

      apart from (time / space complexity) yours recurrence solution was correct, but generally recursive solution was slower than dp.

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

        Yeah that I agree. I just tried solving CSES and CSES is actually hard to solve. Considering the constraints doesn't favour Bruteforce Solution. They actually prefer Optimized one.

        → Ответить
    • »
      »
      »
      7 месяцев назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      You also can solve it as O(1)

      → Ответить