###### 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)$

Fibonacci(n)
    if n < 2
        return 1
    return Fibonacci(n-1) + Fibonacci(n-2)


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

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


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


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


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

#### Top-Down Approach using Memoization

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

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]
    }
}