【Day 56 】2022-05-26 - 673. 最长递增子序列的个数

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/number-of-longest-increasing-subsequence/

前置知识

• 动态规划

  题目描述

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

示例 1:

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

输入: [2,2,2,2,2] 输出: 5 解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。 注意: 给定的数组长度不超过 2000 并且结果一定是32位有符号整数。

[JiangWenqi]

C++

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

[xixiao51]

Idea

Dynamic programing: using dp[i] to record the longest length and cnt[i] to record the nums of longest subsequences.

Code

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int len = nums.length, maxLen = 0, count = 0;
        int[] dp = new int[len];
        int[] cnt = new int[len];
        for(int i = 0; i < len; i++) {
            dp[i] = cnt[i] = 1;
            for(int j = 0; j < i; j++) {
                 // If the current number can be added to form an inscreasing subsequence
                if(nums[i] > nums[j]) {
                    // If the length increase then update the cnt
                    if(dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];
                    } else if(dp[j] + 1 == dp[i]) {
                         // add all subsequences meet the current length
                        cnt[i] += cnt[j];
                    }
                }
            }
            //update global max length and count
            if(dp[i] > maxLen) {
                maxLen = dp[i];
                count = cnt[i];
            } else if(dp[i] == maxLen) {
                count += cnt[i];
            }
        }
        return count;
    }
}

Complexity Analysis

• Time complexity: O(N^2)
• Space complexity: O(N)

[MichaelXi3]

Idea

寻找 LIS 就是在把 array 的每一个 element 进行枚举，只不过枚举的每一个 sequence 必须是 increasing 的。当我们画出来枚举的决策树时，我们发现其中有好多部分是重复的， 所以我们就要用 DP Array

Code

class Solution {

    // LIS: Longest increasing subsequence

    public int findNumberOfLIS(int[] nums) {

    /* dp array: First row counts the length of LIS starting from that index
                 Second row counts the counts of LIS starting from that index */

        int[][] dp = new int[2][nums.length];
        int maxLIS = 0; // Keep track of longest subsequence, cuz we want the counts of it

        // We iterate from right to left to maximize the utility of DP array
        for (int i = nums.length - 1; i >= 0; i--) {
            int curNum = nums[i];
            // Default value
            dp[0][i] = 1;
            dp[1][i] = 1;

            for (int j = i + 1; j < nums.length; j++) {
                int curMaxLIS = dp[0][i];
                                    // We want increasing subsequence!
                if (nums[j] > curNum) {
                                            // Update the current max LIS
                    if (1 + dp[0][j] > curMaxLIS) {
                        dp[0][i] = dp[0][j] + 1;
                        curMaxLIS = dp[0][i];
                        // Update current counts of LIS
                        dp[1][i] = dp[1][j];
                                            // Other branches also with curMaxLIS, count++
                    } else if (1 + dp[0][j] == curMaxLIS) {
                        // Update current counts of LIS
                        dp[1][i] += dp[1][j];
                    }
                }
            }

            if (dp[0][i] > maxLIS) {
                maxLIS = dp[0][i];
            }
        }

        // Find the count of LIS
        int countOfMaxLIS = 0;
        for (int i = 0; i < dp[0].length; i++) {
            if (dp[0][i] == maxLIS) {
                countOfMaxLIS += dp[1][i];
            }
        }

        return countOfMaxLIS;
    }
}

Complexity

• Time: O(n^2)
• Space: O(n)

[ghost]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)

        dp = [[1,1] for _ in range(n)]
        longest = 1

        for i in range(n):
            for j in range(i+1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0]+1
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])

                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        res = 0

        for i in range(n):
            if dp[i][0] == longest:
                res += dp[i][1]

        return res

[xingchen77]

思路

DP更新状态

