---
# System prepended metadata

title: 'ADA 5.1: Dynamic Programming'
tags: [ADA 5.1, Dynamic Programming]

---

###### tags: `ADA 5.1` `Dynamic Programming`
# ADA 5.1: Dynamic Programming
Textbook Chapter 15 - Dynamic Programming
Textbook Chapter 15.3 - Elements of dynamic programming

## What is Dynamic Programming?
- Dynamic programming, like the divide-and-conquer method, solves problems by <u>combining the solutions to subproblems</u>.
    - 用空間換取時間
    - 讓走過的留下痕跡
- Dynamic: time-varying
- Programming: a tabular method
- Dynamic Programming: planning over time

## Algorithm Design Paradigms
- __Divide-and-Conquer__
    - partition the problem into **independent** or **disjoint** subproblems
    - repeatedly solving the common subsubproblems
    - more work than necessary

- __Dynamic Programming__
    - partition the problem into **dependent** or **overlapping** subproblems
    - avoid recomputation
        - Top-down with memoization
        - Bottom-up method

## Dynamic Programming Procedure
- Apply 4 steps
    1. Characterize the structure of an optimal solution
    2. Recursively define the value of an optimal solution
    3. Compute the value of an optimal solution, typically in a bottom-up facshion
    4. Construct an optimal solution from computed information

## Rethink Fibonacci Sequence
- Fibonacci sequence
    - Base case: $F(0)=F(1)=1$
    - Recursive case: $F(n)=F(n-1)+F(n-2)$

```python=
Fibonacci(n)
    if n < 2
        return 1
    return Fibonacci(n-1) + Fibonacci(n-2)
```
![](https://i.imgur.com/v56YQ7O.png)

### Fibonacci Sequence
### Top-Down with Memoization

- Solve the overlapping subproblems recursively with memoization
    - Check the memo before making the calls

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

```python=
Memoized-Fibonacci(n)
    // initialize memo (array a[])
    a[0] = 1
    a[1] = 1
    for i = 2 to n
        a[i] = 0
    return Memoized-Fibonacci-Aux(n, a)

Memoized-Fibonacci-Aux(n, a)
    if a[n] > 0
        return a[n]
    // save the result to avoid recomputation
    a[n] = Memoized-Fibonacci-Aux(n-1, a) + Memoized-Fibonacci-Aux(n-2, a)
    return a[n]
```

### Bottom-Up Method

- Building up solutions to larger and larger subproblems

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

```python=
Bottom-Up-Fibonacci(n)
    if n < 2
        return 1
    a[0] = 1
    a[1] = 1
    for i = 2 to n
        a[i] = a[i-1] + a[i-2]
    return a[n]
```

## Optimization Problem
- Principle of Optimality
    - Any subpolicy of an optimum policy must itself be an optimum policy with regard to the initial and terminal states of the subpolicy
- Two key properties of DP for optimization
    - Overlapping subproblems
    - Optimal substructure - an optimal solution can be constructed from optimal solutions to subproblems

## Optimal Substructure Example
- Shortest Path Problem
    - Input: a graph where the edges have positive costs
    - Output: a path from S to T with the smallest cost

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

## Exercises
[LeetCode 509. - Fibonacci Number](https://leetcode.com/problems/fibonacci-number/)

#### Top-Down Approach using Memoization
```swift=
class Solution {
    func fib(_ n: Int) -> Int {
        var memo: [Int] = Array(repeating: 0, count: n + 1)
        return fib(n, &memo)
    }
    private func fib(_ n: Int, _ memo: inout [Int]) -> Int {
        guard n > 1 else { return n }
        if memo[n] == 0 {
            memo[n] = fib(n - 1, &memo) + fib(n - 2, &memo)
        }
        return memo[n]
    }
}
```

#### Iterative Bottom-Up Approach
```swift=
class Solution {
    func fib(_ n: Int) -> Int {
        guard n > 1 else { return n }
        var dp: [Int] = Array(repeating: 0, count: n + 1)
        dp[1] = 1
        for i in 2...n {
            dp[i] = dp[i - 1] + dp[i - 2]
        }
        return dp[n]
    }
}
```