YouTip

## Dynamic Programming\n\nDynamic Programming (DP for short) is a method used in mathematics, management science, computer science, economics, and bioinformatics to solve complex problems by breaking them down into relatively simpler subproblems.\n\n> Imagine you are climbing a staircase with `n` steps. Each time you can climb `1` or `2` steps.\n> \n> \n> How many distinct ways can you climb to the top?\n> \n> \n> If you start thinking from the top-level goal (step `n`), it might seem complicated.\n> \n> \n> But let's change our perspective: **to reach step `n`, you can only come from step `n-1` with one step, or from step `n-2` with two steps**. Therefore, the number of ways to reach step `n` equals the number of ways to reach step `n-1` plus the number of ways to reach step `n-2`.\n\nThis method of **breaking a large problem into several overlapping subproblems, and efficiently solving the original problem by storing the solutions to subproblems to avoid redundant calculations** is called Dynamic Programming (DP for short).\n\n### Core Idea\n\nThe core of dynamic programming is **remembering solutions that have already been computed**.\n\nDynamic programming is typically used to solve problems with the following properties:\n\n1. **Overlapping Subproblems**: During recursive solving, the same subproblem is computed multiple times.\n2. **Optimal Substructure**: An optimal solution to a problem contains optimal solutions to its subproblems.\n\nWe can use a simple flowchart to understand the problem-solving approach of dynamic programming:\n\n[!(#)](#)\n\nThe above figure shows the typical steps to solve a dynamic programming problem: starting from defining the problem, finding the subproblem structure through analysis, then formalizing it with states and state transition equations, and finally obtaining the answer through clear initial conditions and computation order.\n\n* * *\n\n## From Recursion to Dynamic Programming: Climbing Stairs Problem\n\nLet's use the classic **"Climbing Stairs"** problem to experience the optimization process from recursion to dynamic programming.\n\n### Problem Description\n\nSuppose you are climbing stairs. It takes `n` steps to reach the top. Each time you can climb `1` or `2` steps. How many distinct ways can you climb to the top?\n\n### Method 1: Brute Force Recursion (Inefficient)\n\nBased 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`.\n\n## Example\n\ndef climb_stairs_recursive(n: int) ->int:\n\n"""Recursive solution"""\n\nif n ==1:\n\nreturn 1\n\nif n ==2:\n\nreturn 2\n\nreturn climb_stairs_recursive(n - 1) + climb_stairs_recursive(n - 2)\n\n# Test\n\nprint(f"Number of ways to climb to the 5th step (Recursion): {climb_stairs_recursive(5)}")# Output: 8\n\n**Disadvantage Analysis**: This recursion involves a large amount of redundant computation. For example, computing `f(5)` requires `f(4)` and `f(3)`, and computing `f(4)` requires `f(3)` and `f(2)`, so `f(3)` is computed twice. When `n` is large, the time complexity is exponential `O(2^n)`, which is extremely inefficient.\n\n### Method 2: Memoized Recursion (Top-Down)\n\nWe can use an array ("memo") to store already computed results to avoid redundant calculations.\n\n## Example\n\ndef climb_stairs_memo(n: int) ->int:\n\n"""Memoized recursion (top-down)"""\n\n# Initialize memo, -1 means not yet computed\n\n memo = * (n + 1)\n\ndef helper(x: int) ->int:\n\n# Base cases\n\nif x ==1:\n\nreturn 1\n\nif x ==2:\n\nreturn 2\n\n# If already computed, return result directly\n\nif memo!= -1:\n\nreturn memo\n\n# Otherwise, compute and store in memo\n\n memo= helper(x - 1) + helper(x - 2)\n\nreturn memo\n\nreturn helper(n)\n\nprint(f"Number of ways to climb to the 5th step (Memoization): {climb_stairs_memo(5)}")# Output: 8\n\nThe time complexity of this method is reduced to `O(n)`, because each subproblem is computed only once. The space complexity is `O(n)`. This is already a dynamic programming idea, called **"top-down"** or **"memoization"**.\n\n### Method 3: Iterative Array (Bottom-Up, Standard DP)\n\nWe start directly from the smallest subproblem and iteratively build up to the original problem. Usually an array `dp` is used to store states.\n\n## Example\n\ndef climb_stairs_dp(n: int) ->int:\n\n"""Dynamic programming (bottom-up)"""\n\nif n int:\n\n"""Dynamic programming (space optimized)"""\n\nif n In the climbing stairs problem, we define `dp` as "the total number of ways to climb to step `i`".\n\n### Step 2: Determine State Transition Equation\n\nFind the relationship between `dp` and previous states (such as `dp`, `dp`). This is the core and difficulty of dynamic programming.\n\n> In the climbing stairs problem, the state transition equation is: `dp = dp + dp`.\n\n### Step 3: Determine Initial Conditions (Base Case)\n\nThe smallest, indivisible subproblems' solutions. This is the starting point of iteration and must be manually defined.\n\n> In the climbing stairs problem, the initial conditions are: `dp = 1`, `dp = 2`.\n\n### Step 4: Determine Computation Order and Calculate\n\nDetermine whether to use "top-down" (memoized recursion) or "bottom-up" (iterative), and ensure that when computing `dp`, all subproblems it depends on have already been computed.\n\n> In the climbing stairs problem, we use bottom-up, looping from `i=3` to `i=n`.\n\n* * *\n\n## Classic Case: Fibonacci Sequence\n\nThe Fibonacci sequence is the most direct example of dynamic programming, as its definition itself is a state transition equation.\n\n**Problem**: Find the `n`th term of the Fibonacci sequence. `F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2) (n>=2)`\n\n## Example\n\ndef fibonacci(n: int) ->int:\n\n"""Dynamic programming for Fibonacci sequence"""\n\nif n <2:\n\nreturn n\n\n# Space optimized version\n\n prev, curr =0,1# F(0), F(1)\n\nfor _ in range(2, n + 1):\n\n prev, curr = curr, prev + curr\n\nreturn curr\n\n# Test data\n\n test_n =10\n\nprint(f"The ...th term of the Fibonacci sequence {test_n} term is: {fibonacci(test_n)}")# Output: 55\n\n* * *\n\n## Advanced Case: Coin Change\n\nThis is a more typical problem demonstrating optimal substructure.\n\n**Problem Description**: Given an integer array `coins` representing different denominations of coins, and an integer `amount` representing a total amount of money, calculate and return the fewest number of coins needed to make up that amount. If no combination of coins can make up the amount, return `-1`. You may assume that you have an infinite number of each kind of coin.\n\n### Problem Analysis and DP Design\n\n1. **Define State**: `dp` represents the minimum number of coins needed to make up amount `i`.\n2. **State Transition Equation**: For amount `i`, we can iterate through each coin denomination `coin`. If `coin <= i`, then one possible way to make up amount `i` is: first make up amount `i - coin`, then add one coin of denomination `coin`. We want the minimum among all possibilities. Therefore, the equation can be written as: `dp = min(dp, dp + 1)`, for all `coin` satisfying `coin int:\n\n"""Coin change - dynamic programming"""\n\n# Initialize dp array, dp represents minimum coins for amount i\n\n# Set an initially unreachable value amount + 1\n\n dp =[amount + 1] * (amount + 1)\n\n dp=0# Amount 0 needs 0 coins\n\n# Outer loop: iterate through all amount states\n\nfor i in range(1, amount + 1):\n\n# Inner loop: iterate through all coin choices\n\nfor coin in coins:\n\n# If current coin denomination is less than or equal to current amount, consider using this coin\n\nif coin <= i:\n\n# State transition: dp is the minimum of not using current coin\n\n# and using current coin (i.e., dp + 1)\n\n dp=min(dp, dp + 1)\n\n# If dp was not updated (still initial value), it means unreachable\n\nreturn dpif dp nums`, then `dp = max(dp, dp + 1)`.\n* Initially, each `dp` is at least 1 (containing only itself).