Dynamic Programming

Dynamic Programming

Key Principles of Dynamic Programming:

• Overlapping Subproblems

• Memoization

When to Use Dynamic Programming:

• The problem can be divided into overlapping subproblems.
• You can solve the problem by combining the solutions to the subproblems.
• The problem has an optimal substructure.

Recognizing DP Problems:
DP problems typically ask for a "best" or "optimal" solution, like the shortest path, minimum cost, maximum profit, etc., and involve a choice that leads to the next problem state.

The problem can be broken down into smaller, simple subproblems, which can be solved independently. The solution to the main problem is then built from the solutions to these subproblems.

Recursion

input = 20

def fibo_recursion(n):
    if n == 1 or n == 2:
        return 1
    return fibo_recursion(n - 1) + fibo_recursion(n - 2)

print(fibo_recursion(input))  # 6765

Dynamic Programming

def fibonacci(n, memo={}):
    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]

# Example usage
print(fibonacci(10))  # Output: 55