Scribd
Upload
5 views

05A Dynamic Programming

Uploaded by

Nguyen Huynh Lam (K16HCM)
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
5 views

05A Dynamic Programming

Uploaded by

Nguyen Huynh Lam (K16HCM)
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 14

Dynamic programming

Introduction

1
What is Dynamic Programming?
• A method for solving complex problems by
breaking them into smaller, easier, sub
problems
• Term Dynamic Programming coined by
mathematician Richard Bellman in early
1950s
– employed by Rand Corporation
– Rand had many, large military contracts
– Secretary of Defense, Charles Wilson “against
research, especially mathematical research”
– how could any one oppose "dynamic"? 2
Who developed Dynamic
Programming?
"Thus, I thought dynamic programming
was a good name. It was something not
even a Congressman could object to. So
I used it as an umbrella for my activities"
- Richard E. Bellman

3
Dynamic Programming
• A generalization of iteration and recursion.
• “Dynamic Programming is recursion’s
somewhat neglected cousin. …(It) is the basis
of comparison and alignment routines.
• Bottom-up design:
– Start at the bottom
– Solve small sub-problems
– Store solutions
– Reuse previous results for solving larger sub-
problems

4
Fibonacci Numbers
• Computing the nth Fibonacci number recursively:
– F(n) = F(n-1) + F(n-2)
– F(0) = 0
– F(1) = 1 int Fib(int n)
– Top-down approach {
if (n <= 1)
return 1;
else
F(n) return Fib(n - 1) + Fib(n - 2);
}

F(n-1) + F(n-2)

F(n-2) + F(n-3) F(n-3) + F(n-4)

5
Fibonacci Numbers
• What is the Recurrence relationship?
– T(n) = T(n-1) + T(n-2) + 1
• What is the solution to this?
– Clearly it is O(2n), but this is not tight.
– A lower bound is (2n/2).
– You should notice that T(n) grows very
similarly to F(n), so in fact T(n) = (F(n)).
• Obviously not very good, but we know that
there is a better way to solve it!
6
Fibonacci Numbers
– Computing the nth Fibonacci number using a bottom-up
approach:
– F(0) = 0
– F(1) = 1
– F(2) = 1+0 = 1
– …
– F(n-2) =
– F(n-1) =
– F(n) = F(n-1) + F(n-2)
0 1 1 . . . F(n-2) F(n-1) F(n)

• Efficiency:
– Time – O(n)
– Space – O(n)
7
Fibonacci Numbers
• The bottom-up approach is only (n).
• Why is the top-down so inefficient?
– Recomputes many sub-problems.
• How many times is F(n-5) computed?

F(n)

F(n-1) + F(n-2) n levels

F(n-2) + F(n-3) F(n-3) + F(n-4)


… … …
8
Fibonacci Numbers
Fib(5)
+

Fib(4) Fib(3)
+ +

Fib(3) Fib(2) Fib(2) Fib(1)


+ + +

Fib(2) Fib(1) Fib(1) Fib(0) Fib(1) Fib(0)


+

Fib(1) Fib(0)

9
How to calculate Fibonacci
Numbers faster?

10
Solution

11
Momoization – Top Down

12
Tabulation – Bottom Up

13
14

You might also like