The hint discusses a mathematical approach. How am I supposed to solve it using DP? Also, please look at my solution. I’m not able to decide the state.
How is this a DP problem?
@bitbeast
You can also do this without that mathematical approach.
Like for every i from 0 to n, we have two choices either to pick L[i] or R[i], and the sum should be even at last.
So the dp state will be dp[i][j] where i represents when the element from 0 to i are considered and j is sum of them.
Here catch point is, we dont have to consider the actual sum what we can do is store sum%2 as j, so there will be only two values for j i.e. 0 and 1.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.