CISC 365 Lecture Notes - Lecture 12: Brie, Dynamic Programming

37 views6 pages

Document Summary

We began our study of dynamic programming by considering a problem: Given a rectangular grid with rows numbered 0,,n and columns numbered 0,,m, With (0,0) in the top left corner and (n,m) in the bo om right corner. With costs associated with all edges - notation: w(a,b : c,d) is the edge-cost (or weight) of the edge from (a,b) to (c,d) With all horizontal edges pointing to the right. From the structure of the grid we can see that every path from (0,0) to (n,m) contains exactly n down edges and exactly m right edges. The total number of di erent paths from (0,0) to (n,m) is equal to the number of ways of interleaving the down and right edges. To get a sense of how large the set of paths is, we can apply the following somewhat casual analysis: First, for simplicity assume that n = m .

Get access

Grade+
$40 USD/m
Billed monthly
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
10 Verified Answers
Class+
$30 USD/m
Billed monthly
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
7 Verified Answers

Related Documents

Related Questions