一開(kāi)始想到的方法非常低效，但好理解。
?

思路分析：

1. 使用二維數(shù)組dp來(lái)記錄遞增子序列的長(zhǎng)度信息，其中dp[i][0]表示以nums[i]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，dp[i][1]表示包含nums[i]的最長(zhǎng)遞增子序列的長(zhǎng)度。

2. 初始化dp數(shù)組，將以第一個(gè)元素結(jié)尾的遞增子序列長(zhǎng)度置為0。

3. 使用兩層循環(huán)遍歷數(shù)組，比較當(dāng)前元素與前面元素的大小關(guān)系，更新dp數(shù)組的值。

4. 最終返回最后一個(gè)元素的兩種狀態(tài)中的最大值，即為整個(gè)數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度。

這種動(dòng)態(tài)規(guī)劃算法的時(shí)間復(fù)雜度為O(n^2)，其中n為數(shù)組的長(zhǎng)度。

class Solution {
public:
    // 函數(shù)用于計(jì)算最長(zhǎng)遞增子序列的長(zhǎng)度
    int lengthOfLIS(vector<int>& nums) {
        // dp[i][0]表示以nums[i]結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
        // dp[i][1]表示包含nums[i]的最長(zhǎng)遞增子序列的長(zhǎng)度
        vector<vector<int>> dp(nums.size(), vector<int>(2, 1));
        
        // 初始化dp數(shù)組，將以第一個(gè)元素結(jié)尾的遞增子序列長(zhǎng)度置為0
        dp[0][0] = 0;

        // 遍歷數(shù)組，計(jì)算dp數(shù)組的值
        for (int i = 1; i < nums.size(); i++) {
            for (int j = i - 1; j >= 0; j--) {
                // 如果當(dāng)前元素大于前面的某個(gè)元素，更新包含當(dāng)前元素的遞增子序列的長(zhǎng)度
                if (nums[i] > nums[j]) {
                    dp[i][1] = max(dp[i][1], dp[j][1] + 1);
                }
                // 更新以當(dāng)前元素結(jié)尾的遞增子序列的長(zhǎng)度
                dp[i][0] = max(dp[i][0], max(dp[j][1], dp[j][0]));
            }
        }

        // 返回最終結(jié)果，取最后一個(gè)元素的兩種狀態(tài)中的最大值
        return max(dp[nums.size() - 1][0], dp[nums.size() - 1][1]);
    }
};

但還有種既節(jié)省空間也節(jié)省時(shí)間的方法。

思路分析：

1. 初始化dp數(shù)組，其中dp[i]表示以第i個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度，初始值為1。

2. 使用兩層循環(huán)遍歷數(shù)組，對(duì)于每個(gè)元素，查找在其之前的元素中比它小的元素，更新以當(dāng)前元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度。

3. 在內(nèi)循環(huán)中，通過(guò)比較當(dāng)前元素與之前元素的大小關(guān)系，更新dp數(shù)組的值。

4. 同時(shí)，記錄整個(gè)數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度，即取dp數(shù)組中的最大值。

5. 最終返回整個(gè)數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度。

這種算法的時(shí)間復(fù)雜度為O(n^2)，其中n為數(shù)組的長(zhǎng)度。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-819627.html

class Solution {
public:
    // 函數(shù)用于計(jì)算最長(zhǎng)遞增子序列的長(zhǎng)度
    int lengthOfLIS(vector<int>& nums) {
        // 如果數(shù)組長(zhǎng)度小于等于1，直接返回?cái)?shù)組長(zhǎng)度
        if (nums.size() <= 1) return nums.size();
        
        // dp數(shù)組用于記錄以每個(gè)元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
        vector<int> dp(nums.size(), 1);
        
        // result用于記錄整個(gè)數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度
        int result = 0;
        
        // 遍歷數(shù)組
        for (int i = 1; i < nums.size(); i++) {
            // 在當(dāng)前元素之前的元素中查找比當(dāng)前元素小的元素
            for (int j = 0; j < i; j++) {
                // 如果找到比當(dāng)前元素小的元素，更新以當(dāng)前元素結(jié)尾的最長(zhǎng)遞增子序列的長(zhǎng)度
                if (nums[i] > nums[j]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            
            // 更新整個(gè)數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度
            if (dp[i] > result) {
                result = dp[i];
            }
        }
        
        // 返回最終結(jié)果，即整個(gè)數(shù)組的最長(zhǎng)遞增子序列的長(zhǎng)度
        return result;
    }
};

到了這里，關(guān)于力扣--動(dòng)態(tài)規(guī)劃300.最長(zhǎng)遞增子序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！