300. 最长递增子序列-LeetCode

🎯 问题描述（来源于LeetCode）

描述：给你一个整数数组 nums，找到其中最长严格递增子序列的长度。

说明：

子序列是由数组元素删除（或不删除）任意数量的元素后，不改变其余元素顺序得到的序列。

示例：

示例 1：

1
2
3

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

示例 2：

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

💻 解题思路

思路1：动态规划 (自底向上)

核心思想：
这是一个标准的线性 DP 问题。

状态定义：dp[i] 表示以 nums[i] 为结尾的最长递增子序列的长度。
- 注意：必须定义为“以 i 结尾”，而不是“前 i 个元素中的最大长度”，这样才能推导状态转移。
状态转移：对于每个元素 i，我们去看它前面所有的元素 j。
- 如果 nums[j] < nums[i]，说明 i 可以接在 j 后面。
- 此时 dp[i] = max(dp[i], dp[j] + 1)。
初始化：每个单独的元素本身就是一个长度为 1 的子序列，所以 dp 数组全部初始化为 1。

算法步骤：

初始化 dp 数组，长度为 n，值全为 1。
外层循环遍历每个位置 i。
内层循环遍历 i 之前的所有位置 j。
如果满足递增条件 nums[j] < nums[i]，尝试更新 dp[i]。
最后返回 dp 数组中的最大值。

思路1：代码实现

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # 1. 初始化 DP 数组
        # 每个位置的最小长度都是 1（只有自己）
        dp = [1] * n
        
        # 2. 外层循环：遍历每个位置 i
        for i in range(n):
            # 3. 内层循环：遍历 i 之前的所有位置 j
            for j in range(i):
                # 4. 状态转移：如果 nums[j] < nums[i]
                # 说明 i 可以接在 j 后面，尝试更新 dp[i]
                if nums[j] < nums[i]:
                    dp[i] = max(dp[i], dp[j] + 1)
        
        # 5. 返回所有 dp[i] 中的最大值
        # 因为最长子序列不一定以最后一个数结尾
        return max(dp)