代码

    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] ->  LIS
        # dp[i][1] -> NumberOfLIS
        dp = [[1, 1] for i in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        # 下面这行代码容易忘记，导致出错
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

复杂度

时间O(n^^2) \ 空间O(n)

[MoonLee001]

思路

动态规划

代码

var findNumberOfLIS = function(nums) {
    const n = nums.length;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(0);
    let maxLen = 0;
    let ans = 0;

    for (let i = 0; i < n; i++) {
        dp[i] = 1;
        cnt[i] = 1;
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j];
                } else if (dp[j] + 1 == dp[i]){
                    cnt[i] += cnt[j];
                }
            } 
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            ans = cnt[i];
        } else if (dp[i] == maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

复杂度分析

• 时间复杂度： o(n^2)
• 空间复杂度： O(n)

[zqwwei]

Code

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) 
    {

        int n = nums.size();
        auto lens = vector<int>(n, 1);
        auto times = vector<int>(n, 1);
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<i; j++)
            {
                if (nums[j] >= nums[i]) continue;
                if (lens[i] < lens[j]+1)
                {
                    lens[i] = lens[j]+1;
                    times[i] = times[j];
                }
                else if (lens[i] == lens[j]+1)
                    times[i] += times[j];
            }
        }

        int result = 0;
        int maxLen = 0;
        for (int i=0; i<n; i++)
        {
            if (maxLen < lens[i])
            {
                maxLen = lens[i];
                result = times[i];
            }
            else if (maxLen == lens[i])
                result += times[i];            
        }
        return result;
    }
};

[KelvinG-LGTM]

思路

300 最长递增子序列 思路: 关键在于定义 dp数组. dp含义: 如必须加上当前值, 递增的子序列的长度是什么. 最后返回max(dp).

代码

# 300 最长递增子序列 
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        dp = [1 for _ in range(len(nums))]

        for i in range(len(nums)): # 101
            cur_max = 1
            for j in range(i): 
                if nums[j] < nums[i]: 
                    cur_max = max(cur_max, dp[j] + 1)
            dp[i] = cur_max
        return max(dp)

复杂度分析

时间复杂度

O(N^2)

空间复杂度

O(N)

[1973719588]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        size = len(nums)
        if size<= 1: return size

        dp = [1 for i in range(size)]
        count = [1 for i in range(size)]

        maxCount = 0
        for i in range(1, size):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j] + 1 > dp[i] :
                        dp[i] = dp[j] + 1
                        count[i] = count[j]
                    elif dp[j] + 1 == dp[i] :
                        count[i] += count[j]
                if dp[i] > maxCount:
                    maxCount = dp[i];
        result = 0
        for i in range(size):
            if maxCount == dp[i]:
                result += count[i]
        return result;

[houmk1212]

思路

两次动态规划；自己的代码没有进一步优化，把计算放在一个循环里。

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
//        dp[i]表示以nums[i]为结尾的递增子串的长度
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]){
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                }
            }
            dp[i] = Math.max(dp[i],1);
        }

        int[] dp2 = new int[n];
        dp2[0] = 1;
        for (int i = 0; i < n; i++) {
            if (dp[i] == 1){
                dp2[i] = 1;
                continue;
            }
            for (int j = 0; j < i; j++) {
                if (dp[j] == dp[i] - 1 && nums[j] < nums[i]){
                    dp2[i] += dp2[j];
                }
            }
        }
        int maxLen = 0;
        for (int i = 0; i < n; i++) {
            if (maxLen < dp[i]) {
                maxLen = dp[i];
            }
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen){
                res+=dp2[i];
            }
        }
        return res;
    }
}

复杂度

• 时间复杂度：O(N2)
• 空间复杂度：O(N)

[currybeefer]

    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] ->  LIS
        # dp[i][1] -> NumberOfLIS
        dp = [[1, 1] for i in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        # 下面这行代码容易忘记，导致出错
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

[HuiWang1020]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int[] dp = new int[nums.length];//LIS
        int[] count = new int[nums.length];//number
        int max = 0;
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        for (int i = 0; i < nums.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    } else if (dp[j] + 1 == dp[i]){
                        count[i] += count[j];
                    }

                }
            }
            max = Math.max(max, dp[i]);
        }

        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (dp[i] == max) {
                res += count[i];
            }
        }
        return res;
    }
}

[hyh331]

Day56 思路

