动态规划 (Dynamic Programming)

通过分解子问题和记忆化搜索，高效解决具有最优子结构性质的复杂问题

什么是动态规划？

动态规划是一种通过将复杂问题分解为重叠子问题，并存储子问题的解以避免重复计算的算法设计技术。它由 Richard Bellman 在 1950 年代提出，现已成为解决优化问题的核心方法。

💡 核心思想

记住过去，避免重复劳动 —— 将已计算的子问题结果存储起来，下次需要时直接查表获取。

🔄 动态规划

子问题重叠，需要存储中间结果

时间：O(n) 空间：O(n)

🔀 分治算法

子问题独立，无需存储中间结果

时间：O(n log n) 空间：O(log n)

🎯 贪心算法

每一步选择局部最优解

时间：O(n) 空间：O(1)

graph TD A[动态规划问题] --> B{问题类型} B --> C[线性 DP] B --> D[区间 DP] B --> E[树形 DP] B --> F[状态压缩 DP] B --> G[数位 DP] C --> C1[斐波那契] C --> C2[LIS] C --> C3[编辑距离] D --> D1[石子合并] D --> D2[回文子串] E --> E1[树的直径] E --> E2[树上背包] F --> F1[TSP 问题] F --> F2[集合覆盖] G --> G1[数字计数] G --> G2[特定数字统计] style A fill:#667eea,color:#fff style B fill:#764ba2,color:#fff style C fill:#48bb78,color:#fff style D fill:#ed8936,color:#fff style E fill:#f56565,color:#fff style F fill:#4299e1,color:#fff style G fill:#9f7aea,color:#fff

核心概念

1. 最优子结构 (Optimal Substructure)

问题的最优解包含其子问题的最优解。即可以通过子问题的最优解来构造原问题的最优解。

2. 重叠子问题 (Overlapping Subproblems)

在递归求解过程中，某些子问题会被重复计算多次。动态规划通过存储这些子问题的解来避免重复计算。

3. 状态转移方程 (State Transition Equation)

描述状态之间如何转换的数学表达式，是动态规划的核心。

状态转移方程通用形式

dp[state] = f(dp[prev_state_1], dp[prev_state_2], ...)

sequenceDiagram participant 问题分析 participant 状态定义 participant 转移方程 participant 初始化 participant 计算顺序 participant 返回结果问题分析->>状态定义：识别可变参数状态定义->>转移方程：找出状态间关系转移方程->>初始化：确定边界条件初始化->>计算顺序：确定遍历方向计算顺序->>返回结果：获取最终答案 Note over 问题分析，返回结果：动态规划解题五步法

斐波那契数列 - 入门经典

斐波那契数列是理解动态规划的最佳入门例子。传统递归方法存在大量重复计算，使用 DP 可以显著优化。

斐波那契 DP 可视化

F₀

F₁

点击"开始演示"查看计算过程

