最长上升子序列

dp[i]表示以第i个数结尾的所有子序列的最大值

集合划分:看第i-1个数是原数列的哪个位置的数

#include <bits/stdc++.h>
using namespace std;
const int N =1010;
int dp[N],a[N];
int n;
int main()
{    cin>>n;
   for(int i=1;i<=n;i++)
   cin>>a[i];
   for(int i=1;i<=n;i++)
   {
       dp[i]=1;
       for(int j=1;j<i;j++)
       {
           if(a[j]<a[i])
           dp[i]=max(dp[i],dp[j]+1);
       }
   }
   int res=0;
   for(int i=1;i<=n;i++)
   res=max(dp[i],res);
   cout<<res<<endl;

    return 0;
}

上升子序列的个数

法1:

dp[i]表示 以第i个数结尾的所有子序列的个数

第i个数前面有比它小的数，那么第i个数可以接在比它小的数结尾的所有子序列的后面

构成新的子序列

集合划分:看第i-1个数 是原序列的哪个位置的数

#include <bits/stdc++.h>
using namespace std;
const int N =1010;
int dp[N];
int n;
char a[1000];
int main()
{    cin>>n>>a+1;
   for(int i=1;i<=n;i++)
   {
       dp[i]=1;
       for(int j=1;j<i;j++)
       {
           if(a[j]<a[i])
           dp[i]=dp[i]+dp[j];
       }
   }
   int res=0;
   for(int i=1;i<=n;i++)
   res+=dp[i];
   cout<<res<<endl;

    return 0;
}

法2:

二进制枚举所有子序列

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
string c;
int ans;
bool check(string x)
{
    for (int i = 1; i < x.size(); i++)
    {
        if (x[i] <= x[i - 1])
            return false;
    }
    return true;
}
int main()
{
    cin >> c;
    int len = c.size();
    for (int i = 0; i < 1 << len; i++) //枚举所有子序列
    {
        string t = "";
        for (int j = 0; j < len; j++)
        {
            if (i >> j & 1)
                t = t + c[j];
        }
        if (check(t)) //判断选中的子序列是否为上升子序列
            ans++;
    }
    cout<<ans-1<<endl; //减掉都不选的情况

    return 0;
}