1. dp[i]:到达i处，最长递增子序列长度
2. count[i]：以nums[i]为结尾的字符串，最长递增子序列的个数
3. 递推公式：nums[i]>nums[j]的前提下： a.dp[j]+1 > dp[i], dp[i]=dp[j]+1; count[i]=count[j]; b. dp[j]+1 == dp[i], count[i] +=count[j]

   class Solution {
   public:
   int findNumberOfLIS(vector<int>& nums) {
       int n=nums.size();
       if(n <= 1) return n;
       //初始值为1，因为最少为1
       vector<int> dp(n,1);
       vector<int> count(n,1);
       int maxCount=0;
       for(int i=1; i<n; i++){
           for(int j=0; j<i; j++){
               //
               if(nums[i]>nums[j]){
                   if(dp[j]+1 > dp[i]){
                       dp[i]=dp[j]+1;
                       count[i]=count[j];
                   }else if(dp[j]+1 == dp[i]){
                       count[i] +=count[j];
                   }
               }
               //记录并更新最长子序列长度
               if(dp[i] > maxCount) maxCount=dp[i];
           }
       }
       int res=0;
       for(int i=0; i<n;i++){
           if(maxCount == dp[i]) res +=count[i];
       }
       return res;
   }
   };

   复杂度分析

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

[ZacheryCao]

Code

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[1, 1] for i in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

[zhiyuanpeng]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] ->  LIS
        # dp[i][1] -> NumberOfLIS
        dp = [[1, 1] for i in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        # 下面这行代码容易忘记，导致出错
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

[KennethAlgol]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) 
    {

        int n = nums.size();
        auto lens = vector<int>(n, 1);
        auto times = vector<int>(n, 1);
        for (int i=0; i<n; i++)
        {
            for (int j=0; j<i; j++)
            {
                if (nums[j] >= nums[i]) continue;
                if (lens[i] < lens[j]+1)
                {
                    lens[i] = lens[j]+1;
                    times[i] = times[j];
                }
                else if (lens[i] == lens[j]+1)
                    times[i] += times[j];
            }
        }

        int result = 0;
        int maxLen = 0;
        for (int i=0; i<n; i++)
        {
            if (maxLen < lens[i])
            {
                maxLen = lens[i];
                result = times[i];
            }
            else if (maxLen == lens[i])
                result += times[i];            
        }
        return result;
    }
};

[yinhaoti]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        """
        DP
        TC: O(n^2)
        SC: O(n)
        """
        n = len(nums)
        # dp[i][0] -> LIS
        # dp[i][1] -> NumberOfLIS

        dp = [[1, 1] for _ in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    # print(nums[j], nums[i])
                    # print(dp[i], dp[j])
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
                    # print(dp[i], dp[j])

        # print(dp, longest)
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

[freedom0123]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // 以 i 结尾的最长上升子序列的长度
        int[] f = new int[n + 10];
        // 以 i 结尾的最长上升子序列的个数
        int[] g = new int[n + 10];
        int tem = 0;
        for(int i = 0; i < n; i++) {
            f[i] = g[i]  =1;
            for(int j = 0; j < i; j++) {
                // 说明nums[i] 可以接在 nums[j] 的后面 
                if(nums[i] > nums[j]) {
                    if(f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if(f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }

            }
            tem = Math.max(tem,f[i]);
        }
        int ans = 0;
        for(int i = 0 ; i < n; i++) {
            if(f[i] == tem) ans+=g[i];
        }
        return ans;
    }
}

[Ellie-Wu05]

DP

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        // 以i为结尾的递增子序列的长度
        int[] len = new int[n];
        // 个数
        int[] times = new int[n];
        int max =1;

        for(int i=0;i<n;i++){
            // 单个数字可成为数组，所以肯定有1
            len[i] = times[i] =1;
            for (int j=0;j<i;j++){
                if (nums[j] < nums[i]){
                    if (len[i] < len[j] +1 ){
                        len[i] = len[j] + 1;
                        times[i] = times[j];
                    } else if(len[i] == len[j]+1){
                        times[i] += times[j];
                    }
                }
            }
            max = Math.max(max,len[i]);
        }

        int ans = 0;
        for (int i=0;i<n;i++){
            if (len[i] == max){ 
                ans += times[i];
                }
        }

        return ans;
    }
}

复杂度

时间 On^2 \ 空间 On

[ShawYuan97]

思路

    状态空间：
    dp[i][0]表示递增子序列长度 dp[i][1]表示该长度的序列个数
    when i > j and nums[i] > nums[j]
    dp[i][0] = max(dp[j][0] + 1，dp[i][0]) 
    if 拼接后dp[i][0]变大 dp[i][1] = dp[j][1]
    elif 凭借后dp[i][0]不变 就需要叠加之前的状态 dp[i][1] += dp[j][1]

关键点

• 如何找到最长递增子序列
• 如何对最长递增子序列进行计数

代码

• 语言支持：Python3

