?聲明：本文原題主要來自力扣，記錄此博客主要是為自己學(xué)習(xí)總結(jié)，不做任何商業(yè)等活動！

一、下面是原題描述

給定一個未排序的整數(shù)數(shù)組，找到最長遞增子序列的個數(shù)。

示例 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。
注意:?給定的數(shù)組長度不超過 2000 并且結(jié)果一定是32位有符號整數(shù)。

1.1題目分析

由于上一篇博客已經(jīng)分析過求最長上升子序列長度——C++的經(jīng)典LIS問題，該題是求最長增長子序列個數(shù)，經(jīng)過分析，這題也只是經(jīng)典LIS(Longest Increasing Subsequence)問題的變種，也就是用同樣的LIS框架，區(qū)別在于本體需要額外記錄每個最長子序列個數(shù)。下面是具體實現(xiàn)思路。

用dp[i]記錄最長子序列長度maxLen，count[i]記錄最長子序列個數(shù)，其中i表示數(shù)組的元素個數(shù)，0 <= i < n；如果求出前dp[i]和count[i]的i-1元素的值，則可以推導(dǎo)出：

dp[i] = max(dp[j]) + 1，滿足條件nums[i] > nums[j]，0 =< i < n，0 <=?j?< i - 1；

當(dāng)nums[i] > nums[j]時，有：

如果dp[i] == dp[j] + 1，則count[i] += count[j]；

如果dp[i] <?dp[j] + 1，則count[i] = count[j]；

第(1.)需要累加是因為前面遇到一個相同的最長子序列，需要把該子序列也加上。后面第(2.)之所以重新賦值，是因為第一次遇到更長的子序列，故需要更新count[i]最長子序列長度。

當(dāng)求出全部的count[i]后，需要遍歷找出等于maxLen的所有count[j]，然后將這些滿足條件的coount[j]全部相加即為最長子序列長度asn。

動態(tài)規(guī)劃滿足三個條件：狀態(tài)方程、狀態(tài)轉(zhuǎn)移方程、邊界條件，根據(jù)分析可知該題滿足條件，下面是分析的表格：

nums = {10, 9, 2, 5, 3, 7, 101, 18}

dp[i] = max(dp[j]) + 1，滿足條件nums[i] > nums[j]，0 =< i < n，0 <=?j?< i - 1；

當(dāng)nums[i] > nums[j]時，有：

如果dp[i] == dp[j] + 1，則count[i] += count[j]；

如果dp[i] <?dp[j] + 1，則count[i] = count[j]；

元素下標(biāo)n	0	1	2	3	4	5	6	7
元素值	10	9	2	5	3	7	101	18
dp[i](或LIS)	1	1	1	2	2	3	4	4
count	1	2	3	1	2	2	2	4

1.2代碼實現(xiàn)分析

1.2.1求出dp[i]和count[i]的值

假如nums[i]>nums[j]，則更新dp[i]和count[i]，更新規(guī)則為假如dp[i]<dp[j]+1，dp[i]=dp[j]+1，且count[i]=count[j]，著兩條語句是假如有更長最長子序列，則更新dp[i]和count[i]，一般如果第一次出現(xiàn)更長最長子序列，count[i]==1，只有在小遍歷第二次遇到該最長子序列時，才會累加count[i]+=count[j]，則關(guān)鍵實現(xiàn)代碼如下：

for (int i = 0; i < size; ++i) // 求出前面i個dp[i]和count[i]的值 {dp[i] = 1;count[i] = 1;for (int j = 0; j < i; ++j) // 更新dp[i]和count[i]{if (nums[i] > nums[j]){if (dp[i] < dp[j] + 1){dp[i] = dp[j] + 1;count[i] = count[j];}else if (dp[i] == dp[j] + 1){count[i] += count[j];}}}// 根據(jù)已求得的dp[i]和count[i]，求出asn }

1.2.2根據(jù)已求得的dp[i]和count[i]求出asn

根據(jù)前面已經(jīng)更新的dp[i]和count[i]，求出最長子序列長度asn。即假如有新增最長子序列，則直接更新asn=count[i]，否則有相同最長子序列dp[i]==maxLen，則累加所有最長子序列長度asn+=count[i]。關(guān)鍵代碼如下：

for (int i = 0; i < size; ++i) // 大遍歷 {dp[i] = 1;count[i] = 1;for (int j = 0; j < i; ++j) // 小遍歷，更新dp[i]和count[i]{// ......}if (dp[i] > maxLen) // 假如有新增最長子序列，則直接更新{maxLen = dp[i];asn = count[i];}else if (dp[i] == maxLen) // 否則有相等最長子序列，則累加所有相同子序列count[i]{asn += count[i];} }

1.3完整代碼

class Solution { public:int findNumberOfLIS(vector<int>& nums) {int asn=0, maxLen=1, size = nums.size();vector<int> dp(size, 0), count(size, 0);for(int i=0; i<size; ++i) // 大遍歷{dp[i] = 1;count[i] = 1;for(int j=0; j<i; ++j) // 小遍歷，更新dp[i]和count[i]{if(nums[i] > nums[j]) // 出現(xiàn)更新子序列{if(dp[i] < dp[j] + 1) // 更新最長子序列長度{dp[i] = dp[j] + 1;count[i] = count[j];}else if(dp[i] == dp[j] + 1) // 出現(xiàn)相同最長子序列長度，累加所有相同最長子序列{count[i] += count[j];}}}if(dp[i] > maxLen) // 更新完后找出最長子序列dp[i]，大于maxLen則更新，否則累加{maxLen = dp[i];asn = count[i];}else if(dp[i] == maxLen) // 遇到相同最長子序列，需要累加所有相同最長子序列{asn += count[i];}}return asn;} };

1.4結(jié)果

1.5復(fù)雜度分析

由上面代碼實現(xiàn)可知，經(jīng)過了雙層遍歷，即時間復(fù)雜度為O(n^2)；申請了n個長度的數(shù)組空間，故空間復(fù)雜度為O(n)。

總結(jié)

以上是生活随笔為你收集整理的求最长递增子序列个数——C++的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。