Dynamic programming

Dynamic programming (English: Dynamic programming, abbreviated as DP) is a method used in mathematics, management science, computer science, economics, and bioinformatics that solves complex problems by decomposing the original problem into relatively simple subproblems.

Imagine you are climbing anstaircase with n steps. Each time you can climb1step or2steps.

So, how many different ways are there to climb to the top of the building?

If you start from the topmost goal (thennth step), it may seem complicated.

But if we change our perspective:To reach thenn. To reach step n, you can onlyn-1take one step up from step n-1, or from then-2level by taking two steps up.. So, to reach thenThe number of ways to reach step n equals the number of ways to reach stepn-1n-1 plus the number of ways to reach stepn-2level, the number of ways.

This kind ofDecompose a large problem into several overlapping subproblems, and avoid repeated computation by storing the solutions of subproblems, thereby solving the original problem efficiently.The method is Dynamic Programming (DP for short).

Core idea

The core of dynamic programming isremember the solutions already computed. 。

Dynamic programming is usually used to solve problems with the following properties:

  1. overlapping subproblems: During the recursive solution process, the same subproblem may be computed multiple times.
  2. Optimal substructure: The optimal solution to a problem contains the optimal solutions to its subproblems.

We can use a simple flowchart to understand the problem-solving approach of dynamic programming:

The figure above shows the typical steps for solving a dynamic programming problem: start by defining the problem, find the subproblem structure through analysis, then formalize it with states and state transition equations, and finally obtain the answer through clear initial conditions and computation order.

From recursion to dynamic programming: the climbing stairs problem

let's use the classic"Climbing Stairs"problems to experience the optimization process from recursion to dynamic programming.

Problem description

Suppose you are climbing stairs. You neednsteps before you can reach the top. Each time you can climb1or2steps. How many different ways can you climb to the top?

Method 1: brute-force recursion (inefficient)

Based on the analysis at the beginning, we can directly write the recursive formula:f(n) = f(n-1) + f(n-2)where,f(1) = 1, f(2) = 2。

Example

def climb_stairs_recursive(n: int) -> int:
    """Recursive solution"""
    if n == 1:
        return 1
    if n == 2:
        return 2
    return climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)

# Test
print(f"Number of ways to climb to the 5th step (recursion): {climb_stairs_recursive(5)}")  # Output: 8

Disadvantages Analysis: This recursion involves a large amount of repeated computation. For example, computingf(5)requiresf(4)andf(3), computingf(4)in turn requiresf(3)andf(2), heref(3)It is computed twice. Whennn is large, the time complexity is exponential.O(2^n), which is extremely inefficient.

Method 2: Recursion with memoization (top-down)

We can use an array (a "memo") to store already computed results and avoid repeated calculations.

Example

def climb_stairs_memo(n: int) -> int:
    """Recursion with memoization (top-down)"""
    # Initialize the memoization table; -1 means not computed
    memo = [-1] * (n + 1)
   
    def helper(x: int) -> int:
        # Base case
        if x == 1:
            return 1
        if x == 2:
            return 2
        # If already computed, return the result directly
        if memo[x] != -1:
            return memo[x]
        # Otherwise, compute and store it in the memoization table
        memo[x] = helper(x - 1) + helper(x - 2)
        return memo[x]
   
    return helper(n)

print(f"Number of ways to climb to the 5th step (memoization): {climb_stairs_memo(5)}")  # Output: 8

The time complexity of this method is reduced toO(n), because each subproblem is computed only once. The space complexity isO(n). This is already a dynamic programming approach, called"top-down"or"memoized search"。

Method 3: Iterative array (bottom-up, standard DP)

We start directly from the smallest subproblem and iterate step by step to the original problem. Usually an array is useddpto store states.

Example

def climb_stairs_dp(n: int) -> int:
    """Dynamic programming (bottom-up)"""
    if n <= 2:
        return n
    # 1. Define the state array: dp[i] represents the number of ways to climb to the i-th step
    dp = [0] * (n + 1)
    # 2. Determine the initial conditions
    dp[1] = 1
    dp[2] = 2
    # 3. State transition: derive recursively according to the state transition equation
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    # 4. Return the final result
    return dp[n]

print(f"Number of ways to climb to the 5th step (DP): {climb_stairs_dp(5)}")  # Output: 8

Method 4: space optimization (rolling array)

Observe the state transition equationdp[i] = dp[i-1] + dp[i-2], we find that the current state only depends on the previous two states. Therefore, we don't need to store the entiredparray; just use two variables to update in a rolling fashion.

Example

def climb_stairs_optimized(n: int) -> int:
    """Dynamic programming (space-optimized version)"""
    if n <= 2:
        return n
    # Use only two variables to represent dp[i-1] and dp[i-2]
    prev, curr = 1, 2  # Correspond to dp[1], dp[2]
    for i in range(3, n + 1):
        # Compute the new current value
        new_curr = prev + curr
        # Rolling update variables, preparing for the next loop iteration
        prev, curr = curr, new_curr
    return curr

print(f"Number of ways to climb to the 5th step (optimized DP): {climb_stairs_optimized(5)}")  # Output: 8