Python3 Code:

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        """
        返回最长递增子序列的个数
        """
        n = len(nums)

        dp = [[1,1] for _ in range(n)]
        ans = [1,1]
        longest = 1
        for i in range(1,n):
            for j in range(i):
                if nums[i] > nums[j]:
                    # 需要拼接nums[i] 
                    # 计算dp[i][1]值
                    # 如果拼接后 长度变长 这个判断结构可以选择最长递增子序列
                    if dp[i][0] < dp[j][0] + 1:
                        dp[i][0] = dp[j][0]+1
                        dp[i][1] = dp[j][1]
                        longest = max(longest,dp[i][0])
                    # 如果拼接后长度不变 这个判断结构可以计算最长递增子序列的个数
                    elif dp[i][0] == dp[j][0] + 1:
                        dp[i][1] += dp[j][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0]==longest)

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n^2)$
• 空间复杂度：$O(n)$

[Magua-hub]

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

[L-SUI]

var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        dp[i] = 1;
        cnt[i] = 1;
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; // 重置计数
                } else if (dp[j] + 1 === dp[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            ans = cnt[i]; // 重置计数
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

[Shuchunyu]

class Solution { public int findNumberOfLIS(int[] nums) { int n = nums.length; // 以i为结尾的递增子序列的长度 int[] len = new int[n]; // 个数 int[] times = new int[n]; int max =1;

    for(int i=0;i<n;i++){
        // 单个数字可成为数组，所以肯定有1
        len[i] = times[i] =1;
        for (int j=0;j<i;j++){
            if (nums[j] < nums[i]){
                if (len[i] < len[j] +1 ){
                    len[i] = len[j] + 1;
                    times[i] = times[j];
                } else if(len[i] == len[j]+1){
                    times[i] += times[j];
                }
            }
        }
        max = Math.max(max,len[i]);
    }

    int ans = 0;
    for (int i=0;i<n;i++){
        if (len[i] == max){ 
            ans += times[i];
            }
    }

    return ans;
}

}

[okbug]

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> f(n), g(n);

        int maxValue = 0, count = 0;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) f[i] = f[j] + 1, g[i] = g[j];
                    else if (f[i] == f[j] + 1) g[i] += g[j];
                }
            }

            if (maxValue < f[i]) maxValue = f[i], count = g[i];
            else if (maxValue == f[i]) count += g[i];
        }

        return count;
    }
};

[zhishinaigai]

今天住在李佳琦直播间了，明天再做这道，300还没整明白

代码

class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        int n = nums.size(), maxLen = 0, ans = 0;
        vector<int> dp(n), cnt(n);
        for (int i = 0; i < n; ++i) {
            dp[i] = 1;
            cnt[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (nums[i] > nums[j]) {
                    if (dp[j] + 1 > dp[i]) {
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j]; // 重置计数
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
};

[xiayuhui231]

题目

最长递增子序列的个数

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if(nums.size() <= 1) return nums.size();
        vector<int> dp(nums.size(), 1);
        vector<int>count(nums.size(),1);
        int maxCount = 0;
        for(int i =1;i<nums.size();i++){
            for(int j = 0;j<i;j++){
                if(nums[i] > nums[j]){
                    if(dp[j] + 1 > dp[i]){
                        dp[i] = dp[j] + 1;
                        count[i] = count[j];
                    }else if(dp[j] + 1 == dp[i]){
                        count[i] += count[j];
                    }
                }
                if(dp[i] > maxCount) maxCount = dp[i];
            }
        }
        int result = 0;
        for(int i =0;i<nums.size();i++){
            if(maxCount == dp[i]) result += count[i];
        }
        return result;

    }
};

[LQyt2012]

思路

动态规划

代码

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        length = len(nums)
        max_length = 0
        ans = 0
        dp = [0 for _ in range(length)]
        cnt = [0 for _ in range(length)]
        for i, num in enumerate(nums):
            dp[i] = 1
            cnt[i] = 1
            for j in range(i):
                if num > nums[j]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j]+1
                        cnt[i] = cnt[j]
                    elif dp[j]+1 == dp[i]:
                        cnt[i] += cnt[j]
            if dp[i] > max_length:
                max_length = dp[i]
                ans = cnt[i]
            elif dp[i] == max_length:
                ans +=  cnt[i]
        return ans

复杂度分析

