Blog of CodeJELLOW’S ENGINEERING NOTES
← 返回文章

最长递增子序列的个数

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

本文目录 ⌄

    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累加这些数组
    TEXT
    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个数,数字之间用空格格开

    输出格式:

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

    输入样例:

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

    TEXT
    5
    1 3 5 2 9
    

    输出样例:

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

    TEXT
    4
    TEXT
    #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");
    }

    通过 RSS 订阅更新 →