I am good at solving DP problems when the recurrence is apparent and the order of evaluating states follows from the recursion. However, I get stumped when the problem requires a weird order of evaluating states.
For example: 1367F2 - Flying Sort (Hard Version). Here the DP states are the values in the array while the order in which we evaluate them is based on the indices. I am looking to get better at these kinds of problems. I am open to suggestions / a list of practice problems.
Brute force + memoization for the win! The big-O-constant can be slightly optimized down the road by mechanical manipulations if the order of computation becomes apparent after the implementation and the TL is tight.
Yeah, this is exactly what I have been doing so far. But for example in the above problem, I couldn't come up with a recursive brute force + memoization that does better than $$$O(n^2)$$$ (which is what I did for F1).
I'm not sure about that exact problem, but you can try converting your recursive approach:
f(x)withf_memo[x].What is your recursive approach for the problem?
Yeah, ideally I should have come up with an $$$O(n)$$$ state recursion. But because of the weird order that the states need to be evaluated, I couldn't come up with one. (My function was $$$f(i,c)$$$ is the longest subsequence using elements from $$$0$$$ to $$$i$$$ with element $$$c$$$ being the element chosen last. Which has $$$O(n^2)$$$ states.)
Again this is just an example. Usually the steps you mentioned work and that is what I have been doing so far. I am looking for problems where they don't easily apply.
Thanks for your reply!
Ah, yes, you have to change the recursive approach here. I don't know any generic way, just a set of vague ideas from past problems. One popular is to "trade states for complex transition".
In that case, getting rid of $$$i$$$ works and keeping the rest of the state works. You will get $$$O(n)$$$ states, but each one will take $$$O(n)$$$ to calculate. Same $$$O(n^2)$$$, but much easier to apply memoization, and $$$O(n)$$$ transition is more prone to optimization than $$$O(1)$$$ transition.
I am also in the exact same situation. I can catch up with the recursive approach in dp problems easily, but I get slow when I try the iterative approach. But I think I have managed to get some improvement by trying to convert my recursive implementation into an iterative one. I am still not pro, but after doing this several times, I was able to think the iterative approach and solved some problems using that too.