时间复杂度：O(N*N)
空间复杂度：O(1)

[VictorHuang99]

Code:

var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        dp[i] = 1;
        cnt[i] = 1;
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; // 重置计数
                } else if (dp[j] + 1 === dp[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            ans = cnt[i]; // 重置计数
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

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

[miss1]

思路

LIS, 最长上升子序列。

从数组最后一个数开始倒序遍历，求出当前位置为起点时的最长子序列，并记录最长的数量。当前位置的最长子序列长度取决于当前数字以及它后一个数，如果当前数字大于等于后一个数，非升序，LIS为它自己，长度为1。如果当前数子小于后一个数，升序，LIS为它后一个数的LIS + 1(它自己)

代码

var findNumberOfLIS = function(nums) {
  let res = []; // res = [[length, count]]
  for (let i = nums.length - 1; i >= 0; i--) {
    let t = [1, 1];
    for (let j = i + 1; j < nums.length; j++) {
      let next = res[nums.length - 1 - j];
      if (nums[i] < nums[j]) {
        if (next[0] + 1 > t[0]) t = [next[0] + 1, next[1]];
        else if (next[0] + 1 === t[0]) t[1] += next[1];
      }
    }
    res.push(t);
  }
  let num = 0, maxLength = 0;
  for (let i = 0; i < res.length; i++) {
    if (res[i][0] > maxLength) {
      maxLength = res[i][0];
      num = res[i][1];
    }else if (res[i][0] === maxLength) {
      num += res[i][1];
    }
  }
  return num;
};

复杂度

• time: O(n²)
• space: O(n)

[revisegoal]

dp

• 定义状态：dp[i] = 以nums[i]结尾的最长子序列
• 状态转移：nums[j] < nums[i] 下 dp[i] = max(dp[j]) + 1
• 加个cnt数组记录个数

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n];
        int[] cnt = new int[n];
        Arrays.fill(dp, 1);
        Arrays.fill(cnt, 1);
        int maxLen = 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;
                        cnt[i] = cnt[j];
                    } else if (dp[j] + 1 == dp[i]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[i]);
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (dp[i] == maxLen) {
                res += cnt[i];
            }
        }
        return res;
    }
}

• time: O(n ^ 2)
• space: O(n)

[linjunhe]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        dp = [1]*len(nums)
        combination = [1]*len(nums)
        for i in range(len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[j]+1 > dp[i]:
                        dp[i] = dp[j]+1
                        combination[i] = combination[j]
                    elif dp[j]+1 == dp[i]:
                        combination[i] += combination[j]
        maxL = 0
        for i in range(len(dp)):
            maxL = max(maxL, dp[i])

        res = 0
        for i in range(len(dp)):
            if dp[i]==maxL: res += combination[i]
        return res

[mo660]

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

[tensorstart]

思路

dp，维护两个数组，dp[i]表示i之前最长子序列的长度，count[i]表示i之前最长子序列个数

代码

var findNumberOfLIS = function(nums) {
    if(nums.length<=1) return nums.length;
    let dp=new Array(nums.length);
    for (let i = 0; i < dp.length; i++) {
        dp[i]=1;
    }
    let count=new Array(nums.length);
    for (let i = 0; i < count.length; i++) {
        count[i]=1;
    }
    let maxCount=0;
    for (let i = 0; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i]>nums[j]){
                if (dp[j]+1>dp[i]){
                    dp[i]=dp[j]+1;
                    count[i]=count[j];
                }else if (dp[j]+1===dp[i]){
                    count[i]+=count[j];
                }
            }
            if (dp[i]>maxCount)maxCount=dp[i];
        }
    }
    let res=0;
    for (let i = 0; i < nums.length; i++) {
        if (maxCount===dp[i]) res+=count[i];
    }
    return res;
};

复杂度分析

空间O(n^2) 时间O(n)

[ShuqianYang]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        # dp[i][0] ->  LIS
        # dp[i][1] -> NumberOfLIS
        dp = [[1, 1] for i in range(n)]
        ans = [1, 1]
        longest = 1
        for i in range(n):
            for j in range(i + 1, n):
                if nums[j] > nums[i]:
                    if dp[i][0] + 1 > dp[j][0]:
                        dp[j][0] = dp[i][0] + 1
                        # 下面这行代码容易忘记，导致出错
                        dp[j][1] = dp[i][1]
                        longest = max(longest, dp[j][0])
                    elif dp[i][0] + 1 == dp[j][0]:
                        dp[j][1] += dp[i][1]
        return sum(dp[i][1] for i in range(n) if dp[i][0] == longest)