// 方法 1: 递归（低效，存在大量重复计算）
function fibRecursive(n) {
    if (n <= 1) return n;
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

// 方法 2: 记忆化递归（自顶向下）
function fibMemo(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n <= 1) return n;
    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

// 方法 3: 动态规划（自底向上）
function fibDP(n) {
    if (n <= 1) return n;
    const dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

// 方法 4: 空间优化（只保存前两个状态）
function fibOptimized(n) {
    if (n <= 1) return n;
    let prev2 = 0, prev1 = 1;
    for (let i = 2; i <= n; i++) {
        const current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
    return prev1;
}

console.log(fibOptimized(10)); // 55

# 方法 1: 递归（低效）
def fib_recursive(n):
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# 方法 2: 记忆化递归（自顶向下）
def fib_memo(n, memo=None):
    if memo is None:
        memo = {}
    if n in memo:
        return memo[n]
    if n <= 1:
        return n
    memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
    return memo[n]

# 方法 3: 动态规划（自底向上）
def fib_dp(n):
    if n <= 1:
        return n
    dp = [0, 1]
    for i in range(2, n + 1):
        dp.append(dp[i - 1] + dp[i - 2])
    return dp[n]

# 方法 4: 空间优化
def fib_optimized(n):
    if n <= 1:
        return n
    prev2, prev1 = 0, 1
    for i in range(2, n + 1):
        current = prev1 + prev2
        prev2, prev1 = prev1, current
    return prev1

print(fib_optimized(10))  # 55

package main

import "fmt"

// 方法 1: 递归（低效）
func fibRecursive(n int) int {
    if n <= 1 {
        return n
    }
    return fibRecursive(n-1) + fibRecursive(n-2)
}

// 方法 2: 记忆化递归
func fibMemo(n int, memo map[int]int) int {
    if val, ok := memo[n]; ok {
        return val
    }
    if n <= 1 {
        return n
    }
    memo[n] = fibMemo(n-1, memo) + fibMemo(n-2, memo)
    return memo[n]
}

// 方法 3: 动态规划（自底向上）
func fibDP(n int) int {
    if n <= 1 {
        return n
    }
    dp := make([]int, n+1)
    dp[0], dp[1] = 0, 1
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2]
    }
    return dp[n]
}

// 方法 4: 空间优化
func fibOptimized(n int) int {
    if n <= 1 {
        return n
    }
    prev2, prev1 := 0, 1
    for i := 2; i <= n; i++ {
        current := prev1 + prev2
        prev2, prev1 = prev1, current
    }
    return prev1
}

func main() {
    fmt.Println(fibOptimized(10)) // 55
}

方法	时间复杂度	空间复杂度	特点
递归	O(2ⁿ)	O(n)	大量重复计算，不推荐
记忆化递归	O(n)	O(n)	自顶向下，易理解
动态规划	O(n)	O(n)	自底向上，无递归开销
空间优化	O(n)	O(1)	最优解，推荐

背包问题 (Knapsack Problem)

给定一组物品，每件物品有重量和价值，在限定的重量内选择物品使总价值最大。这是动态规划最经典的应用之一。

问题描述

有一个容量为 W 的背包，和 n 个物品，第 i 个物品的重量为 weight[i]，价值为 value[i]。问：如何选择物品装入背包，使得总价值最大？

输入: weight = [1, 2, 3, 4, 5], value = [10, 15, 20, 25, 30], capacity = 10

输出: 60

解释: 选择重量为 1,2,3,4 的物品，总重量 10，总价值 10+15+20+25=60

0-1 背包状态转移方程

dp[i][w] = max(dp[i-1][w], value[i-1] + dp[i-1][w-weight[i-1]])

其中 dp[i][w] 表示前 i 个物品，背包容量为 w 时的最大价值

graph LR A[背包问题] --> B[0-1 背包] A --> C[完全背包] A --> D[多重背包] B --> B1[每件物品选或不选] B --> B2[倒序遍历容量] C --> C1[每件物品可选多次] C --> C2[正序遍历容量] D --> D1[每件物品有数量限制] D --> D2[二进制拆分优化] style A fill:#667eea,color:#fff style B fill:#48bb78,color:#fff style C fill:#ed8936,color:#fff style D fill:#f56565,color:#fff

// 0-1 背包问题 - 二维 DP
function knapsack2D(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(n + 1).fill(null).map(() => Array(capacity + 1).fill(0));

    for (let i = 1; i <= n; i++) {
        for (let w = 1; w <= capacity; w++) {
            if (weights[i - 1] <= w) {
                dp[i][w] = Math.max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                );
            } else {
                dp[i][w] = dp[i - 1][w];
            }
        }
    }

    return dp[n][capacity];
}

