【力扣】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);               //不选择
    }
};

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