Can some body explain me how to apply memoization technique to achieve linear time complexity for bellow.
closed as off-topic by Kaveh, András Salamon, R B, Jeffε, David Eppstein Aug 3 '14 at 7:10
This question appears to be off-topic. The users who voted to close gave this specific reason:
- "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Kaveh, András Salamon, R B, Jeffε, David Eppstein
The linear time algorithms for this sort of problem are based on the SMAWK algorithm rather than more straightforward dynamic programming / memoization. I have an implementation of a linear-time line-breaking algorithm (possibly not exactly the one you want, but likely similar) in the Wrap.py module of my collection of Python algorithm implementations (you'll also need SMAWK.py).