7. Speeding up dynamic programming

views comments

Finding minimum elements in every row of an array
No other information: Brute force O(mn) is optimal
Monotone: Minima in higher rows are above/left of minima in later rows
Filtering: row minima in monotone arrays in O(m + n log n) time
Totally monotone: Every minor is monotone
SMAWK: Reducing wide totally monotone arrays in O(n) time
Alternately reducing and filtering: Row minima of totally monotone array in O(m+n) time.

	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