<story><title>Dynamic programming is not black magic</title><url>https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/</url></story><parent_chain><item><author>akoboldfrying</author><text>It&amp;#x27;s good that the article points out that DP algorithms are &amp;quot;just&amp;quot; clever ways to cache a recursion. Looking for a recursive solution is certainly the best way to start out looking for a DP solution, in my experience -- if you can find one, memoising it is trivial and may give a big speedup (and may even be faster than a &amp;quot;bottom-up&amp;quot; DP, since it only ever computes solutions that we definitely need).&lt;p&gt;With enough practice, it&amp;#x27;s usually possible to come up with a (correct but slow) recursive solution. When turning this into a DP, it doesn&amp;#x27;t matter if there are large numbers of subproblems in the call tree -- what&amp;#x27;s important is that there are a relatively small number of &lt;i&gt;distinct&lt;/i&gt; subproblems. (Since there&amp;#x27;s no point caching a result that&amp;#x27;s only ever needed one time.) And that&amp;#x27;s where the difficulty tends to lie: Figuring out how to partition the original problem into &lt;i&gt;few enough distinct subproblems&lt;/i&gt;.</text></item></parent_chain><comment><author>vishnugupta</author><text>&amp;gt; what&amp;#x27;s important is that there are a relatively small number of distinct subproblems.&lt;p&gt;This is the crucial part IMO. Whether the larger algorithm is recursive or iterative etc is secondary. But yes DP usually tends to show up in recursive algorithms most often.</text></comment>
<story><title>Dynamic programming is not black magic</title><url>https://qsantos.fr/2024/01/04/dynamic-programming-is-not-black-magic/</url></story><parent_chain><item><author>akoboldfrying</author><text>It&amp;#x27;s good that the article points out that DP algorithms are &amp;quot;just&amp;quot; clever ways to cache a recursion. Looking for a recursive solution is certainly the best way to start out looking for a DP solution, in my experience -- if you can find one, memoising it is trivial and may give a big speedup (and may even be faster than a &amp;quot;bottom-up&amp;quot; DP, since it only ever computes solutions that we definitely need).&lt;p&gt;With enough practice, it&amp;#x27;s usually possible to come up with a (correct but slow) recursive solution. When turning this into a DP, it doesn&amp;#x27;t matter if there are large numbers of subproblems in the call tree -- what&amp;#x27;s important is that there are a relatively small number of &lt;i&gt;distinct&lt;/i&gt; subproblems. (Since there&amp;#x27;s no point caching a result that&amp;#x27;s only ever needed one time.) And that&amp;#x27;s where the difficulty tends to lie: Figuring out how to partition the original problem into &lt;i&gt;few enough distinct subproblems&lt;/i&gt;.</text></item></parent_chain><comment><author>Shorel</author><text>Agree. When I first learned the subject, my first thought was:&lt;p&gt;As fancy as that feature is, it should be called array memoization, or call stack memoization.&lt;p&gt;The term &amp;quot;dynamic programming&amp;quot; should be reserved for something better. IMO.</text></comment>