решение проблемы leetcode (проблема самой длинной восходящей подпоследовательности)

определение

LIS (Longest Increasing Subsequence) самая длинная возрастающая подпоследовательность Последовательность чисел bi, когда b1

leetcode 300. Самая длинная восходящая подпоследовательность

анализ решения проблем

решение грубой силы

Выберите все подпоследовательности для суждения. О ((2 ^ п) * п)

Решение для динамического программирования

определение состояния

LIS(i) представляет собой длину самой длинной восходящей подпоследовательности, заканчивающейся i-м числом.
LIS(i) представляет собой длину самой длинной восходящей подпоследовательности, которую можно получить, выбрав число nums[i] в диапазоне [0...i].

переход состояния

LIS(i) = max(1+LIS(j) if nums[i]>nums[j]) (j<i)

Код

рекурсивный и запоминаемый поиск


class Solution {

//在[0…index]的范围内，选择数字nums[index]可以获得的最长上升子序列的长度。
private:
    vector<int> memo;
    int searchLIS(vector<int>& nums, int index){
        if (index == 0){
            return 1;
        }
        
        if (memo[index] != -1){
            return memo[index];
        }

        int res = 1;
        for (int i = 0; i < index; i++){
            if (nums[index] > nums[i]){
                res = max(res, 1 + searchLIS(nums, i));
            }

        }
        memo[index] = res;
        return res;
    }

public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0){
            return 0;
        }
        memo = vector<int>(n, -1);
        int res = -1;
        for(int i = 0; i < n; i++){
            res = max(res, searchLIS(nums, i));
        }
        return res;
    }
};

Используйте динамическое программирование


class Solution {

public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (n == 0){
            return 0;
        }
        //memo[index]表示在[0…index]的范围内，选择数字nums[index]可以获得的最长上升子序列的长度。
        vector<int> memo(n, 1);
        for (int i = 1; i < n; i++){
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    memo[i] = max(memo[i], memo[j] + 1);
                }
            }
        }
        
        
        int res = -1;
        for(int i = 0; i < n; i++){
            res = max(res, memo[i]);
        }
        return res;
    }
};

определение

leetcode 300. Самая длинная восходящая подпоследовательность

анализ решения проблем

решение грубой силы

Решение для динамического программирования

определение состояния

переход состояния

Код

рекурсивный и запоминаемый поиск

Используйте динамическое программирование

похожие темы