2
$\begingroup$

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

Improve this question
$\endgroup$
  • 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 '17 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 '17 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$ – Hendrik Jan Mar 22 '17 at 13:40
  • $\begingroup$ This reads like a question straight out of a textbook question section. $\endgroup$ – SDsolar Mar 23 '17 at 7:51

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.