【c++刷题Day2】专题2线性DP

这是C++刷题的Day2

🔈题目描述
🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
给定一个长度为 N 的整数序列 a1,a2,…,aN。
请你计算该序列的最长上升子序列的长度。
上升子序列是指数值严格单调递增的子序列。

输入格式

第一行包含整数 N。

第二行包含 N
个整数 a1,a2,…,aN。

输出格式

一行，一个整数，表示最长上升子序列的长度。

数据范围

1≤N≤1000,
0≤ai≤10000。
输入样例：

7
1 7 3 5 9 4 8

输出样例：

4

🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇🎇
🔑思路

思路1：暴力dfs
直接dfs每一种子序列，时间复杂度O(2^n)，超时
思路2：动态规划
f[i]表示以i结尾的最长上升子序列的长度，那么对于a[i]，如果要接到j(0a[j]，所以可以得到状态转移方程：对于所有的满足条件的j：f[i] = max (f[j]) + 1

💯CODE代码：

#include 
using namespace std ;
const int N = 1010 ;
int f[N] , a[N] , res ;
int main () {
    int n ;
    cin >> n ;
    for (int i = 1; i <= n; i ++) {
        f[i] = 1 ;
        cin >> a[i] ;
        for (int j = 1; j < i; j ++)
            if (a[i] > a[j])
                f[i] = max (f[i] , f[j] + 1) ;
        res = max (res , f[i]) ;
    } cout << res ;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16