[AConcert]

var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    const dp = new Array(n).fill(0);
    const cnt = new Array(n).fill(0);
    for (let i = 0; i < n; ++i) {
        dp[i] = 1;
        cnt[i] = 1;
        for (let j = 0; j < i; ++j) {
            if (nums[i] > nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    cnt[i] = cnt[j]; 
                } else if (dp[j] + 1 === dp[i]) {
                    cnt[i] += cnt[j];
                }
            }
        }
        if (dp[i] > maxLen) {
            maxLen = dp[i];
            ans = cnt[i]; 
        } else if (dp[i] === maxLen) {
            ans += cnt[i];
        }
    }
    return ans;
};

[xil324]

class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        dp = [1] * n;
        ans = [1] * n;
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]: 
                        ans[i] = ans[j]; 
                        dp[i] = dp[j] + 1; 
                    elif dp[j] + 1 == dp[i]:
                        ans[i] += ans[j];
        return sum(y for x,y in zip(dp, ans) if x == max(dp))
``
time complexity: O(n^2)

[YuyingLiu2021]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        res,dp,cnt = 0,[1]*n,[1]*n
        for i in range(n):
            for j in range(i):
                if nums[j]<nums[i]:
                    if dp[j]+1 > dp[i]:
                        dp[i] = dp[j]+1
                        cnt[i] = cnt[j]
                    elif dp[j]+1 == dp[i]:
                        cnt[i] += cnt[j]
                    else:continue
        for i in range(n):
            if dp[i] == max(dp):res+=cnt[i]
        return res

[rzhao010]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        int max = 1;
        for (int i = 0; i < n; i++) {
            f[i] = g[i] = 1;
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (f[i] < f[j] + 1) {
                        f[i] = f[j] + 1;
                        g[i] = g[j];
                    } else if (f[i] == f[j] + 1) {
                        g[i] += g[j];
                    }
                }
            }
            max = Math.max(max, f[i]);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (f[i] == max) ans += g[i];
        }
        return ans;
    }
}

[wychmod]

思路

动态规划，二维数组的动态规划

代码

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        dp_num = [1] * (n+1)
        longest = 1
        for i in range(n):
            for j in range(i+1, n):
                if nums[j] > nums[i]:
                    if dp[i] + 1 > dp[j]:
                        dp[j] = dp[i] + 1
                        dp_num[j] = dp_num[i]
                        longest = max(longest, dp[j])
                    elif dp[i] + 1 == dp[j]:
                        dp_num[j] += dp_num[i]
        return sum(dp_num[i] for i in range(n) if dp[i] == longest)

复杂度分析

时间复杂度：On^2 空间复杂度：On

[maggiexie00]

def findNumberOfLIS(self, nums: List[int]) -> int:
    n, max_len, ans = len(nums), 0, 0
    dp = [0] * n
    cnt = [0] * n
    for i, x in enumerate(nums):
        dp[i] = 1
        cnt[i] = 1
        for j in range(i):
            if x > nums[j]:
                if dp[j] + 1 > dp[i]:
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j]  
                elif dp[j] + 1 == dp[i]:
                    cnt[i] += cnt[j]
        if dp[i] > max_len:
            max_len = dp[i]
            ans = cnt[i]  
        elif dp[i] == max_len:
            ans += cnt[i]
    return ans

[taojin1992]

/*

# Complexity:
time: O(N^2), N = nums.length
space: O(2*N) -> O(N)
*/

