简介

       动态规划（DP）是计算机科学和数学中一种强大的优化技术，核心思想是将复杂问题拆解为若干个重叠的子问题，通过存储子问题的解（即 “记忆化”）来避免重复计算，最终高效求解原问题。它广泛应用于路径规划、资源分配、序列匹配等场景，是算法面试中的高频考点。

---

动态规划的核心思想

       动态规划的本质是 “以空间换时间”，其有效性依赖于两个关键前提，以及两个核心操作。

关键问题：

1. 重叠子问题（Overlapping Subproblems）：
          原问题的解依赖于多个子问题的解，且这些子问题会被重复计算。
          例如：计算斐波那契数列时，fib(5) = fib(4) + fib(3)，而fib(4) = fib(3) + fib(2)——fib(3)被重复计算了两次，这就是 “重叠子问题”。
2. 最优子结构（Optimal Substructure）：原问题的最优解可以由子问题的最优解推导得出。         例如：最短路径问题中，从 A 到 C 的最短路径 = （A 到 B 的最短路径）+（B 到 C 的最短路径），即原问题的最优解由子问题的最优解构成。

核心操作

1. 状态定义（State Definition）：
          将问题抽象为一个 “状态”，用变量描述子问题的核心信息（如dp[i]表示 “前 i 个元素的最优解”）。
          状态定义是 DP 的灵魂，定义不当会导致无法推导或复杂度飙升。
2. 状态转移方程（State Transition Equation）：
          描述如何从 “子问题的状态” 推导 “当前问题的状态”（如dp[i] = dp[i-1] + dp[i-2]）。
          状态转移方程是 DP 的骨架，直接决定了算法的逻辑。

---

动态规划的实现方式

       首先我们需要明确一点，根据 “子问题解的存储方式”，动态规划主要分为两种实现形式，二者本质相同，仅计算顺序和存储的逻辑有略微差异。

自顶向下（Top-down）：记忆化搜索

• 思路：从原问题出发，递归拆解为子问题；计算子问题时，先检查是否已存储结果（记忆化），若有则直接使用，若无则计算并存储。
• 核心：递归 + 缓存（数组或哈希表），符合人类 “从大到小” 的思考习惯。
• 示例：计算斐波那契数列（fib(n) = fib(n-1) + fib(n-2)）

  import java.util.HashMap;
  import java.util.Map;
  
  public class Fibonacci {
      // 计算斐波那契数列的自顶向下方法
      public static int fibTopDown(int n, Map<Integer, Integer> memo) {
          // base case：终止条件
          if (n <= 2) {
              return 1;
          }
          // 若子问题已计算，直接返回缓存结果
          if (memo.containsKey(n)) {
              return memo.get(n);
          }
          // 计算子问题并缓存
          int result = fibTopDown(n - 1, memo) + fibTopDown(n - 2, memo);
          memo.put(n, result);
          return result;
      }
      
      public static void main(String[] args) {
          // 初始化记忆化缓存
          Map<Integer, Integer> memo = new HashMap<>();
          // 计算并打印斐波那契数列的第10项
          System.out.println(fibTopDown(10, memo));  // 输出55
      }
  }
  

  自底向上（Bottom-up）：递推（DP 数组）

• 思路：从最小的子问题（base case）出发，按顺序计算到原问题；用数组（或变量）存储子问题的解，直接通过循环递推。
• 核心：循环 + DP 数组，避免递归栈溢出，效率更高。
• 示例：同样计算斐波那契数列

  public class FibonacciBottomUp {
      public static int fibBottomUp(int n) {
          // base case：最小子问题的解
          if (n <= 2) {
              return 1;
          }
          // 初始化DP数组，存储子问题解
          int[] dp = new int[n + 1];
          dp[1] = 1;
          dp[2] = 1;
          // 从子问题递推到原问题
          for (int i = 3; i <= n; i++) {
              dp[i] = dp[i - 1] + dp[i - 2];  // 状态转移方程
          }
          return dp[n];
      }
      
      public static void main(String[] args) {
          System.out.println(fibBottomUp(10));  // 输出55
      }
  }
      

---

动态规划的解题步骤（通用框架）

步骤 1：明确问题目标，确定是否满足 DP 前提

       先分析问题是否存在 “重叠子问题” 和 “最优子结构”。例如：

• 问题：“求最长递增子序列（LIS）”—— 满足最优子结构（LIS 的子序列也是递增的）和重叠子问题（不同序列可能共享子序列的长度），可用 DP。
• 问题：“求二叉树的前序遍历”—— 无重叠子问题，无需 DP（递归或迭代即可）。