// 空间优化版本 - 一维 DP
function knapsack1D(weights, values, capacity) {
    const n = weights.length;
    const dp = Array(capacity + 1).fill(0);

    for (let i = 0; i < n; i++) {
        // 倒序遍历，避免重复使用同一物品
        for (let w = capacity; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }

    return dp[capacity];
}

const weights = [1, 2, 3, 4, 5];
const values = [10, 15, 20, 25, 30];
const capacity = 10;
console.log(knapsack1D(weights, values, capacity)); // 60

# 0-1 背包问题 - 二维 DP
def knapsack_2d(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i - 1] <= w:
                dp[i][w] = max(
                    values[i - 1] + dp[i - 1][w - weights[i - 1]],
                    dp[i - 1][w]
                )
            else:
                dp[i][w] = dp[i - 1][w]

    return dp[n][capacity]

# 空间优化版本 - 一维 DP
def knapsack_1d(weights, values, capacity):
    n = len(weights)
    dp = [0] * (capacity + 1)

    for i in range(n):
        # 倒序遍历，避免重复使用同一物品
        for w in range(capacity, weights[i] - 1, -1):
            dp[w] = max(dp[w], values[i] + dp[w - weights[i]])

    return dp[capacity]

weights = [1, 2, 3, 4, 5]
values = [10, 15, 20, 25, 30]
capacity = 10
print(knapsack_1d(weights, values, capacity))  # 60

package main

import "fmt"

// 0-1 背包问题 - 空间优化版本
func knapsack(weights, values []int, capacity int) int {
    n := len(weights)
    dp := make([]int, capacity+1)

    for i := 0; i < n; i++ {
        // 倒序遍历，避免重复使用同一物品
        for w := capacity; w >= weights[i]; w-- {
            if values[i]+dp[w-weights[i]] > dp[w] {
                dp[w] = values[i] + dp[w-weights[i]]
            }
        }
    }

    return dp[capacity]
}

func main() {
    weights := []int{1, 2, 3, 4, 5}
    values := []int{10, 15, 20, 25, 30}
    capacity := 10
    fmt.Println(knapsack(weights, values, capacity)) // 60
}

最长递增子序列 (Longest Increasing Subsequence)

找到一个序列中最长的严格递增子序列的长度。子序列不要求连续，但必须保持原序列中的相对顺序。

问题描述

给定一个无序的整数数组，找到其中最长递增子序列的长度。

输入: [10, 9, 2, 5, 3, 7, 101, 18]

输出: 4

解释: 最长递增子序列是 [2, 3, 7, 18] 或 [2, 3, 7, 101]

LIS 状态转移方程

dp[i] = max(dp[j] + 1), 其中 0 ≤ j < i 且 nums[j] < nums[i]

其中 dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度

// 方法 1: 动态规划 O(n²)
function lengthOfLIS(nums) {
    if (nums.length === 0) return 0;

    const dp = Array(nums.length).fill(1);
    let maxLength = 1;

    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLength = Math.max(maxLength, dp[i]);
    }

    return maxLength;
}

// 方法 2: 贪心 + 二分查找 O(n log n)
function lengthOfLISOptimized(nums) {
    const tails = [];
    
    for (const num of nums) {
        // 二分查找第一个 >= num 的位置
        let left = 0, right = tails.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (tails[mid] < num) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        tails[left] = num;
    }
    
    return tails.length;
}

console.log(lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18])); // 4
console.log(lengthOfLISOptimized([10, 9, 2, 5, 3, 7, 101, 18])); // 4

# 方法 1: 动态规划 O(n²)
def length_of_lis(nums):
    if not nums:
        return 0
    
    dp = [1] * len(nums)
    max_length = 1
    
    for i in range(1, len(nums)):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)
        max_length = max(max_length, dp[i])
    
    return max_length

# 方法 2: 贪心 + 二分查找 O(n log n)
def length_of_lis_optimized(nums):
    tails = []
    
    for num in nums:
        # 二分查找第一个 >= num 的位置
        left, right = 0, len(tails)
        while left < right:
            mid = (left + right) // 2
            if tails[mid] < num:
                left = mid + 1
            else:
                right = mid
        if left < len(tails):
            tails[left] = num
        else:
            tails.append(num)
    
    return len(tails)

print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))  # 4
print(length_of_lis_optimized([10, 9, 2, 5, 3, 7, 101, 18]))  # 4

package main

import "fmt"