class Solution {
    public int findNumberOfLIS(int[] nums) {
        // dp[i][0]: longest len of increasing subsequence ending at index i
        // dp[i][1]: count of above
        int[][] dp = new int[nums.length][2];
        int maxLen = 1;

        // initialization, each number is an increasing subseq
        for (int i = 0; i < nums.length; i++) {
            dp[i] = new int[]{1,1}; // careful of syntax
        }
        // recurrence (keep tracking of maxLen)
        for (int j = 0; j < nums.length; j++) {
            for (int i = 0; i < j; i++) {
                if (nums[j] > nums[i]) {
                   //说明我们可以拼接。但是拼接与否取决于拼接之后会不会更长。如果更长了就拼，否则不拼。 
                    int curLenByJ = dp[i][0] + 1; // using this i
                    if (curLenByJ > dp[j][0]) {
                        dp[j][1] = dp[i][1];
                        dp[j][0] = curLenByJ; // careful! don't forget
                    } else if (curLenByJ == dp[j][0]) {
                        dp[j][1] += dp[i][1];
                    }
                }
            }
            maxLen = Math.max(maxLen, dp[j][0]);// careful! don't forget
        }

        int count = 0;
        // traverse the count part using the maxLen
        for (int i = 0; i < nums.length; i++) {
            if (dp[i][0] == maxLen) {
                count += dp[i][1];
            }
        }
        return count;
    }
}

[XXjo]

思路

dp

代码

var findNumberOfLIS = function(nums) {
    let n = nums.length;
    let dp = new Array(n).fill(1);  //dp[i]表示以nums[i] 结尾的最长上升子序列的长度
    let count = new Array(n).fill(1); //count[i] 表示以nums[i] 结尾的最长上升子序列的个数
    for(let i = 1; i < n; i++){
        for(let j = 0; j < i; j++){
            if(nums[i] > nums[j]){
                if(dp[i] < dp[j] + 1){
                    dp[i] = dp[j] + 1;
                    count[i] = count[j];
                }
                else if(dp[i] == dp[j] + 1){
                    count[i] += count[j];
                }
            }
        }
    }
    let max = Math.max(...dp);
    let res = 0;
    for(let i = 0; i < n; i++){
        if(dp[i] == max) {
            res += count[i];
        }
    }

    return res;
};

复杂度分析

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

[sallyrubyjade]

/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function (nums) {
    const arr = [{ len: 1, repeat: 1 }];
    for (let i = 1; i < nums.length; i++) {
        const curr = nums[i];
        let max = 0;
        let idx = 1;
        for (let j = 0; j < i; j++) {
            const compare = nums[j];
            if (compare < curr) {
                if (max < arr[j].len) {
                    max = arr[j].len;
                    idx = arr[j].repeat;
                } else if (max === arr[j].len) {
                    idx += arr[j].repeat;
                }
            }
        }
        arr.push({
            len: max + 1,
            repeat: idx,
        });
    }
    let max = 0;
    let idx = 1;
    for (let j = 0; j < arr.length; j++) {
        if (max < arr[j].len) {
            max = arr[j].len;
            idx = arr[j].repeat;
        } else if (max === arr[j].len) {
            idx += arr[j].repeat;
        }
    }
    return idx;
};

[flyzenr]

• 思路

  • 1. 定义状态
       • dp[i]: 到nums[i]的最长子序列的长度
       • count[i]：到nums[i]的最长子序列的个数
  • 2. 初始化状态
       • 因为最长子序列的长度和个数均至少为1
  • 3. 状态转移 dp[i]>dp[j]
       • 1. 如果dp[j] +1 > dp[i]
       • 说明新的长度dp[j] +1，在第i个位置头一次出现，于是更新count[i]状态 count[i] = count[j]+1
       • 2. 如果dp[j] +1 == dp[i]
       • 代表最大长度没变，于是count[i] += 1
  • 4. 记录最长子序列的最大长度 max_length
  • 5. 遍历dp数组，如果记录的长度dp[i]正好是最大长度max_length，那就将count[i]加入到结果res中

• Code

  -

        class Solution:
            def findNumberOfLIS(self, nums: List[int]) -> int:
                n = len(nums)
                # 数组长度为1的时候
                if n == 1: return 1
  
                # 到nums[i]为止的最长递增子序列长度
                dp = [1] * n
                # 到nums[i]为止的最长递增子序列个数
                count = [1] * n
                # 记录整个数组的最长递增子序列长度
                max_length = 0
                for i in range(1, n):
                    for j in range(i):
                        if nums[i] > nums[j]:
                            # 头一次遇到这个长度（到nums[i]为止的最长递增子序列长度）
                            if dp[j] + 1 > dp[i]:
                                # 到nums[i]为止的最长递增子序列数目+1
                                dp[i] = dp[j] + 1
                                count[i] = count[j]
                            # 如果长度正好相等
                            elif dp[j] + 1 == dp[i]:
                                # 记录的最长子序列个数+1
                                count[i] += count[j]
                    max_length = max(max_length, dp[i])
  
                # 最长子序列个数初始化
                res = 0
                for i in range(n):
                    if dp[i] == max_length:
                        res += count[i]
                return res

