anmolsainiii23's blog

Confused Regarding Cses 2nd DP Question
By anmolsainiii23, history, 13 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

Comments Comments (5)
| Write comment?
»
13 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    -2147483647 This is the output

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

      show me ur code

      → Reply
      • »
        »
        »
        »
        13 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
        • »
          »
          »
          »
          »
          13 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