---
# System prepended metadata

title: Dynamic Programming

---

---

type: slide
slideOptions:
    transition: 'convex'
---


# Dynamic Programming

**Group G**
謝皓青．林暘瑾．郭浩雲

---

## Introduction

Dynamic Programming, a technique of breaking down a problem into subproblems, solving these subproblems once, and storing their solutions.

----

### Key attribute

* optimal substructure
* overlapping sub-problem

----

### Optimal substructure

Find the shortest path from A to F
![](https://i.imgur.com/6gqEQJY.png)

----

### Optimal substructure
The solution to a given optimization problem can be obtained by the combination of optimal solutions to its sub-problems

----

### Overlapping sub-problem

Fibonacci series
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144
![](https://i.imgur.com/CRQsvmY.png)

----

### Overlapping sub-problem
If a problem can be divided into subproblems which are reused several times 

----

### Why dynamic programming?

----

recursive way
![](https://i.imgur.com/1Df38Bg.png)

----

dynamic programming way
![](https://i.imgur.com/52MezfT.png)

----

### Summary

*Footprints in the sand show where one has been*
凡走過必留下痕跡
*Use additional memory to save computation time*
用記憶體換速度

> cited from our algorithm Prof. Mei-chien Yeh.

---

### Top-down or bottom-up strategy

Different view to the same problem.
Same complexity.
Further explanation in case study.

---

### Case Study: Knapsack problem

![](https://i.imgur.com/GGHCDwU.png)

How do you put items into a bag to maximize the total value within a given limit of weight?
![](https://i.imgur.com/9BO4e4C.png)

----

#### Brute force

Take or not take, that is the question.

The most straight forward idea.
$2^n$ subsets, $n$ rounds
Results in $O(N\cdot 2^n)$ time complexity
Extremely inefficient

----

#### Greedy?

Take items that have the highest value, and then the less value one, and so on.

Sometimes a set of "cheap items" results in higher value than a set of a few "expensive items".

No suitable.

----

#### DP

![](https://i.imgur.com/NTP1APv.png)


----

![](https://i.imgur.com/7MPJ9qG.png)

For each element in the table, we compute
$T[i,j]=\begin{cases}max(T[i-1,j], T[i-1,j-w_i]+v_i)\\T[i-1,j], \text{if  }j-w_i<0\end{cases}$

----

![](https://i.imgur.com/MAYfR95.png)

----

#### Soloving

*  unbounded knapsack problem
*  0-1 knapsack problem
*  other problrm

![](https://i.imgur.com/8bozZdt.png)

----

unbounded knapsack problem
![](https://i.imgur.com/5T4UAgM.png)

----

0-1 knapsack problem
![](https://i.imgur.com/cAW2mHz.png)