• 复杂度

  • 动态规划

    • 时间复杂度: $O(n^2)$
    • 空间复杂度 $O(n)$

[TonyLee017]

思路

• 动态规划

  代码

  class Solution:
  def findNumberOfLIS(self, nums: List[int]) -> int:
      n,maxlen,ans = len(nums),0,0
      dp,count = [0]*n,[0]*n
      for i in range(n):
          dp[i],count[i] = 1,1
          for j in range(i):
              if nums[i] > nums[j]:
                  if dp[j] +1 > dp[i]:
                      dp[i] = dp[j] +1
                      count[i] = count[j]
                  elif dp[j] +1 == dp[i]:
                      count[i] += count[j]
          if dp[i] > maxlen:
              maxlen = dp[i]
              ans = count[i]
          elif dp[i] == maxlen:
              ans += count[i]
      return ans

  复杂度分析

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

[houyanlu]

思路

代码

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        vector<int> dp(nums.size(), 1);
        vector<int> count(nums.size(), 1);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (dp[i] < dp[j] + 1) {
                        count[i] = count[j];
                    } else if (dp[i] == dp[j] + 1) {
                        count[i] += count[j];
                    }
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
        }

        int result = 0;
        int maxCount = *max_element(dp.begin(), dp.end());
        for (int i = 0; i < nums.size(); i++) {
            if (maxCount == dp[i]) {
                result += count[i];
            }
        }

        return result;
    }
};

复杂度分析

• 时间复杂度：O(n * n)
• 空间复杂度：O(n)

[gitbingsun]

题目地址(673. 最长递增子序列的个数)

https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

题目描述

给定一个未排序的整数数组 nums ， 返回最长递增子序列的个数 。

注意 这个数列必须是 严格 递增的。

示例 1:

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

示例 2:

输入: [2,2,2,2,2]
输出: 5
解释: 最长递增子序列的长度是1，并且存在5个子序列的长度为1，因此输出5。

提示: 

1 <= nums.length <= 2000
-106 <= nums[i] <= 106

前置知识

动态规划 每次存下来相同递增子序列的个数。 /* dp(i) = max(dp(i-1)+1, dp(i-2)+1, dp(i-3)+1, ...) including ith number the longest increasing subsequence 1 3 5 4 7 dp[0] = 1 dp[1] = max(1, 1+1) = 2 dp[2] = max(1, 2) => 3, 2

*/ class Solution { public: int findNumberOfLIS(vector& nums) { int n = nums.size(); if (n==0) return 0; int res = 0;

    vector<int> dp(n, 1);  // longest non-decreasing subseq ending at i
    vector<int> sameLens(n, 1);

    // 2323
    dp[0] = 1;
    sameLens[0] = 1;
    int index = 0;
    for (int i = 1; i<n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i]>nums[j]) {
                if (dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                    sameLens[i] = sameLens[j];
                } else if (dp[j] + 1 == dp[i] ) {
                    sameLens[i] += sameLens[j];
                }
            } 
        }
    }

    int len=0;
    for (int i = 0; i<n; i++) {
        //cout<<dp[i]<<' '<<sameLens[i]<<endl;
        if (dp[i]>len) {
            res = sameLens[i];
            len = dp[i];
        } else if (dp[i]==len) {
            res += sameLens[i];
        }
    }
    return res;
}

};

**复杂度分析**

令 n 为数组长度。

- 时间复杂度：$O(n)$
- 空间复杂度：$O(n)$

[Yongxi-Zhou]

思路

dp

代码

    class Solution:
        def findNumberOfLIS(self, nums: List[int]) -> int:
            n = len(nums)
            dp = [1 for i in range(n)]
            s = [1 for _ in range(n)]

            for i in range(1, n):
                for j in range(i):
                    if nums[j] < nums[i]:
                        if dp[j] + 1 > dp[i]:
                            dp[i] = dp[j] + 1
                            s[i] = s[j]
                        elif dp[i] == dp[j] + 1:
                            s[i] += s[j]

            # print(dp)
            # print(s)
            res = 0
            maxLength = max(dp)
            for i in range(n):
                if dp[i] == maxLength:
                    res += s[i]
            return res

复杂度

time O(NM) space O(NM)