DP-最长上升子序列

题面：

样例：

思路：

遇到动态规划问题，我们照旧思考两部分，状态表示以及状态计算。这里我们f[N]表示以第i个数结尾的上升子序列的最大值。我们将f[N]划分为若干个部分，因为我们要用到递推思路想办法用前面的来表示这一个，所以我们自然而然地可以想到用上升子序列中的前一个数进行分类。前一个数是序列中的第一个数，第二个数以此类推直到第i-1个数。我们就可以得到状态计算方程。f[i]就可以分为这些部分的“和”然后求最大值。

代码： #include<iostream> using namespace std; const int N = 1010; int n; int a[N]; int f[N]; int main(void) { cin >> n; for(int i = 1;i <= n;i++) cin >> a[i],f[i] = 1; for(int i = 1;i <= n;i++) for(int j = 1;j < i;j++) if(a[j]<a[i]) f[i] = max(f[i],f[j]+1); int cnt; for(int i = 1;i <= n;i++) cnt = max(cnt,f[i]); cout << cnt << endl; return 0; } tips：

需要注意的是，我们划分的那些部分不一定是每一部分都有的，必须要满足前一个小于a[i]这个条件。其次我们在状态计算的时候，一定要加上1，因为前面的还有这个数它自身。