LeetCode 300 Longest Increasing Subsequence

概述

https://leetcode.com/problems/longest-increasing-subsequence/

注意哦，没说是连续的哦

动态规划法（最小值索引 & 当前起始索引作为状态）

1. base case：长度为 0 时为 0
2. 状态：最小值索引 & 当前起始索引（不能用最小值做索引，因为这样的话 dp 数组直接炸了，取而代之用最小值索引）
3. 选择：是否选择当前值
4. dp 函数 / 数组的定义：dp[上次选择的索引 + 1][当前索引] = 最长递增子序列长度

实现的时候第一次 >= 写成了 <=，就这还看了半天。。。

class Solution {
public:
    vector<vector<int>> dp;
    int lengthOfLIS(vector<int>& nums) {
        vector<vector<int>> t(nums.size() + 1, vector<int>(nums.size(), -1));
        dp = t;
        return helper(-1, 0, nums);
    }
    
    int helper(int minIdx, int curIdx, vector<int>& nums) {
        if (curIdx >= nums.size()) return 0;
        if (dp[minIdx+1][curIdx] != -1) return dp[minIdx+1][curIdx];
        if (minIdx != -1 && nums[curIdx] <= nums[minIdx]) {
            dp[minIdx+1][curIdx] = helper(minIdx, curIdx + 1, nums);
        } else {
            dp[minIdx+1][curIdx] = max(helper(minIdx, curIdx + 1, nums), 1 + helper(curIdx, curIdx + 1, nums));
        }
        return dp[minIdx+1][curIdx];
    }
};

动态规划法（dp[i] 表示以第 i 个起始的数字开始的最长递增子序列的长度）

1. base case：最小为 1
2. 状态：当前起始索引
3. 选择：是否选择当前值
4. dp 函数 / 数组的定义：dp[当前起始索引] = 最长递增子序列长度

实现的时候，第一次 nums[j] > nums[i] 写成 dp[j] > dp[i]，第二次 j < nums.size() 写成 j < nums.size() - 1。

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(), 1);
        int ans = 0;
        for (int i = nums.size() - 1; i >= 0 ; i --) {
            for (int j = i + 1; j < nums.size(); j ++) {
                if (nums[j] > nums[i]) {
                    dp[i] = max(dp[i], 1 + dp[j]);
                }
            }
            ans = max(ans, dp[i]);
        }
        return ans;
    }
};

状态定义成以第 i 个结束也是 okay 的，这里不再赘述。

Links: leetcode-300-longest-increasing-subsequence

未经允许，禁止转载，本文源站链接：https://iamazing.cn/