Jeskson-微服务分布式

动态规划 (Dynamic Programming)

# 动态规划 (Dynamic Programming)

# 📋 学习目标

  • 理解动态规划的核心思想
  • 掌握状态定义和转移方程
  • 熟练运用记忆化搜索和递推
  • 能够优化空间复杂度

# 🎯 核心概念

# 什么是动态规划

动态规划是一种通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

# 适用条件

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：递归算法反复求解相同的子问题
  3. 无后效性：子问题的解一旦确定，不会再改变

# 解题步骤

  1. 定义状态：确定dp数组的含义
  2. 状态转移：找出状态间的递推关系
  3. 初始化：确定边界条件
  4. 计算顺序：确定计算的顺序
  5. 返回结果：从dp数组中得到答案

# 🏗️ DP分类

# 线性DP

状态转移呈线性关系

# 经典问题

  • 斐波那契数列
  • 爬楼梯
  • 最大子数组和
  • 最长递增子序列

# 区间DP

在区间上进行动态规划

# 经典问题

  • 最长回文子串
  • 矩阵链乘法
  • 石子合并

# 背包DP

资源分配类问题

# 经典问题

  • 0-1背包
  • 完全背包
  • 多重背包
  • 分组背包

# 树形DP

在树上进行动态规划

# 经典问题

  • 树的直径
  • 树上最大独立集
  • 树的重心

# 状态机DP

状态之间有转移限制

# 经典问题

  • 买卖股票
  • 打家劫舍
  • 状态压缩DP

# 🎯 经典题目详解

# 1. 爬楼梯 🟢

题目：假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。有多少种不同的方法可以爬到楼顶？

状态定义：dp[i] = 爬到第i阶的方法数

状态转移：dp[i] = dp[i-1] + dp[i-2]

代码实现：

public int climbStairs(int n) {
    if (n <= 2) return n;
    
    int[] dp = new int[n + 1];
    dp[1] = 1;
    dp[2] = 2;
    
    for (int i = 3; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

空间优化：

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

# 2. 最长递增子序列 🟡

题目：给定一个无序的整数数组，找到其中最长上升子序列的长度。

状态定义：dp[i] = 以nums[i]结尾的最长递增子序列长度

状态转移：dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]

代码实现：

public int lengthOfLIS(int[] nums) {
    if (nums.length == 0) return 0;
    
    int[] dp = new int[nums.length];
    Arrays.fill(dp, 1);
    int maxLen = 1;
    
    for (int i = 1; i < nums.length; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
        maxLen = Math.max(maxLen, dp[i]);
    }
    
    return maxLen;
}

时间复杂度：O(n²)
空间复杂度：O(n)

# 3. 0-1背包问题 🟡

题目：给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W，求能装入背包的最大价值。

状态定义：dp[i][w] = 前i个物品，背包容量为w时的最大价值

状态转移：

贪心算法