极客资料网推荐LIS续：动态规划这篇文章给大家，欢迎收藏极客资料网享受知识的乐趣

如果对dp不熟，可以先看这篇文章

接上文——
发完上一篇随笔后，我灵光一闪，想到了用DP做的思路。
于是就写下了这篇随笔（好像是废话）。

1.思路1

考虑用 \(dp[i]\) 来存储 \(1\) ~ \(i\) 的最优解，可是后面你会发现……

根 本 解 不 出 来 ！

只是因为再求 \(dp[i + 1]\) 的时候，不知道 \(dp[i]\) 的末尾是什么。那怎么解决这个问题呢？

2.思路2

简单，用 \(dp[i]\) 来存储末尾下标是 \(i\) 的最优解就行了！
于是可以得到当不选时，最优解就是 \(dp[i]\) 。
而选的时候，就要一直向前遍历，直到找到一个既能匹配 \(a[i]\) 又是最优解的 \(dp[j]\) 。
可以写出如下代码：

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

思路出来了，代码也就显而易见了。

代码

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n, a[200010] = { 0 }, dp[200010] = { 0 }, maxn = -1;
	cin >> n;
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++){
		for(int j = 1; j < i; j++){
			if(a[j] < a[i])
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
    for(int i = 1; i <= n; i++) maxn = max(maxn, dp[i]);
	cout << "max=" << maxn + 1; //这里不加一的话答案就一定会少一
}

文章来源:https://www.cnblogs.com/AlgorithmInWang/p/20074823
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！