[已解决]如何求数列的子数列个数

RIXO

数列就是一串数字的集合，子数列就是他不改变相对顺序下的子集

例如 （1，2，1）
子数列为 （1）（2）（1，2）（2，1）（1，1）（1，2，1）
个数为6

我的数列是无序数列，且里面的每个值都小于等于5，即可能值为 0，1，2，3，4，5

想求一个效率高一点的算法。

如果可以尽量用C和C++，java我还没学。

最佳答案

月排行榜 / 总排行榜

Croper

2019-4-16 10:42:58

使用动态规划解决，效率要高得多

1. #include <vector>
   
2. #include <unordered_map>
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. //动态规划
   
7. //从size为1的子集开始，now记录以当前节点结束的新增子集的数目
   
8. //当size增加时，now变为pre，并通过pre推出新的now
   
9. 
   
10. 
    
11. int GetSubArrCount(vector<int> v) {
    
12.         vector<int> pre(v.size()+1, 0);
    
13.         pre[0] = 1;              //当子集的size为0时，只有1个子集，空集
    
14.         int sum = 0;         
    
15.         for (int i = 0; i <= v.size(); ++i) {
    
16.                 vector<int> now(v.size() - i, 0);
    
17.                 for (int j = 0; j < pre.size()-1; ++j) {  //遍历pre的元素，当元素不为0时，考虑此元素与之后的每一个不重复的元素都能构成新的不重复子集
    
18.                         if (pre[j] == 0) continue;
    
19.                         unordered_map<int, bool> map;
    
20.                         for (int k = 0; k < pre.size()-1 - j; ++k) {
    
21.                                 int a = v[i + j + k];
    
22.                                 if (map[a] == false) {
    
23.                                         map[a] = true;
    
24.                                         now[j + k] += pre[j];
    
25.                                         sum += pre[j];
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 pre = move(now);
    
30.         }
    
31.         return sum;
    
32. }
    
33. int main() {
    
34.         vector<int> v = { 1,3,2,5,3,1,4,2,5};
    
35.         int i = GetSubArrCount(v);
    
36.         cout << i;
    
37.         system("pause");
    
38. }

复制代码

跳转到最佳答案楼层

Croper

使用动态规划解决，效率要高得多

1. #include <vector>
   
2. #include <unordered_map>
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. //动态规划
   
7. //从size为1的子集开始，now记录以当前节点结束的新增子集的数目
   
8. //当size增加时，now变为pre，并通过pre推出新的now
   
9. 
   
10. 
    
11. int GetSubArrCount(vector<int> v) {
    
12.         vector<int> pre(v.size()+1, 0);
    
13.         pre[0] = 1;              //当子集的size为0时，只有1个子集，空集
    
14.         int sum = 0;         
    
15.         for (int i = 0; i <= v.size(); ++i) {
    
16.                 vector<int> now(v.size() - i, 0);
    
17.                 for (int j = 0; j < pre.size()-1; ++j) {  //遍历pre的元素，当元素不为0时，考虑此元素与之后的每一个不重复的元素都能构成新的不重复子集
    
18.                         if (pre[j] == 0) continue;
    
19.                         unordered_map<int, bool> map;
    
20.                         for (int k = 0; k < pre.size()-1 - j; ++k) {
    
21.                                 int a = v[i + j + k];
    
22.                                 if (map[a] == false) {
    
23.                                         map[a] = true;
    
24.                                         now[j + k] += pre[j];
    
25.                                         sum += pre[j];
    
26.                                 }
    
27.                         }
    
28.                 }
    
29.                 pre = move(now);
    
30.         }
    
31.         return sum;
    
32. }
    
33. int main() {
    
34.         vector<int> v = { 1,3,2,5,3,1,4,2,5};
    
35.         int i = GetSubArrCount(v);
    
36.         cout << i;
    
37.         system("pause");
    
38. }

复制代码

Croper

如果没有不重复的要求德话直接套公式n*(n+1)/2就好了啊

//====================================分割线================================
上电脑端，看了一下，你的要求好像是要求子序列不重复且子序列是非连续子序列

首先提供一个使用stl的办法

1. #include <vector>
   
2. #include <set>
   
3. #include <iostream>
   
4. 
   
5. using namespace std;
   
6. //这种方法的思路相当直接：求出所有子序列，加入set，set的大小就是不重复子序列的数量
   
7. //但是效率可能稍低
   
8. int GetSubArrCount(vector<int> v) {
   
9.         set<vector<int>> SubArrSet;
   
10.         int N = 1 << v.size();
    
11.         for (int i = 1; i < N; ++i) {
    
12.                 int a = i;
    
13.                 vector<int> SubArr;
    
14.                 for (int j = 0; a != 0; j++, a >>= 1) {
    
15.                         if ((a & 1) == 1) {
    
16.                                 SubArr.push_back(v[j]);
    
17.                         }
    
18.                 }
    
19.                 SubArrSet.insert(SubArr);
    
20.         }
    
21.         return SubArrSet.size();
    
22. }
    
23. 
    
24. int main() {
    
25.         vector<int> v = { 1,2,1};
    
26.         int i = GetSubArrCount(v);
    
27.         cout << i;
    
28.         system("pause");
    
29. }

复制代码

micolar

如果下午六点前没人给你更好的代码 我就给出我的思路 挺好的 差实现了

RIXO

micolar 发表于 2019-4-16 13:42
如果下午六点前没人给你更好的代码 我就给出我的思路 挺好的 差实现了

呃，你还回复不，不回复我明天可就设他为最佳答案了