寒灯纸上梨花雨凉
我等风雪又一年
C++，动态规划。
动态规划
纯动态规划十分的简单，就是用数组dp记录上升序列的长度，dp[i]就表示以i为结尾的最长上升子序列，于是就能得到状态转移方程：
用代码来表示也是非常简单，对每个元素，遍历在此之前的所有元素，然后看能不能以当前元素作为“最长上升子序列”的尾巴，并选取最长的一个进行组合。
所以就能写出代码了：
class Solution {
public:
int lengthOfLIS(vector<int> &nums) {
if (nums.empty()) return 0;
vector<int> dp(nums.size(), 1);
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i])
dp[i] = max(dp[i], dp[j] + 1);
}
ans = max(ans, dp[i]);
}
return ans;
}
};
动态规划+二分
这个是参考了题解区的大佬写的题解，总的来说就是要改变dp数组记录的信息。
在本解法中，dp[i]记录的是所有长度为i+1的LIS的最后元素的最小值。
也就是说，被初始化为全0的数组dp中，可能从某个位置起全部都是零，因为大于某个长度的LIS根本不存在。
了解了以上以后，我们需要明白，如果不考虑dp数组中后面的0，那么dp数组一定是个递增数组，这个可以证明。。。
我们需要一步一步去填充dp数组，所以遍历nums数组时，需要看元素X能不能插入到某个dp的非零项中，也就是能不能刚好找到最后一个刚好小于X的dp数组的元素Y，那样就说明X能替代Y的下一个元素。。。
最后统计dp中非零的个数就好了。
class Solution {
public:
int lengthOfLIS(vector<int> &nums) {
vector<int> dp(nums.size());
int ans = 0;
for (const int &it : nums) {
int left = 0, right = ans;
while (left < right) {
int mid = (left + right) / 2;
if (it > dp[mid]) left = mid + 1;
else right = mid;
}
dp[left] = it;
ans = left == ans ? ans + 1 : ans;
}
return ans;
}
};
