Skip to content

03-dynamic-programming.md

Latest commit

 

History

History
302 lines (230 loc) · 5.9 KB

03-dynamic-programming.md

File metadata and controls

302 lines (230 loc) · 5.9 KB

4.3 动态规划

📍 导航：返回目录 | 上一节：排序算法 | 下一节：一致性哈希

动态规划基础

核心思想

  • 最优子结构：大问题的最优解包含子问题的最优解
  • 重叠子问题：子问题被重复计算
  • 状态转移方程：递推关系

解题步骤

  1. 定义状态（dp数组含义）
  2. 初始化
  3. 状态转移方程
  4. 遍历顺序
  5. 返回结果

0-1背包问题

问题描述

n个物品，背包容量W，每个物品有重量w[i]和价值v[i]，求最大价值。

func knapsack(weights, values []int, capacity int) int {
    n := len(weights)
    // dp[i][j]: 前i个物品，容量为j的最大价值
    dp := make([][]int, n+1)
    for i := range dp {
        dp[i] = make([]int, capacity+1)
    }
    
    for i := 1; i <= n; i++ {
        for j := 0; j <= capacity; j++ {
            // 不选第i个物品
            dp[i][j] = dp[i-1][j]
            
            // 选第i个物品
            if j >= weights[i-1] {
                dp[i][j] = max(dp[i][j], 
                    dp[i-1][j-weights[i-1]] + values[i-1])
            }
        }
    }
    
    return dp[n][capacity]
}

空间优化（滚动数组）

func knapsackOptimized(weights, values []int, capacity int) int {
    dp := make([]int, capacity+1)
    
    for i := 0; i < len(weights); i++ {
        // 逆序遍历，避免重复使用
        for j := capacity; j >= weights[i]; j-- {
            dp[j] = max(dp[j], dp[j-weights[i]] + values[i])
        }
    }
    
    return dp[capacity]
}

时间复杂度：O(n × capacity)
空间复杂度：O(capacity)

最长公共子序列（LCS）

func longestCommonSubsequence(text1, text2 string) int {
    m, n := len(text1), len(text2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if text1[i-1] == text2[j-1] {
                dp[i][j] = dp[i-1][j-1] + 1
            } else {
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
            }
        }
    }
    
    return dp[m][n]
}

股票买卖问题

最多一次交易

func maxProfit(prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    minPrice := prices[0]
    maxProfit := 0
    
    for _, price := range prices {
        if price < minPrice {
            minPrice = price
        } else {
            maxProfit = max(maxProfit, price-minPrice)
        }
    }
    
    return maxProfit
}

无限次交易

func maxProfit2(prices []int) int {
    profit := 0
    
    for i := 1; i < len(prices); i++ {
        if prices[i] > prices[i-1] {
            profit += prices[i] - prices[i-1]
        }
    }
    
    return profit
}

最多k次交易

func maxProfit3(k int, prices []int) int {
    if len(prices) == 0 {
        return 0
    }
    
    n := len(prices)
    // dp[i][j][0]: 第i天，交易j次，不持股
    // dp[i][j][1]: 第i天，交易j次，持股
    dp := make([][][2]int, n)
    for i := range dp {
        dp[i] = make([][2]int, k+1)
    }
    
    // 初始化
    for j := 0; j <= k; j++ {
        dp[0][j][0] = 0
        dp[0][j][1] = -prices[0]
    }
    
    for i := 1; i < n; i++ {
        for j := 1; j <= k; j++ {
            dp[i][j][0] = max(dp[i-1][j][0], dp[i-1][j][1]+prices[i])
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j-1][0]-prices[i])
        }
    }
    
    return dp[n-1][k][0]
}

打家劫舍

func rob(nums []int) int {
    if len(nums) == 0 {
        return 0
    }
    if len(nums) == 1 {
        return nums[0]
    }
    
    // dp[i]: 偷前i个房子的最大金额
    prev2, prev1 := 0, nums[0]
    
    for i := 2; i <= len(nums); i++ {
        current := max(prev1, prev2+nums[i-1])
        prev2 = prev1
        prev1 = current
    }
    
    return prev1
}

爬楼梯

func climbStairs(n int) int {
    if n <= 2 {
        return n
    }
    
    prev2, prev1 := 1, 2
    
    for i := 3; i <= n; i++ {
        current := prev1 + prev2
        prev2 = prev1
        prev1 = current
    }
    
    return prev1
}

编辑距离

func minDistance(word1, word2 string) int {
    m, n := len(word1), len(word2)
    dp := make([][]int, m+1)
    for i := range dp {
        dp[i] = make([]int, n+1)
    }
    
    // 初始化
    for i := 0; i <= m; i++ {
        dp[i][0] = i
    }
    for j := 0; j <= n; j++ {
        dp[0][j] = j
    }
    
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                dp[i][j] = min(
                    dp[i-1][j]+1,   // 删除
                    dp[i][j-1]+1,   // 插入
                    dp[i-1][j-1]+1, // 替换
                )
            }
        }
    }
    
    return dp[m][n]
}

func min(nums ...int) int {
    result := nums[0]
    for _, num := range nums {
        if num < result {
            result = num
        }
    }
    return result
}

本章小结

关键要点：

  • ✅ 动态规划 = 递归 + 记忆化
  • ✅ 关键是找到状态转移方程
  • ✅ 空间优化：滚动数组
  • ✅ 背包、LCS、股票、打家劫舍是经典问题

扩展阅读

💡 思考题：

  1. 如何判断一个问题可以用动态规划？
  2. 背包问题为什么要逆序遍历？
  3. 如何优化动态规划的空间复杂度？

⏮️ 上一节：排序算法 | ⏭️ 下一节：一致性哈希