步骤 2：定义 DP 状态（最关键一步）

         状态定义需回答两个问题：

• DP 数组的维度：1 维（如序列问题）、2 维（如矩阵、两个序列的匹配问题）或更高维（如三维 DP）。
• DP [i]（或 DP [i][j]）的含义：用简洁的语言描述 “当前状态代表的子问题”，需包含核心信息。

       示例：最长递增子序列（LIS）问题

• 问题：给定数组nums，求长度最长的严格递增子序列的长度（子序列不要求连续）。
• 状态定义：dp[i]表示 “以nums[i]为最后一个元素的最长递增子序列的长度”。（若定义为 “前 i 个元素的 LIS 长度”，则无法推导转移方程，因为无法确定子序列是否包含nums[i]）。

步骤 3：推导状态转移方程

       根据状态定义，分析 “当前状态如何由前一个 / 多个状态推导而来”，需结合问题的约束条件。

       示例：LIS 的状态转移方程对于dp[i]（以nums[i]结尾的 LIS 长度）：

• 若nums[j] < nums[i]（j < i），则nums[i]可接在nums[j]的子序列后，此时dp[i] = dp[j] + 1；
• 需遍历所有j < i，取满足条件的dp[j] + 1的最大值；
• 若没有j < i满足nums[j] < nums[i]，则dp[i] = 1（子序列仅包含nums[i]本身）。

       因此，转移方程为：dp[i] = max(dp[j] + 1) for all j < i and nums[j] < nums[i]，若无可选j，则dp[i] = 1。

步骤 4：确定 Base Case（初始状态）

       Base Case 是最小子问题的解，是递推的起点，需明确初始化 DP 数组的值。

       示例：LIS 的 Base Case对于每个i，以nums[i]为唯一元素的子序列长度为 1，因此dp[i] = 1（初始化时所有元素为 1）。

步骤 5：计算最终结果（可选）

       部分问题的最终结果是 DP 数组的最后一个元素（如斐波那契数列的dp[n]），部分问题需遍历 DP 数组取最大值（如求解递增子序列 LIS 的结果是max(dp)）。

/**
 * 求解递增子序列
 */
public class LongestIncreasingSubsequence {
    public static int lengthOfLIS(int[] nums) {
        // 处理空数组情况
        if (nums == null || nums.length == 0) {
            return 0;
        }        
        int n = nums.length;
        // dp[i]表示以nums[i]为最后一个元素的最长递增子序列的长度
        int[] dp = new int[n];
        // Base Case：所有元素初始化为1（每个元素自身构成长度为1的子序列）
        for (int i = 0; i < n; i++) {
            dp[i] = 1;
        }        
        // 计算每个位置的最长递增子序列长度
        for (int i = 1; i < n; i++) {
            // 检查所有之前的元素
            for (int j = 0; j < i; j++) {
                // 如果之前的元素小于当前元素，说明可以构成更长的子序列
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }        
        // 找出dp数组中的最大值，即为最长递增子序列的长度
        int maxLength = 0;
        for (int length : dp) {
            maxLength = Math.max(maxLength, length);
        }    
        return maxLength;
    }
    
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lengthOfLIS(nums));  // 输出4
    }
}
    

---

四、常见动态规划问题分类与示例

       DP 问题可按场景分类，不同类别有相似的状态定义和转移逻辑，掌握分类可快速建立解题思路：

1. 一维 DP：序列类问题

       特点：问题基于线性序列（如数组、字符串），状态用 1 维数组表示（dp[i]对应前 i 个元素的子问题）。典型问题：斐波那契数列、爬楼梯、LIS（上述文章中有具体的代码）、打家劫舍。

       示例：打家劫舍

