最长递增子序列的个数

DP问题，求解方法还是不太好想出来的。

示例 1:

输入: [1,3,5,4,7]
输出: 2
解释: 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。
示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。
注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

题解：

1. DP[i]记录最长递增序列，count[i]记录个数，初始化所有元素均为1，原因为DP在均不递增时自己算一个元素，个数为1
2. 双层循环，若nums[j]DP[i]则说明这个新找到的子序列是最长的（ps：这个也就等价于DP[j]==DP[i]，但由于初始时DP都为1，第一次比较时DP[j]可能远大于DP[i]，所以这样写),count[i]=count[j]，将j处之前最长的子序列个数更新到i处，若DP[j]+1==DP[i]，说明又找到一个相同长度的子序列，那么count就要更新
3. 找到DP中的最大值，在DP中找到有多少个子序列与最大值相同的数组，count累加这些数组

int findNumberOfLIS(vector<int>& nums) {
    int N = nums.size();
    if(N==0){
        return 0;
    }
    vector<int> DP(N, 1);
    vector<int> count(N, 1);
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          if (DP[j] + 1 > DP[i]) {
            DP[i] = DP[j] + 1;
            count[i] = count[j];
          } else if (DP[i] == DP[j] + 1) {
            count[i] += count[j];
          }
        }
      }
    }
    int max = *max_element(begin(DP), end(DP));
    int ans = 0;
    for (int i = 0; i < N; i++) {
      if (max == DP[i]) {
        ans += count[i];
      }
    }
    return ans;
  }

PTA上的题是这个的简化，只求最长子序列，小修一下即可

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

输入格式:

输入有两行： 第一行：n，代表要输入的数列的个数 第二行：n个数，数字之间用空格格开

输出格式:

最长单调递增子序列的长度

输入样例:

在这里给出一组输入。例如：

5
1 3 5 2 9

输出样例:

在这里给出相应的输出。例如：

4

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int Big(vector<int> vec) {
  vector<int> dp(vec.size(), 1);
  for (int i = 0; i < vec.size(); i++) {
    for (int j = 0; j < i; j++) {
      if (vec[i] > vec[j]) {
        if (dp[j] + 1 > dp[i]) {
          dp[i] = dp[j] + 1;
        }
      }
    }
  }
  return *max_element(begin(dp),end(dp));
}

int main() {
  int n;
  cin >> n;
  vector<int> vec(n);
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
  }
  cout << Big(vec);
  system("pause");
}

---