动态规划

动态规划

lx 11 2025-05-27

动态规划

动态规划基础

动态规划(Dynamic Programming)是一种分阶段求解问题的思想，它通过将原问题分解为相对简单的子问题的方式来求解复杂问题。

动态规划适用条件

  1. 最优子结构：问题的最优解包含子问题的最优解
  2. 重叠子问题：递归算法会重复求解相同的子问题

Java实现案例

1. 斐波那契数列

递归解法（非动态规划）

public int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

动态规划解法（自底向上）

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

优化空间复杂度版本

public int fib(int n) {
    if (n <= 1) return n;
  
    int prev1 = 1;  // f(n-1)
    int prev2 = 0;  // f(n-2)
  
    for (int i = 2; i <= n; i++) {
        int current = prev1 + prev2;
        prev2 = prev1;
        prev1 = current;
    }
  
    return prev1;
}

2. 爬楼梯问题

问题描述：每次可以爬1或2个台阶，有多少种不同的方法可以爬到第n阶？

动态规划解法

public int climbStairs(int n) {
    if (n == 1) return 1;
  
    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 == 1) return 1;
  
    int first = 1;
    int second = 2;
  
    for (int i = 3; i <= n; i++) {
        int third = first + second;
        first = second;
        second = third;
    }
  
    return second;
}

3. 最长公共子序列(LCS)

问题描述：给定两个字符串，找出它们最长的公共子序列的长度。

动态规划解法

public int longestCommonSubsequence(String text1, String text2) {
    int m = text1.length(), n = text2.length();
    int[][] dp = new int[m + 1][n + 1];
  
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
  
    return dp[m][n];
}

4. 0-1背包问题

问题描述：给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择物品使得总价值最大。

动态规划解法

public int knapsack(int W, int[] weights, int[] values, int n) {
    int[][] dp = new int[n + 1][W + 1];
  
    for (int i = 1; i <= n; i++) {
        for (int w = 1; w <= W; 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][W];
}

空间优化版本（一维数组）

public int knapsack(int W, int[] weights, int[] values, int n) {
    int[] dp = new int[W + 1];
  
    for (int i = 0; i < n; i++) {
        for (int w = W; w >= weights[i]; w--) {
            dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
        }
    }
  
    return dp[W];
}

动态规划解题步骤总结

  1. 定义状态：明确dp数组或变量表示的含义
  2. 确定状态转移方程：找出如何从子问题的解得到当前问题的解
  3. 初始化边界条件：确定最简单子问题的解
  4. 确定计算顺序：通常是自底向上或自顶向下
  5. 考虑空间优化：看是否能减少空间复杂度

通过以上案例和步骤，可以更好地理解和应用动态规划算法解决实际问题。

LeetCode中等