• 问题：你是一个小偷，不能偷相邻的房子，求能偷到的最大金额。
• 状态定义：dp[i]表示 “偷前 i 个房子的最大金额”。
• 转移方程：偷第 i 个房子：dp[i] = dp[i-2] + nums[i-1]（第 i 个房子对应nums[i-1]，且不能偷第 i-1 个）；不偷第 i 个房子：dp[i] = dp[i-1]；因此dp[i] = max(dp[i-1], dp[i-2] + nums[i-1])。
• Base Case：dp[0] = 0（偷 0 个房子），dp[1] = nums[0]（偷 1 个房子）。

  public class HouseRobber {
      public static int rob(int[] nums) {
          // 处理边界情况
          if (nums == null || nums.length == 0) {
              return 0;
          }
          if (nums.length == 1) {
              return nums[0];
          }        
          int n = nums.length;
          // dp[i]表示偷前i个房子的最大金额
          int[] dp = new int[n + 1];        
          // Base Case
          dp[0] = 0;          // 偷0个房子，金额为0
          dp[1] = nums[0];    // 偷1个房子，金额为第一个房子的价值        
          // 状态转移：对于第i个房子，有两种选择
          // 1. 不偷：最大金额等于偷前i-1个房子的金额
          // 2. 偷：最大金额等于偷前i-2个房子的金额加上当前房子的价值
          // 取两种选择的最大值
          for (int i = 2; i <= n; i++) {
              dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
          }        
          return dp[n];
      }    
  
      // 空间优化版本：只需要保存前两个状态
      public static int robOptimized(int[] nums) {
          if (nums == null || nums.length == 0) {
              return 0;
          }
          if (nums.length == 1) {
              return nums[0];
          }       
          int prevPrev = 0;   // 对应dp[i-2]
          int prev = nums[0]; // 对应dp[i-1]        
          for (int i = 2; i <= nums.length; i++) {
              int current = Math.max(prev, prevPrev + nums[i - 1]);
              prevPrev = prev;
              prev = current;
          }        
          return prev;
      }
      
      public static void main(String[] args) {
          int[] nums1 = {1, 2, 3, 1};
          System.out.println(rob(nums1));          // 输出4
          System.out.println(robOptimized(nums1)); // 输出4
          int[] nums2 = {2, 7, 9, 3, 1};
          System.out.println(rob(nums2));          // 输出12
          System.out.println(robOptimized(nums2)); // 输出12
      }
  }  

2. 二维 DP：多序列 / 矩阵类问题

       特点：问题涉及两个序列（如字符串匹配）或矩阵（如路径问题），状态用 2 维数组表示（dp[i][j]对应两个序列的前 i、j 个元素，或矩阵的 (i,j) 位置）。典型问题：最长公共子序列（LCS）、编辑距离、不同路径、最小路径和。

       示例：最长公共子序列（LCS）

• 问题：给定两个字符串s1和s2，求最长公共子序列的长度（子序列不要求连续）。
• 状态定义：dp[i][j]表示 “s1的前 i 个字符和s2的前 j 个字符的 LCS 长度”。
• 转移方程：若s1[i-1] == s2[j-1]（当前字符相同）：dp[i][j] = dp[i-1][j-1] + 1（LCS 长度 + 1）；若s1[i-1] != s2[j-1]（当前字符不同）：dp[i][j] = max(dp[i-1][j], dp[i][j-1])（取 “去掉 s1 的 i” 或 “去掉 s2 的 j” 的最大值）。
• Base Case：dp[i][0] = 0（s2 为空），dp[0][j] = 0（s1 为空）。

  public class LongestCommonSubsequence {
      public static int longestCommonSubsequence(String text1, String text2) {
          int m = text1.length();
          int n = text2.length();
          
          // 创建二维DP数组，dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度
          int[][] dp = new int[m + 1][n + 1];
          
          // 填充DP数组
          for (int i = 1; i <= m; i++) {
              for (int j = 1; j <= n; j++) {
                  // 如果当前字符相同，则LCS长度为前i-1和j-1的LCS长度加1
                  if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                      dp[i][j] = dp[i - 1][j - 1] + 1;
                  } else {
                      // 如果当前字符不同，则取"去掉text1的第i个字符"或"去掉text2的第j个字符"的最大值
                      dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                  }
              }
          }
          
          // 返回两个字符串的LCS长度
          return dp[m][n];
      }
      
      public static void main(String[] args) {
          String text1 = "abcde";
          String text2 = "ace";
          System.out.println(longestCommonSubsequence(text1, text2));  // 输出3（对应子序列"ace"）
          
          String text3 = "abc";
          String text4 = "def";
          System.out.println(longestCommonSubsequence(text3, text4));  // 输出0（无公共子序列）
      }
  }
  

3. 背包问题：资源分配类问题

       特点：给定 “物品”（有重量 / 价值）和 “背包”（有容量限制），求满足限制的最优解（如最大价值、最少物品数），是 DP 的经典分支。常见类型：0-1 背包（物品只能选一次）、完全背包（物品可选无限次）、多重背包（物品可选有限次）。

       示例：0-1 背包（最大价值）

