题目传送

原题目链接

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

DFS方法思路图

思路简述

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

代码

#include <iostream>
//最长递增子序列
using namespace stdclass 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;}
};