每日算法：洛谷B3637（动态规划)

题目描述

这是一个简单的动规板子题。

给出一个由 n(n≤5000) 个不超过 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 n，表示序列长度。

第二行有 n 个整数，表示这个序列。

输出格式

一个整数表示答案。

输入输出样例

输入 #1

6
1 2 4 1 3 4

输出 #1

4

说明/提示

分别取出 1、2、3、4 即可。

思路:

根据题意，我们需要找到最长的序列和，但是这中间可以连续（如124）也可以不连续（如1234），这里我们可以发现朴素算法是每一次都站在一个节点上去一次遍历后面的所有节点，又因为后面遍历的节点的抉择影响着不同的选择，因此我们可以很容易的想象到递归树，众所周知，一旦出现递归树，那么这个问题大概率就可以用动态规划来优化。

动态规划思路：

1.将大问题拆解成子问题：

我们发现：一个子序列的最长长度是由它的最后一个最大的数决定的，如2可以放在1的后面，构成12序列，3可以放在1或放在12后面构成13或123序列，4可以放在12或123后面构成124或1234序列........

因此我们可以来到第二步：

构建状态转移方程：

假设前面的所有序列已经全部遍历完了，那么第q[i]个数应该可以放在最后一个数为q[j] 的后面，又因为子序列是自增的，因此q[i]应该大于q[j]，同时因为要求长度最大，因此我们应该对该结果取最大值。

因此，我们可以得到状态转移方程：

if(q[i] > q[j]) q[i] = max(q[i],q[j]+1);

然后，写代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];
int dp[N];
int main() {
	cin>>n;
	 for(int i = 1;i<=n;i++){
	 	cin>>q[i];
	 	dp[i] = 1;
	 }
	 dp[1] = 1;//以1结尾的数长度一定是1  
	for(int i = 2;i <=n;i++){//从2开始遍历，i表示子序列的末尾数字 
		for(int j = 1;j <=i - 1;j++){//j表示的是遍历子序列长度比i小的数字 
			if(q[i] > q[j]){//只能接在比自己小的数的后面 
				dp[i] = max(dp[i],dp[j]+1);//取最大值
			}
		}
	}
	int ans = 0;//遍历DP数组找到最大值
	for(int i = 1;i <=n;i++){
		ans = max(ans,dp[i]);
	}
	cout<<ans<<endl;
    return 0;

}