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

动态规划

要注意统计个数的时候，dp相等时要把之前的数量累加上，dp大的时候则是直接继承之前的数量。

时间复杂度： O(N^2)
空间复杂度：O(N)

func findNumberOfLIS(nums []int) int {
    n := len(nums)
    dp := make([]int, n)
    count := make([]int, n)
    maxLength := 0
    ans := 0

    for i := 0; i < n; i++ {
        dp[i] = 1
        count[i] = 1

        for j := 0; j < i; j++ {
            if nums[i] > nums[j] {
                if dp[j] + 1 == dp[i] {
                    // j位置的所有个数都要加上
                    count[i] += count[j]
                }
                if dp[j] + 1 > dp[i] {
                    dp[i] = dp[j] + 1
                    // 针对j位置的每一种最长子序列都有一个对应的新序列
                    count[i] = count[j]
                }
            }
            
        }

        // 所有最长的子序和都要考虑
        if dp[i] == maxLength {
            ans += count[i]
        }
        if dp[i] > maxLength {
            maxLength = dp[i]
            ans = count[i]
        }
    }

    return ans
}```