Number of Longest Increasing Subsequence

题目描述

解题思路

题目要求我们在一个无序的整数数组里找出最长递增子序列的个数，显而易见，我们可以先找到最长递增子序列对应的长度是多少，接着就是要找这么长的递增子序列有多少个。
针对最长递增子序列，可以选用传统的动态规划解法LIS来解决，即dp[i]代表以下标i对应的数字结尾的序列中最长递增子序列的长度，那么dp[i]就应该在下标i之前比nums[i]数值小的dp长度中取最大值。
但之后的难题是怎么求解总共有多少个这么长的递增子序列呢？其实可以在求解dp[i]的时候额外多加一个vector lsn(lsn[i]代表以下标i对应的数字结尾的序列 最长递增子序列的数目)即可。对于下标比i小的j，如果dp[j]+1>dp[i]那么dp[i]=dp[j]+1;lsn[i]=lsn[j]，（因为nums[j]为结尾的序列后面加上nums[i]，lsn[i]和lsn[j]相同)。但如果dp[j]+1==dp[i],就意味着以nums[i]为结尾的序列的最长递增子序列还可以从nums[j]拼接nums[i]得到，所以此时，lsn[i]+=lsn[j].
废话不多说，直接上代码，简单明了：

C++代码实现

int findNumberofLIS(vector<int>& nums) {
    int N = nums.size();
    vector<int> dp(N, 1);   // dp[i]代表 以当前下标i对应数字 结尾的序列的最长递增子序列的长度 
    vector<int> lsn(N, 1);  // lsn[i]代表当前下标i对应数字为结尾的序列 最长递增子序列 的数目 
    int max = 0, result = 0;;
    for (int i = 1; i < N; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j]+1;
                    lsn[i] = lsn[j];
                } else if (dp[j]+1 == dp[i]) {
                    // nums[j]->nums[i]同样可以达到最长序列长度为dp[i]，故lsn[i]要加上lsn[j] 
                    lsn[i] += lsn[j];
                }
            }
        }
        // 找出最长递增子序列对应的最大长度 
        max = (dp[i] > max)?dp[i]:max;
    }
    for (int i = 0; i < N; ++i) {
        // 可能有多个不同的数字结尾的子序列包含最长子序列，因此要加上其对应的lsn[i] 
        if (dp[i] == max) {
            result += lsn[i];
        }
    }
    return result;
} 

运行截图：