// 方法 1: 动态规划 O(n²)
func lengthOfLIS(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    
    dp := make([]int, len(nums))
    for i := range dp {
        dp[i] = 1
    }
    maxLength := 1
    
    for i := 1; i < len(nums); i++ {
        for j := 0; j < i; j++ {
            if nums[j] < nums[i] {
                if dp[j]+1 > dp[i] {
                    dp[i] = dp[j] + 1
                }
            }
        }
        if dp[i] > maxLength {
            maxLength = dp[i]
        }
    }
    
    return maxLength
}

// 方法 2: 贪心 + 二分查找 O(n log n)
func lengthOfLISOptimized(nums []int) int {
    tails := []int{}
    
    for _, num := range nums {
        // 二分查找第一个 >= num 的位置
        left, right := 0, len(tails)
        for left < right {
            mid := (left + right) / 2
            if tails[mid] < num {
                left = mid + 1
            } else {
                right = mid
            }
        }
        if left < len(tails) {
            tails[left] = num
        } else {
            tails = append(tails, num)
        }
    }
    
    return len(tails)
}

func main() {
    fmt.Println(lengthOfLIS([]int{10, 9, 2, 5, 3, 7, 101, 18}))  // 4
    fmt.Println(lengthOfLISOptimized([]int{10, 9, 2, 5, 3, 7, 101, 18}))  // 4
}

编辑距离 (Edit Distance)

给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数。可以对一个单词进行插入、删除或替换一个字符的操作。

编辑距离状态转移方程

dp[i][j] =
dp[i-1][j-1] if word1[i] == word2[j]
1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) otherwise

分别对应：删除、插入、替换三种操作

function minDistance(word1, word2) {
    const m = word1.length, n = word2.length;
    const dp = Array(m + 1).fill(null).map(() => Array(n + 1).fill(0));

    // 初始化边界
    for (let i = 0; i <= m; i++) dp[i][0] = i;
    for (let j = 0; j <= n; j++) dp[0][j] = j;

    // 状态转移
    for (let i = 1; i <= m; i++) {
        for (let j = 1; j <= n; j++) {
            if (word1[i - 1] === word2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + Math.min(
                    dp[i - 1][j],      // 删除
                    dp[i][j - 1],      // 插入
                    dp[i - 1][j - 1]   // 替换
                );
            }
        }
    }

    return dp[m][n];
}

console.log(minDistance("horse", "ros")); // 3
console.log(minDistance("intention", "execution")); // 5

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    # 初始化边界
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j

    # 状态转移
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i - 1] == word2[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],      # 删除
                    dp[i][j - 1],      # 插入
                    dp[i - 1][j - 1]   # 替换
                )

    return dp[m][n]

print(minDistance("horse", "ros"))  # 3
print(minDistance("intention", "execution"))  # 5

动态规划解题步骤

1. 定义状态

2. 状态转移

3. 初始化

4. 遍历顺序

5. 返回结果

📋 五步解题法详解

定义状态：确定 dp[i] 或 dp[i][j] 表示什么含义
状态转移：找出状态之间的关系，写出状态转移方程
初始化：确定基础情况（边界条件）的初始值
遍历顺序：确定状态计算的顺序（自顶向下或自底向上）
返回结果：确定最终要返回的值（dp[n]、dp[n-1]、max(dp) 等）

常见动态规划问题类型

类型	典型问题	状态定义	时间复杂度
线性 DP	斐波那契、爬楼梯	dp[i] 表示前 i 个状态	O(n)
子序列	LIS、LCS、编辑距离	dp[i][j] 表示两个序列的状态	O(n²)
背包问题	0-1 背包、完全背包	dp[i][w] 表示前 i 个物品容量 w	O(nW)
区间 DP	石子合并、回文子串	dp[i][j] 表示区间 [i,j] 的状态	O(n³)
树形 DP	树的直径、树上背包	dp[u] 表示以 u 为根的子树	O(n)
状态压缩	TSP、集合覆盖	dp[mask] 表示状态 mask	O(n²·2ⁿ)