lecxe's blog

[HELP] Dp optimization (CSES coin combinations 2)
By lecxe, history, 11 months ago, In English

Question https://cses.fi/problemset/task/1636/

My code: https://pastebin.com/Ex76qD5f

I know for some problems where in dp state, the transitions go from (i,j) -> (i+1, j) or (i, j) -> (i-1, j)
in this case we can make the dp storage as dp[2][maxJ] instead of dp[maxI][maxJ]

But is there a way I can do the same when I have already written the code in recursive fashion?

or make just few changes to code so to apply this (i.e dp[2][maxJ]) optimization, instead of writing the iterative code again to apply the optimization.

NOTE: I want to know if I can apply this optimization for a general case? Or it is necessary to write iterative code to apply it?

  • Vote: I like it
  • +5
  • Vote: I do not like it

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

I had solved it using state (dp[i]=number of ways to get sum==i) and then for each coin in the array say C reached sum = i(iterate over i from 1 to required_sum), iff (i>=C) ,by making transition dp[i]+=dp[i-C]. Then the final answer is stored in dp[required_sum].Don't forget to take mod.

In your code, you have taken sum of op1, op2.

op1:wherein you iterate on the indices and don't take the current element.

op2:wherein you try to consider the present element till the curr_sum stays >=0.

**A more optimised way** to do the same would be as follows:
Spoiler
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes I have seen some doing this way too link

    But I want to know about this optimization to be applied for a general case. Do I need to write iterative code only to apply it?

    → Reply