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

这篇具有很好参考价值的文章主要介绍了【学会动态规划】最长递增子序列的个数（28）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

动态规划怎么学？

1. 题目解析

2. 算法原理

1. 状态表示

2. 状态转移方程

3. 初始化

4. 填表顺序

5. 返回值

3. 代码编写

写在最后：

动态规划怎么学？

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

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

1. 题目解析

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

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

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

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;
    }
};