线性DP：最长上升子序列（可不连续，数组必须连续）
| Dp问题 | 状态表示 f(i,j) | 集合 | 所有以第i个数结尾的上升子序列集合 | |||||
| - | ||||||||
| f(i,j)的值存的是什么 | 序列长度最大值max | |||||||
| - | ||||||||
| 状态计算 （其实质是集合的划分） | 划分 | f[ i ] = max(f[ i ] , f [ j ]+1), j < i ,a[ j ]<a[ i ] 以上面的条件作为选或不选聚类形成划分依据 | ||||||
#include<iostream>
#include<algorithm>
using namespace std;const int N=1010;int n;
int a[N], f[N];int main()
{cin>>n;for (int i = 1; i <= n; i++) cin>>a[i];for (int i = 1; i <= n; i++){f[i] = 1; //初始化，只有a[i]一个数for (int j = 1; j < i; j++)//j<i,a[j] < a[i]，max三个条件作为集合划分为选或不选的依据if (a[j] < a[i])f[i] = max(f[i], f[j] + 1);}int res = 0;for (int i = 1; i <= n; i++) res = max(res, f[i]);//在dp数组内找maxcout<<res;return 0;
}