• 问题：有n个物品，每个物品有重量w[i]和价值v[i]，背包容量为C，求能装下的最大价值。
• 状态定义：dp[i][j]表示 “前 i 个物品，背包容量为 j 时的最大价值”。
• 转移方程：不选第 i 个物品：dp[i][j] = dp[i-1][j]；选第 i 个物品（需j >= w[i-1]）：dp[i][j] = dp[i-1][j - w[i-1]] + v[i-1]；因此dp[i][j] = max(dp[i-1][j], (dp[i-1][j - w[i-1]] + v[i-1]) if j >= w[i-1] else 0)。
• Base Case：dp[0][j] = 0（无物品），dp[i][0] = 0（无容量）。

public class Knapsack {

    /**
     * 基础版本：使用二维DP数组
     * @param weights 物品重量数组
     * @param values 物品价值数组
     * @param capacity 背包容量
     * @return 最大价值
     */
    public static int knapsackBasic(int[] weights, int[] values, int capacity) {
        if (weights == null || values == null || weights.length != values.length || capacity <= 0) {
            return 0;
        }
        int n = weights.length;
        // dp[i][j]表示前i个物品在容量为j时的最大价值
        int[][] dp = new int[n + 1][capacity + 1];
        // 填充DP数组
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                // 第i个物品的重量（注意数组索引偏移）
                int weight = weights[i - 1];      
                // 如果当前物品重量超过背包容量，则不选该物品
                if (weight > j) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 两种选择的最大值：不选当前物品 或 选当前物品
                    dp[i][j] = Math.max(
                        dp[i - 1][j],  // 不选当前物品
                        dp[i - 1][j - weight] + values[i - 1]  // 选当前物品
                    );
                }
            }
        }
        return dp[n][capacity];
    }
        System.out.println("基础版本结果: " + knapsackBasic(weights, values, capacity));  // 输出7
    }
}
    

       空间优化：观察到dp[i][j]仅依赖dp[i-1][...]（上一行），可将二维数组压缩为 1 维数组（dp[j]），但需从后向前遍历容量（避免覆盖上一行的未使用数据）

public class Knapsack {
    /**
     * 空间优化版本：使用一维DP数组
     * @param weights 物品重量数组
     * @param values 物品价值数组
     * @param capacity 背包容量
     * @return 最大价值
     */
    public static int knapsackOptimized(int[] weights, int[] values, int capacity) {
        if (weights == null || values == null || weights.length != values.length || capacity <= 0) {
            return 0;
        }
        int n = weights.length;
        // 一维数组，dp[j]表示容量为j时的最大价值
        int[] dp = new int[capacity + 1];
        
        // 填充DP数组
        for (int i = 0; i < n; i++) {
            int weight = weights[i];
            int value = values[i];
            // 从后向前遍历，避免覆盖之前的结果
            for (int j = capacity; j >= weight; j--) {
                dp[j] = Math.max(dp[j], dp[j - weight] + value);
            }
        } 
        return dp[capacity];
    }

    public static void main(String[] args) {
        // 测试案例：物品重量、价值和背包容量
        int[] weights = {2, 3, 4};
        int[] values = {3, 4, 5};
        int capacity = 5;

        System.out.println("优化版本结果: " + knapsackOptimized(weights, values, capacity));  // 输出7
    }
}
    

---

五、动态规划的常见误区与技巧

1. 常见误区

• 状态定义模糊：未明确dp[i]的含义（如 LIS 中定义为 “前 i 个元素的 LIS 长度”），导致无法推导转移方程。
• 忽略 Base Case：未初始化最小子问题的解（如斐波那契数列中dp[1]未设为 1），导致结果错误。
• 空间未优化：过度使用高维数组（如 0-1 背包用二维数组），导致空间复杂度过高。
• 混淆 “子序列” 与 “子串”：子序列不要求连续（如 LCS），子串要求连续（如最长回文子串），状态定义需区分。

2. 实用技巧

• 从小例子入手：若无法定义状态，可先手动计算小规模问题（如 n=1、n=2），观察规律。
• 画图辅助：对于二维 DP（如 LCS），可画出 DP 数组的填充过程，直观理解转移逻辑。
• 优先自底向上：面试中自底向上的循环实现更易被接受（无栈溢出风险），且便于空间优化。
• 记住经典模型：LIS、LCS、0-1 背包、路径问题是 DP 的基础模型，掌握后可迁移到类似问题（如 “最长递增子数组” 可类比 LIS）。