LeetCode 300. 最长递增子序列

300. 最长递增子序列

解题思路

视频讲解

动态规划

1. 状态定义：
   dp[i] 表示以 nums[i] 结尾的最长递增子序列的长度。

2. 转移方程：
   对于每个位置 i，遍历之前的所有位置 j ($0 \le j < i$)：

   • 如果 nums[i] > nums[j]，说明 nums[i] 可以拼接在 nums[j] 后面，此时 dp[i] = Math.max(dp[i], dp[j] + 1)。

3. 初始化：
   每个元素自身都可以作为一个长度为 1 的子序列，初始化 dp[i] = 1。

4. 最终结果：
   dp 数组中的最大值。

参考代码

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int maxValue = 1;
        dp[0] = 1;
        if(n == 1) {
            return dp[0];
        }
        for(int i = 1; i < n; i ++) {
            dp[i] = 1;
            for(int j = 0; j < i; j ++) {
                // 如果后一个比前一个大，考虑更新dp
                if(nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            maxValue = Math.max(maxValue, dp[i]);
        }
        return maxValue;
    }
}

记忆化搜索

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // 记录以nums[i]为结尾的最长递增子序列的长度
        int[] memo = new int[n];
        int ans = 0;
        for(int i = 0; i < n; i ++) {
            ans = Math.max(ans, dfs(i, nums, memo));
        }
        return ans;
    }

    private int dfs(int i, int[] nums, int[] memo) {
        if(memo[i] != 0) {
            return memo[i];
        }

        // 至少包含自身
        int res = 1;
        for(int j = 0; j < i; j ++) {
            if(nums[j] < nums[i]) {
                res = Math.max(res, dfs(j, nums, memo) + 1);
            }
        }
        memo[i] = res;
        return res;
    }
}

递推

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        // 记录以nums[i]为结尾的最长递增子序列的长度
        int ans = 0;
        int[] f = new int[n];
        for(int i = 0; i < n; i ++) {
            f[i] = 1; // 每个位置至少可以单独作为一个子序列
            for(int j = 0; j < i; j ++) {
                if(nums[j] < nums[i]) {
                    f[i] = Math.max(f[i], f[j] + 1);
                }
            }
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}