LeetCode 300 Longest Increasing Subsequence

动态规划问题 2022-02-14 18:27:37 2022-02-14 20:56:58 260 次浏览

概述

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 的,这里不再赘述。

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