【学会动态规划】最长递增子序列的个数（28）

动态规划怎么学？

学习一个算法没有捷径，更何况是学习动态规划，

跟我一起刷动态规划算法题，一起学会动态规划！

1. 题目解析

这道题的题目非常好理解，就是求出最长的递增子序列的个数，

还是同一个需要注意的地方，就是子序列是可以跳着求的。

2. 算法原理

1. 状态表示

dp[ i ] 表示以 i 位置为结尾的所有子序列中，最长的递增子序列的个数。

而实际上，我们得先知道子序列的长度，才能求个数，

len [ i ] 表示以 i 位置为结尾的所有子序列中，最长的递增子序列的长度。

count [ i ] 表示以 i 位置为结尾的所有子序列中，最长的递增子序列的个数。

2. 状态转移方程

我们设 j 的区间是 0 ~ i - 1

如果是他们自己作为一个子序列，那么 len[ i ] =  count[ i ] = 1

如果是他们自己加上前面任意一个数作为子序列，那么：

遍历区间 0 ~ i - 1，找到 nums[ j ] < nums[ i ] 的情况，然后讨论：

当 len[ j ] + 1 == len[ i ]，count[ i ] += count[ j ]（长度相同的情况）

当 len[ j ] + 1 < len[ i ]，count 不动（长度比现在的最长长度小的情况）

当 len[ j ] + 1 > len[ i ]，len[ i ] = len[ j ] + 1（更新最长的长度并重新计数） count[ i ] = count[ j ]

3. 初始化

都初始化成 1 即可。

4. 填表顺序

从左往右。

5. 返回值

在遍历的时候同时计算。

3. 代码编写

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(), maxCnt = 1, maxLen = 1;
        vector<int> len(n, 1), cnt(n, 1);
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < i; j++) {
                if(nums[j] < nums[i]) {
                    if(len[j] + 1 == len[i]) cnt[i] += cnt[j];
                    else if(len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    }
                }
            }
            if(maxLen == len[i]) maxCnt += cnt[i];
            else if(maxLen < len[i]) maxLen = len[i], maxCnt = cnt[i];
        }
        return maxCnt;
    }
};

写在最后：

以上就是本篇文章的内容了，感谢你的阅读。

如果感到有所收获的话可以给博主点一个赞哦。

如果文章内容有遗漏或者错误的地方欢迎私信博主或者在评论区指出~