3. Backtracking and dynamic programming

views comments

Example 1: Text segmentation (Interpunctio verborum)

Example 2: Longest increasing subsequence

Is this input number in the subsequence?
An increasing sequence larger than x is either empty or a number y larger than x followed by an increasing sequence larger than y.
Two-parameter recurrence -> memoize into 2d array
single arrows = inner loop, double arrows = outer loop
English specification + recurrence + evaluation order picture + time bound = full credit

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois