First of all, I now know that 'dynamic' has nothing to do with the dynamism of a dynamic programming algorithm. But I didn't before I studied them, and I was kind of disappointed that they all seem to rely on a pretty basic recursion. Are there any problems with more interesting optimal substructures?

  • $\begingroup$ I don't follow. It sounds like you just want examples of "interesting" DP problems? The whole point of a DP algorithm is to make the computation a basic recursion of a function of a small number of variables that each take as few values as possible. $\endgroup$ – j_random_hacker Sep 17 '20 at 2:09
  • 1
    $\begingroup$ For a problem that can be solved using DP, but for which the side constraints that enable optimal substructure are challenging to find, I suggest cs.stackexchange.com/questions/126885/…. $\endgroup$ – j_random_hacker Sep 17 '20 at 2:12
  • $\begingroup$ I'm not entirely sure what you're asking here, but your title vaguely reminds me of a common misconception that a DP algorithm can use the full information of a solution instance, rather than solution value. But please clarify what you mean by interesting optimal substructures. $\endgroup$ – Discrete lizard Sep 17 '20 at 5:38
  • $\begingroup$ I'm not sure what you're asking, either. Can you provide an example of what you mean? $\endgroup$ – 6005 Sep 17 '20 at 14:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.