Dynamic Programming (DP)

Dynamic Programming, often abbreviated as DP, is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable where the problem can be broken down into overlapping subproblems that can be solved independently.

Basic Principles

Optimal Substructure: The optimal solution to a problem can be constructed efficiently from optimal solutions of its subproblems.
Overlapping Subproblems: The space of subproblems must be small. A good sign of this is when a recursive implementation would lead to a repeated calculation of the same subproblems.

Common DP Problems

Fibonacci Sequence: Calculate the nth number in the Fibonacci sequence.
Knapsack Problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible.
Longest Common Subsequence: Find the longest subsequence common to all sequences in a set of sequences (not necessarily contiguous).

Example: Fibonacci Sequence

def fibonacci(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(fibonacci(10))

Resources

For more information on Dynamic Programming, you can check out our Dynamic Programming Tutorial.