673. 最长递增子序列的个数 ❤

673. 最长递增子序列的个数

给定一个未排序的整数数组，找到最长递增子序列的个数。滴滴面试

输入: [1,3,5,4,7]
输出: 2
解释:** 有两个最长递增子序列，分别是 [1, 3, 4, 7] 和[1, 3, 5, 7]。

思路：这道题可以说是 300.最长上升子序列 的进阶版本

参考：

• 确定dp数组（dp table）以及下标的含义

这道题目我们要一起维护两个数组。
dp[i]：i之前（包括i）最长递增子序列的长度为dp[i]
count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]

• 确定递推公式

在300.最长上升子序列 中，我们给出的状态转移是：
if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
即：位置i的最长递增子序列长度 等于j从0到i-1各个位置的最长升序子序列 + 1的最大值。

本题就没那么简单了，我们要考虑两个维度，一个是dp[i]的更新，一个是count[i]的更新。
那么如何更新count[i]呢？

以nums[i]为结尾的字符串，最长递增子序列的个数为count[i]。
1，那么在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 > dp[i]，说明找到了一个更长的递增子序列。
那么以j为结尾的子串的最长递增子序列的个数，就是最新的以i为结尾的子串的最长递增子序列的个数，即：count[i] = count[j]。

2，在nums[i] > nums[j]前提下，如果在[0, i-1]的范围内，找到了j，使得dp[j] + 1 == dp[i]，说明找到了两个相同长度的递增子序列。那么以i为结尾的子串的最长递增子序列的个数 就应该加上以j为结尾的子串的最长递增子序列的个数，即：count[i] += count[j];

//动规，dp=以i结尾最长序列，cnt=dp的频次
//时间On^2,空间On
func findNumberOfLIS(nums []int) int {
    dp := make( []int, len(nums))
    cnt := make( []int, len(nums))
    res:= 0
    for i := 0 ; i < len(nums) ; i++{
        dp[i] = 1                       //dp[i] 记录到当前节点i的最大长度，=到i节点的最大序列
        cnt[i] = 1               // 重复的个数 cnt = dp[i]次数，到i节点最大序列个数，即相等队列中有几种
        for j := 0;j < i; j++{
            if nums[i] > nums[j]{
                if dp[j] + 1 >  dp[i] {     
                    dp[i] = dp[j] +1            // 更新 dp[i]放在这里，就不用max了
                    cnt[i] = cnt[j] 
                    continue
                }
                if dp[i] == dp[j] + 1{
                    cnt[i] += cnt[j] 
                    continue
                }
            }
        }
        res = max(dp[i], res)  
    }
    sum := 0
    //最后还有再遍历一遍dp[i]，把最长递增序列长度对应的cnt[i]累计下来就是结果了。
    for i := 0 ; i < len(dp) ; i++{     
        if dp[i] == res{
            sum += cnt[i]
        }
    }
    return sum
}
func max( a, b int) int {
    if a > b {
        return a
    }
    return b
}