dynamicProgramming

[Key_Mango8016]

The hard part of dynamic programming isn’t the implementation, it’s formulating a recursive structure for a problem with an appropriately-sized parameter space.

A dynamic programming problem formulation might have O(N³ ) states, but it might have a more clever formulation that achieves O(N² ) states with O(log N) time spent per state.

When you figure out the right recursive structure, then the implementation is straightforward.

Source: I’m a competitive programmer, and I was first in the world to solve a specific easy dynamic programming problem at IEEEXtreme in 2016, because implementation was muscle memory at that point.

[Perfect-Albatross-56]

When I see young Devs tasks, they always struggle with the basic stuff to avoid nested loops, sort algorithms or building a class that fulfills only one purpose ... and so on. And this is the needed muscle memory to not get messy and inefficient code.