lesson1Title

lesson2Title

lesson3Title

lesson4Title

lesson5Title

lesson6Title

lesson7Title

lesson8Title

lesson9Title

lesson10Title

lesson11Title

lesson12Title

lesson13Title

lesson14Title

lesson15Title

lesson16Title

lesson17Title

pythonIntroAlgorithms2Chapter1Title

pythonIntroAlgorithms2Chapter2Title

pythonIntroAlgorithms2Chapter3Title

pythonIntroAlgorithms2Chapter4Title

def fibonacci(n, memo={}):
    # If the value is in memo
    if n in memo:
        # Return the memoized value
        return memo[n]
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
    
print(fibonacci(1))
print(fibonacci(2))
print(fibonacci(3))
print(fibonacci(4))
print(fibonacci(5))
print(fibonacci(6))

# Implementing Dynamic Programming in Python

Let's explore dynamic programming by examining how to store and reuse subproblem results in Python code.

<br />

## 1. Define the Function and Set Up Memoization

Dynamic programming is the technique of storing and reusing computational results. Memoization is used to achieve this.

```python title="Example of Setting Up Memoization"
def fibonacci(n, memo={}):
    if n in memo:
        return memo[n] # Memoization
    if n <= 2:
        return 1
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]
```

<br />

## 2. Recursive Call and Storing Results

The function calculates the \(n\)-th Fibonacci number and stores it in `memo`. Stored values are reused.

```python title="Example of Recursive Call and Storing Results"
if n in memo:
    return memo[n]
if n <= 2:
    return 1
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
```

<br />

## Algorithm Complexity

1. `Time Complexity`: O(n)

   - The time complexity of the Fibonacci function using memoization is O(n). Each Fibonacci number is calculated only once, and the calculated value is stored and reused.

2. `Space Complexity`: O(n)

   - Due to the additional memory space used for memoization, the space complexity is also O(n). Each computed Fibonacci number is stored in the `memo` dictionary, so up to n spaces are required to compute the nth number.