Hello,
I’m at that point where I can recognize a problem has something to do with DP, but I just can’t seem to translate that into actual code. I believe I get the basics like overlapping subproblems, and I can figure out if a problem is DP-related. But when it comes to sitting down and writing the actual implementation.. I literally face a wall.
for example see recent problem like 2022C - Gerrymandering
I knew it must has something to do with DP, and able to identify three condition? 1x3 shape L shape, Г shape and closing but endup with no actual code but full of thought in 2 hours.
Anyone have tips on how to bridge that gap? How do you go from identifying a DP problem to confidently writing out the solution?
And what is your rules of thumb that you follow when implementing DP problems? I'm not posting this to hear something like "practice more problem on DP" or similar.
Thanks in advance.
I think it can be really helpful to write out what $$$dp[i][j]$$$ (however many dimensions it has) means. For example, if you want to figure out the number of binary strings of length $$$n$$$ that are made up of single $$$1$$$'s and double $$$0$$$'s (like $$$001$$$ but not like $$$101$$$), you can write out that $$$dp[i]$$$ is the number of binary strings of length $$$i$$$ having that property. Usually that is the hard part and the recurrence relation shouldn't be too hard from there.
i also don't know iterative dp but i think recursive dp is fine to solve all these problems may be try to get better at recursion .
for 2022C - Gerrymandering you can chek it 285716626 just breaking down into different cases
Same here, I figured out at a point that it is a DP Sum, but couldnt implement
Write the dp formula on your scratch paper first. Don't write your code before you got a completed and correct solution.
Try out the cses dp section they have some really good questions.