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?
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.
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?