嘛~最近被问到了一个题，觉得很好(mian)玩(shu)。但是没答出来还是比较不甘心的。所以要写下来。问题的描述很简单：

求一个数组的递增子序列的个数

这是什么意思呢，我们来举一个栗子。对于数组[1,3,2]，我们有[1,3],[1,2]这两个子序列是递增的，所以需要求的结果就是2。

忧伤的我一开始把题意理解成了子串，这又是另一个故事了。

一个直观的想法是使用dfs来解这个题，但是这是一个O(2^n)的算法，肯定是要TLE的啊！于是我们需要一个O(n^2)的算法来解决这个问题。这个时候就要祭出dp大法了。

首先想到的是这个子结构是个什么呢？我们找到一个数字A，如果它比它前面的某个数字B大，那么数字B可以组成的最大的递增子序列们和BA这个组合就是A能够达到的最大递增子序列啦，所以写成递推式：

dp[i] = dp[i]+dp[j]+1; //num[i]>num[j]

然后代码贴在下面：

++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <iostream>
#include <memory.h>
using namespace std;
int n;
const int MAXN=10000;
int num[MAXN], dp[MAXN];
int main(){
    int ans = 0;
    cin >> n;
    for(int i = 0; i < n; ++i){
        cin >> num[i]; 
    }
    memset(dp, 0, sizeof(dp));
    for(int i = 1; i < n; ++i){
        for(int j = 0; j < i; ++j){
            if(num[i]>num[j]){
                dp[i] += (dp[j]+1);
                //cout<<num[i]<<" "<<num[j]<<" "<<dp[i]<<endl;
            }
        }
        ans+= dp[i];
    }
    cout << ans<< endl;
    return 0;
}

当时没做出来真是不应该啊sad。|ω•`)