Dynamic Programming with Example in Python

Dynamic programming is a technique used in computer programming to solve problems by breaking them down into smaller, subproblems that can be solved independently. This allows for a more efficient solution as the subproblems can be solved once and then used to solve the larger problem.

A simple example of dynamic programming in Python is calculating the Fibonacci sequence. In this example, we can break down the problem into smaller subproblems by calculating the previous two numbers in the sequence. This can be done using a function and a dictionary to store the previous calculations:

def fibonacci(n, fib_dict):
   if n in fib_dict:
      return fib_dict[n]
   if n == 0 or n == 1:
     return n
   fib_dict[n] = fibonacci(n - 1, fib_dict) + fibonacci(n - 2, fib_dict)
   return fib_dict[n]

fib_dict = {}
print(fibonacci(10, fib_dict))

In this example, the function fibonacci() is called recursively to calculate the nth number in the Fibonacci sequence. The dictionary fib_dict is used to store the previous calculations, allowing for more efficient solution to the larger problem.