Java最长递增子序列详解（动态规划DP入门实战教程）

动态规划思路解析

动态规划的核心思想是：把大问题拆成小问题，利用小问题的解构建大问题的解。

对于LIS问题，我们可以定义一个DP数组：

• dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

那么，如何计算 dp[i] 呢？

我们遍历 j = 0 到 i-1，如果 nums[j] < nums[i]，说明可以把 nums[i] 接在以 nums[j] 结尾的子序列后面，从而形成一个更长的递增子序列。因此：

dp[i] = Math.max(dp[i], dp[j] + 1);

Java代码实现（O(n²) 时间复杂度）

下面是完整的Java实现代码，包含详细注释：

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];                // 初始化：每个元素自身构成长度为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 = 1;        for (int len : dp) {            if (len > maxLength) {                maxLength = len;            }        }                return maxLength;    }        // 测试方法    public static void main(String[] args) {        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};        System.out.println("最长递增子序列长度为: " + lengthOfLIS(nums));        // 输出：4    }}  

算法复杂度分析

• 时间复杂度：O(n²)，因为有两层嵌套循环。
• 空间复杂度：O(n)，用于存储dp数组。

注：还有一种基于二分查找的O(n log n)解法，但本教程聚焦于DP基础，适合初学者理解核心思想。

常见误区提醒

• ❌ 误以为子序列必须连续 → 实际上可以不连续，只要保持原顺序即可。
• ❌ 忘记初始化dp数组为1 → 每个元素至少能构成长度为1的子序列。
• ❌ 混淆“递增”和“非递减” → 本题要求严格递增，所以要用 < 而不是 <=。

总结

通过本教程，你已经掌握了使用Java最长递增子序列的动态规划解法。这是学习动态规划教程中的经典案例，也是提升Java DP算法能力的重要一步。多加练习，你就能熟练应用这种“状态定义 + 状态转移”的DP思维模式。

记住：理解问题本质比死记代码更重要。动手写一写、改一改，才能真正掌握最长递增子序列实现的精髓！