After optimization, the space complexity goes fromO(n)dropped toO(1)。

Dynamic programming problem-solving framework

Through the climbing stairs problem, we can summarize a universal four-step process for solving dynamic programming problems:

Step 1: Define the state

Use one or more arrays (usually calleddp) to represent the solutions to subproblems. The key is to clearly figure outdp[i]ordp[i][j]What does it represent?

In the climbing stairs problem, we definedp[i]as "climb to theithe total number of ways to reach step n.

Step 2: Determine the state transition equation

finddp[i]with the previous state (such asdp[i-1], dp[i-2]the relationship between them. This is the core and difficulty of dynamic programming.

In the climbing stairs problem, the state transition equation is:dp[i] = dp[i-1] + dp[i-2]。

Step 3: Determine the initial conditions (Base Case).

The solutions to the smallest, indivisible subproblems. This is the starting point of the recurrence and must be defined manually.

In the climbing stairs problem, the initial conditions are:dp[1] = 1, dp[2] = 2。

Step 4: Determine the computation order and compute

Determine whether it is "top-down" (memoized recursion) or "bottom-up" (iterative recurrence), and ensure that when computingdp[i], all the subproblems on which it depends have already been computed.

In the climbing stairs problem, we adopt a bottom-up approach, starting fromi=3loop toi=n。

Classic example: Fibonacci sequence

The Fibonacci sequence is the most direct example of dynamic programming; its definition itself is the state transition equation.

Problem: find the nth Fibonacci numbernterm.F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)

Example

def fibonacci(n: int) -> int:
    """Compute Fibonacci numbers using dynamic programming"""
    if n < 2:
        return n
    # Space-optimized implementation
    prev, curr = 0, 1  # F(0), F(1)
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

# Test data
test_n = 10
print(f"The {test_n}th term of the Fibonacci sequence is: {fibonacci(test_n)}")  # Output: 55

Advanced example: coin change

This is a more typical problem that demonstrates optimal substructure.

Problem description: given an integer arraycoins, representing coins of different denominations, and an integeramount, representing the total amount. Calculate and return the minimum number of coins needed to make up the total amount. If no combination of coins can make up the total amount, return-1. You may assume that the quantity of each coin is unlimited.

Problem analysis and DP design

  1. Define state：dp[i]represents making up the total amountithe minimum number of coins needed.
  2. state transition equation: For the amounti, we can iterate over each denomination of coincoin. Ifcoin <= i, then making up the amountiOne possible way is: first make up the amounti - coin, then add one coincoindenomination of coin. What we need to find is the minimum among all possibilities. Therefore, the equation can be written as:dp[i] = min(dp[i], dp[i - coin] + 1), for all that satisfycoin <= iofcoin。
  3. Initial conditions：dp[0] = 0, making up amount 0 requires 0 coins. Othersdp[i]initialized to a very large number (e.g.amount + 1orfloat('inf')), meaning it cannot be made up for now.
  4. Computation order: bottom-up, fromi=1Compute up toi=amount。

Code implementation

Example

def coin_change(coins: list, amount: int) -> int:
    """Coin Change - Dynamic Programming"""
    # Initialize the dp array, where dp[i] represents the minimum number of coins for amount i
    # Set an unreachable initial value amount + 1
    dp = [amount + 1] * (amount + 1)
    dp[0] = 0  # When the amount is 0, 0 coins are needed
   
    # Outer loop: iterate through all amount states
    for i in range(1, amount + 1):
        # Inner loop: iterate through all coin choices
        for coin in coins:
            # If the current coin denomination is less than or equal to the current amount, consider using this coin
            if coin <= i:
                # State transition: dp[i] is the solution without using the current coin and
                # the smaller value among the solutions using the current coin (i.e., dp[i-coin] + 1)
                dp[i] = min(dp[i], dp[i - coin] + 1)
   
    # If dp[amount] has not been updated (still the initial value), it means the amount cannot be made up
    return dp[amount] if dp[amount] <= amount else -1

# Test data
coins = [1, 2, 5]
amount = 11
print(f"The minimum number of coins required to make up the total amount {amount} is: {coin_change(coins, amount)}")  # Output: 3 (5+5+1)

Practice exercises

Please try to solve the following problems independently to consolidate your understanding of dynamic programming:

Exercise 1: Maximum subarray sum

Given an integer arraynums, please find a contiguous subarray with the maximum sum, and return its maximum sum.

Example：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6.

Hint：

  • definitiondp[i]as "with theithe maximum sum of a contiguous subarray ending with the element".
  • state transition equation:dp[i] = max(nums[i], dp[i-1] + nums[i])。
  • The final answer is alldp[i]the maximum among them.

Exercise 2: Longest increasing subsequence

Given an integer arraynums, find the length of the longest strictly increasing subsequence.

Example：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4.

Hint：

  • definitiondp[i]as "with theithe length of the longest increasing subsequence ending with the number".
  • For eachi, need to traversejfrom0toi-1, ifnums[i] > nums[j], thendp[i] = max(dp[i], dp[j] + 1)。
  • Initially, eachdp[i]at least 1 (containing only itself).
other extensions