Implementing Dynamic Programming in Python

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

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

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

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

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

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.