最长上升子序列--从数学归纳到动态规划

本文所有代码采用C++

0x01.问题

给定一个无序的整数数组，找到其中最长上升子序列的长度。

输入示例：10 9 2 5 3 7 101 18 

输出示例：4

0x02.分析问题

这个题目看起来很简单，其实问题比较复杂。 从题目中，我们得到以下有效信息：

1. 数组是无序的。
2. 需要找的是最长上升子序列。
3. 子序列并不一定是要连在一起，只要都在数组里面，就算做它的子序列。

我们需要做的是找出里面上升子序列中，长度最大的那个，很明显可以使用动态规划的思想。

首先明确状态，如果我们有一个dp[i]，那么它应该代表何种含义呢，我们根据需求来，需求是上升子序列的最大长度，那我们就可以假设dp[i]表示，到第 i 号元素为止，最长上升子序列的长度。

既然明确了状态，我们下一步要做的就是，找到状态转移方程。

我们要弄清楚这里面迭代的关系，可以用数学归纳的思想去思考。

我们回想一下数学归纳的模板，就是假设k=1时，有个啥条件成立，假设k=n-1时，这个条件也成立，然后想办法利用之前的假设，推导k=n时也成立。

在动态规划中，这个思想可以这样运用，先轻松的得出几个相应的初始值，假设dp[0]一直到dp[i-1]的值都已经计算出，那么，如何得到dp[i]的值。

以题目的输入输出做示范：

首先，dp[0]=1，dp[1]=1，dp[2]=1，dp[3]=2，dp[dp4]=2，这些是一眼可以看出来的，我们用这些条件，看如何得出dp[5]。

dp[5]的含义是前6个数中最长上升子序列的长度，我们在求这个的过程中，一定要利用之前已经得到的条件，dp[0]到dp[4]，我们这样想，既然到4为止，最长的上升子序列的长度是2，那么，如果我们再往后面加一个，会是多少呢？估计很多人这个时候会恍然大悟，喔，这不是只要看能不能接到dp[4]产生的最长子序列上就行了嘛，当然不是，哈哈，谁说dp[4]就一定是最大的了，最大的也可能在前面，所以，我们要把dp[0]到dp[4]全部试着接一下，看接到那个上面，长度最大，对于任意一个数，它只有两种情况，就是接上，和不接上，接上的原因是，只要有比自己小的，就可以开始接了，接不上的原因就是，自己比前面的数都小，每办法接上。

我们根据前面的数，得到了dp[i]的值，根据数学归纳的思想，这个时候，我们已经可以基本确定状态转移方程了。还要注意dp数组应该初始化为1。

for (int j = 0; j < i; j++) {
    if (nums[i] > nums[j]) {
	    dp[i] = max(dp[i], dp[j] + 1);
	}
}

解惑：为什么num[i]>nums[j]就可以接了？万一这个最大的结尾不是nums[j]呢？而是比nums[j]更大的数？？

这个时候，我们应该思考nums[j]，又是怎么得到的，它要么是最小的，没有接上，那么这个情况，nums[i]肯定是可以直接接上的，如果nums[j]是接上的，那么nums[j]就是最后一个数，也就是这个子序列中最大的数，nums[i]比这个序列里面最大的数还大，是不是也可以接上。

0x03.动态规划解决

int lengthOfLIS(vector<int>& nums){
	int n = nums.size();
	if (n==0) {
		return 0;
	}
	vector<int> dp(n, 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			if (nums[i] > nums[j]) {
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
	}
	return *max_element(dp.begin(), dp.end());
}

0x04.复杂度分析

时间复杂度为 O(n^2)

空间复杂度为 O(n)

0x05.从数学归纳到动态规划

• 再难以确定状态转移方程的时候，我们可以巧妙的利用数学归纳的思想，假设前面已经算出来了很多值，然后利用前面的这些值，来推导dp[i]，得到的dp[i]肯定是正确的，这样就得到了状态转移方程。
• 这里面最重要的部分就是，如何利用假设的已知值，推导未知的值。

如果本文对你有帮助，请分享给你的朋友吧！

ATFWUS  --Writing By 2020--03--14