For the problem described in Ex. 15.9 about breaking a string a) Prove optimal substructure b) Write the recursive definition for defining the least cost solution c) Write the algorithm (either the memo-ized version or bottom-up version)

If you could help me get started on any of the above three questions (or all three), I would greatly appreciate it. Ex. 15.9

  • 2
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. If you're asking about dynamic programming, we've written some general information to help you get started: cs.stackexchange.com/tags/dynamic-programming/info. I suggest that you absorb that material, apply the systematic approach there, then edit your question to show how far you got and at what step you got stuck. $\endgroup$
    – D.W.
    Mar 21, 2017 at 23:20
  • 1
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – D.W.
    Mar 21, 2017 at 23:20
  • $\begingroup$ This DP problem, or al least close variants seems to, has been discussed several times at this site. I checked for questions with "cutting": Board cutting problem, Knuth Yao DP Speedup - Cutting Sticks, dynamic programming exercise on cutting strings, Broken stick problem. $\endgroup$ Mar 22, 2017 at 13:40
  • $\begingroup$ This reads like a question straight out of a textbook question section. $\endgroup$
    – SDsolar
    Mar 23, 2017 at 7:51


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.