AcWing 895. 最长上升子序列

dp[i]定义： 表示以a[i]结尾的最长递增子序列的长度

选择（状态转移）：dp[i]=max(dp[i],dp[j]+1)，找到前面那些结尾比a[i]小的子序列，然后把a[i] 接到这些子序列末尾，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。以划分集合思考的话：其实就是将a[i]前面的每个数划分为一个小集合，找到a[i]从哪个小集合递增过来拥有最长的上升子序列（前提是a[i]前面的数要小于a[i]才能将其划分为一个小集合）

初始dp中都为1，因为最起码也是以本身开始的递增序列

想法：（如何进行状态转移，如何计算）
假设 dp[0…i-1] 都已经被算出来了，然后问自己：怎么通过这些结果算出 dp[i]？
从0~i-1循环一遍，找到小于a[i]的值，并更新dp[i]找到最长的。

java代码

import java.util.Scanner;

public class Main {
    static int N = 1010;
    static int[] a = new int[N];
    static int[] f = new int[N];
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        for(int i = 1;i <= n;i++) a[i] = scan.nextInt();
        int res = 0;
        for(int i = 1;i <= n;i++)
        {
            f[i] = 1;//如果只以当前数结尾且前面没有数是1
            for(int j = 1;j < i;j++)
                if(a[j] < a[i])
                    f[i] = Math.max(f[i], f[j] + 1);

            res = Math.max(res, f[i]);
        }
        System.out.println(res);
    }
}

#include<iostream>

using namespace std;

int main(){
    int n;
    cin >> n;
    int a[n]; 
    int dp[n];

    for(int i=0;i<n;i++){
        cin >> a[i];
        dp[i]=1; //赋初始值为1
    }

    for(int i=1;i<n;i++){//循环n个位置
        for(int j=0;j<i;j++){ //在a[0..i-1]中，找到结尾数字小于以a[i]结尾的，并更新dp[i]的值，找到最长的（也就是在所有以a[i]结尾的上升子序列集合中找到最长的）
            if(a[j] < a[i]) dp[i]=max(dp[i],dp[j]+1); // 当前以j结尾的序列小于a[i],那么个更新dp[i]的值为max(以i结尾的序列的长度，以j结尾的序列长度+1)
        }
    }

    int res=0;
    for(int i=0;i<n;i++) res=max(res,dp[i]); 

    cout << res << endl;

    return 0;
}