【力扣】300. 最长递增子序列（DFS+DP两种方法实现）

题目传送

原题目链接

最长递增子序列[DFS 方法]

DFS方法思路图

思路简述

• 对于序列中的每一个数字只有选择和不选择两种状态
• 如果选择了，方案数就加一
• 否则方案不变
• 进入下一次选择则 i 后移
• i 越界时更新方案的最大值即可

代码

#include <iostream>
//最长递增子序列
using namespace std

class Solution {
public:
    int size;
    int res;
    vector<int> arr;
    int lengthOfLIS(vector<int>& nums) {
        res = 0;
        size = nums.size();
        arr = nums;
        dfs(0, INT_MIN, 0);
        return res;
    }
    inline void dfs(int i, int pre, int count) {
        if (i == size) {
            res = max(count, res);          //更新最大值
            return;
        }
        if (arr[i] > pre) {
            dfs(i+1, arr[i], count+1);      //选择
        }
        dfs(i+1, pre, count);               //不选择
    }
};

大家可以自行考虑有没有优化的方法

最长递增子序列[DP]方法

DP方法思路图

思路简述

• i 枚举每一个数字
• j每次枚举找到 i 位置前所有比 i 位置数小的数字的dp[j]最大值
• 如果dp[j] > dp[i] –> dp[i] = dp[j] + 1

从而推导出状态转移方程:
前提条件: dp[i] > dp[j]

dp[i] = max(dp[i], dp[j] + 1)

代码方案

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