Carl已经将刷题指南全部整理到了Github ：
https://github.com/youngyangyang04/leetcode-master，方便大家在电脑上阅读，这个仓库每天都会更新，大家快去给一个star支持一下吧！同时我在B站更新算法视频，B站同名：代码随想录
300.最长递增子序列
题目链接：https://leetcode-cn.com/problems/longest-increasing-subsequence/
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。
示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4
示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1
提示：
- 1 <= nums.length <= 2500
- -10^4 <= nums[i] <= 104
思路
最长上升子序列是动规的经典题目，这里dp[i]是可以根据dp[j] （j < i）推导出来的，那么依然用动规五部曲来分析详细一波：
- dp[i]的定义
dp[i]表示i之前包括i的最长上升子序列。
- 状态转移方程
位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。
所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。
- dp[i]的初始化
每一个i，对应的dp[i]（即最长上升子序列）起始大小至少都是是1.
- 确定遍历顺序
dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。
j其实就是0到i-1，遍历i的循环里外层，遍历j则在内层，代码如下：
for?(int?i?=?1;?i??nums[j])?dp[i]?=?max(dp[i],?dp[j]?+?1);
????}
????if?(dp[i]?>?result)?result?=?dp[i];?//?取长的子序列
}
- 举例推导dp数组
输入：[0,1,0,3,2]，dp数组的变化如下：
如果代码写出来，但一直AC不了，那么就把dp数组打印出来，看看对不对！
以上五部分析完毕，C++代码如下：
class?Solution?{
public:
????int?lengthOfLIS(vector&?nums)?{
????????if?(nums.size()?<=?1)?return?nums.size();
????????vector?dp(nums.size(),?1);
????????int?result?=?0;
????????for?(int?i?=?1;?i??nums[j])?dp[i]?=?max(dp[i],?dp[j]?+?1);
????????????}
????????????if?(dp[i]?>?result)?result?=?dp[i];?//?取长的子序列
????????}
????????return?result;
????}
};
总结
本题最关键的是要想到dp[i]由哪些状态可以推出来，并取最大值，那么很自然就能想到递推公式：dp[i] = max(dp[i], dp[j] + 1);
子序列问题是动态规划的一个重要系列，本题算是入门题目，好戏刚刚开始！
「代码随想录」原创算法学习手册开放下载！
我已经将「代码随想录」中的二叉树、回溯算法、贪心算法、背包问题专题都整理成PDF，绝对精华，绝对通透！
先预览一下部分截图：
无套路，直接给出下载地址：
https://pan.baidu.com/s/1smqn0f6xhQNV3NAWw61SHg 密码: vjqw
@代码随想录 期待你的关注