力扣：300. 最长递增子序列（Java，动态规划）

题目描述：

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：

输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

输入：nums = [0,1,0,3,2,3]
输出：4

代码实现：

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) {// 数组长度为0的情况
            return 0;
        }
        int[] dp = new int[n];// dp[i] 表示以nums[i]结尾的最长子序列长度
        int max = 1;// dp[i]中出现的最长子序列长度，初始化为1是因为自身长度至少为1
        dp[0] = 1;// 初始化
        for (int i = 1; i < n; i++) {// 从1开始遍历
            dp[i] = 1;// 任何元素都有包含自身的长度为1
            for (int j = 0; j < i; j++) {// 遍历i之前的所有元素
                if (nums[i] > nums[j]) {// 增加最长子序列长度
                    dp[i] = Math.max(dp[j] + 1, dp[i]);// 状态转移方程
                    // 更新dp[i]的最大值，每出现一次递增趋势,dp[j] + 1 = dp[i],同时跟当前dp[i]比较最大值
                }
            }
            max = Math.max(max, dp[i]);// 求dp中的最大值
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22