动态规划（Dynamic Programming，简称 DP）是解决多阶段决策过程最优化问题的常用算法思想。本文将结合经典的最长递增子序列（Longest Increasing Subsequence, LIS）问题，详细拆解动态规划解题的四个核心步骤。

1. 定义状态

定义状态是动态规划解题的基石。它要求明确问题的状态表示以及每个状态所代表的具体含义。通常，状态对应问题的一个子问题，通过对状态的精确定义，我们能将原问题拆解为一系列可求解的子问题。

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

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

  • 状态定义：设 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度。
  • 状态含义：只考虑数组前 i 个元素，且子序列必须以第 i 个元素结尾时的最长递增子序列长度。

2. 确定状态转移方程

状态转移方程描述了状态之间的递推关系，是动态规划的核心。通过该方程，我们可以从已知的子问题解推导出未知的子问题解。

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

对于 dp[i]，我们需要遍历数组中 i 之前的所有元素 j（0 <= j < i）。如果 nums[j] < nums[i]，说明可以将第 i 个元素添加到以第 j 个元素结尾的递增子序列后面，从而形成一个更长的递增子序列。

  • 状态转移方程：

    dp[i] = \max(dp[j] + 1, dp[i])

    其中 0 <= j < i 且 nums[j] < nums[i]。

  • 方程含义：对于每个满足条件的 j，计算 dp[j] + 1（即在以第 j 个元素结尾的最长递增子序列后面加上第 i 个元素），并取这些值中的最大值作为 dp[i]。

3. 初始化状态

初始化状态是为了确定问题的边界条件，即一些最简单子问题的解。这些初始状态将作为后续递推计算的基础。

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

由于每个元素自身都可以构成一个长度为 1 的递增子序列，因此初始时，我们将 dp 数组的每个元素都初始化为 1。

  • 初始化代码：

    int[] dp = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
  dp[i] = 1;
}

4. 计算最终结果

在完成状态定义、状态转移方程的确定和状态的初始化后，我们可以根据状态转移方程逐步计算出所有子问题的解，最终得到原问题的解。

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

我们需要遍历数组，根据状态转移方程更新 dp 数组的值，最后在 dp 数组中找到最大值，即为最长递增子序列的长度。

  • 计算最终结果的代码：

    public class LongestIncreasingSubsequence {
  public int lengthOfLIS(int[] nums) {
      if (nums == null || nums.length == 0) {
          return 0;
      }
      int n = nums.length;
      int[] dp = new int[n];
      
      // 初始化状态
      for (int i = 0; i < n; i++) {
          dp[i] = 1;
      }
      
      int maxLength = 1;
      // 根据状态转移方程计算 dp 数组
      for (int i = 1; i < n; i++) {
          for (int j = 0; j < i; j++) {
              if (nums[j] < nums[i]) {
                  dp[i] = Math.max(dp[j] + 1, dp[i]);
              }
          }
          // 更新最长递增子序列的长度
          maxLength = Math.max(maxLength, dp[i]);
      }
      return maxLength;
  }

  public static void main(String[] args) {
      LongestIncreasingSubsequence lis = new LongestIncreasingSubsequence();
      int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
      int result = lis.lengthOfLIS(nums);
      System.out.println("最长递增子序列的长度是：" + result);
  }
}

复杂度分析

  • 时间复杂度：由于使用了两层嵌套循环，时间复杂度为 O(n^2)，其中 n 是数组的长度。
  • 空间复杂度：使用了一个长度为 n 的数组 dp 来保存子问题的解，空间复杂度为 O(n)。

通过以上四个步骤，我们可以使用动态规划解决最长递增子序列问题。对于其他动态规划问题，也可以按照类似的思路进行分析和求解。