CSE 421: Introduction to Algorithms

Table of Contents

CSE 421: Introduction to Algorithms

Dynamic Programming

Licking Stamps

How to Lick 27¢

A Simple Algorithm

Better Idea

New Idea: Recursion

Another New Idea:Avoid Recomputation

Finding How Many Stamps

Finding Which Stamps:Trace-Back

Complexity Note

Elements of Dynamic Programming

Matrix-chain Products

Matrix-chain Products

Simple Algorithm

Repeated Subproblems

Optimal Substructure:

An O(n3) Algorithm

Example:

Email: ruzzo@cs.washington.edu

Home Page: http://www.cs.washington.edu/homes/ruzzo

Other information:
(c) 1998, University of Washington, CSE