anmolsainiii23's blog

Confused Regarding Cses 2nd DP Question
By anmolsainiii23, history, 7 months ago, In English

Hi I was practicing the dp section of CSES and I was Solving this Question Minimizing Coins and I approached Pick and Not Pick for this question. But Couldn't Solve it. This is my Code Code. Can anyone Explain ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where have you used dp its recursive solution?

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry Yeahhh Can you explain why my code is giving wrong output. I will edit the dp part tho

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try to submit it after memoizing and after that show me the error.

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        -2147483647 This is the output

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          In the pick option you should pass the starting index that is 0 not the same index where it is currently present so that it can find all the combinations that are possible.

          → Reply
          • »
            »
            »
            »
            »
            »
            7 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Okay Yeah I get it. Thankyou for help brother. By the way are CSES really helpful to counter problems in Codeforces Contest?. I have tried C2OJ and A2OJ ladders as well. Now I have started solving Questions from CSES.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              7 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Ofcourse they are helpful they make the foundation to approach any particular type of problem.

              → Reply
»
7 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I think your code is fine.. U only need to use dp

→ Reply
  • »
    »
    7 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    -2147483647 This is the output

    → Reply
    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      show me ur code

      → Reply
      • »
        »
        »
        »
        7 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        https://ide.geeksforgeeks.org/online-cpp14-compiler/157deeb9-2d31-43d3-8b45-c6ff60be6b1d

        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          This is the basic recursive solution. Now if we have to optimize this we will need dp. To do that here we have two changing variables index and the sum we want. But we cannot create a vector of size greater than i think 1e6 to 1e7. Size of array is upto 100 and x is upto 1e6 so the resulting array would be of size 1e2 * 1e6 i,e 1e8 which is not possible.

          Spoiler

          As we can see from the code that the current state of dp depends on curr index or prev index , what we can do is craete two dp arrays of size 1e6 current and prev and update them accordingly. Here is the tabulated solution.

          Spoiler
          → Reply