【Day 56 】2024-01-10 - 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位有符号整数。

[snmyj]

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

[Chloe-C11]

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

        # 定义状态数组
        # dp[i][0] 表示以 nums[i] 结尾的最长递增子序列的长度
        # dp[i][1] 表示以 nums[i] 结尾的最长递增子序列的个数
        dp = [[1, 1] for _ in range(n)]
        max_length = 1  # 最长递增子序列的长度
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j][0] + 1 > dp[i][0]:  # 如果长度更长，则更新
                        dp[i][0] = dp[j][0] + 1
                        dp[i][1] = dp[j][1]
                    elif dp[j][0] + 1 == dp[i][0]:  # 如果长度相等，则累加个数
                        dp[i][1] += dp[j][1]
            max_length = max(max_length, dp[i][0])  # 更新最长递增子序列长度
        res = 0
        for i in range(n):
            if dp[i][0] == max_length:  # 如果长度等于最长递增子序列长度，则累加个数
                res += dp[i][1]
        return res

[ycan253]

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

        # 定义状态数组
        # dp[i][0] 表示以 nums[i] 结尾的最长递增子序列的长度
        # dp[i][1] 表示以 nums[i] 结尾的最长递增子序列的个数
        dp = [[1, 1] for _ in range(n)]
        max_length = 1  # 最长递增子序列的长度
        for i in range(1, n):
            for j in range(i):
                if nums[j] < nums[i]:
                    if dp[j][0] + 1 > dp[i][0]:  # 如果长度更长，则更新
                        dp[i][0] = dp[j][0] + 1
                        dp[i][1] = dp[j][1]
                    elif dp[j][0] + 1 == dp[i][0]:  # 如果长度相等，则累加个数
                        dp[i][1] += dp[j][1]
            max_length = max(max_length, dp[i][0])  # 更新最长递增子序列长度
        res = 0
        for i in range(n):
            if dp[i][0] == max_length:  # 如果长度等于最长递增子序列长度，则累加个数
                res += dp[i][1]
        return res

[JinhMa]

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length, maxLen = 0, ans = 0;
        int[] dp = new int[n];
        int[] cnt = new int[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;
    }
}

[Danielyan86]

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        nums.append(float('inf'))
        n = len(nums)
        dp = [1]*n  # dp[i] 表示以位置i结尾的最长子序列的长度
        max_cnt = [1]*n  # max_cnt[i] 表示以位置i结尾的最长子序列的个数
        for i in range(1, n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if dp[i] < dp[j] + 1:
                        dp[i] = dp[j] + 1
                        max_cnt[i] = max_cnt[j]
                    elif dp[i] == dp[j] + 1:
                        max_cnt[i] += max_cnt[j]
        return max_cnt[n-1]

[larscheng]

思路

从长度为n的数组nums中找最长递增子序列，并统计一共有多少个

一共两个问题：求最长递增子序列的长度，求这个最大长度的子序列一共有多少个 求最长递增子序列的长度可参考：300.最长递增子序列

遍历nums数组，以nums[i]结尾的最长递增子序列长度dp[i],共有cnt[i]个; dp[i]和cnt[i]默认为1

• i=1时, dp[i] = 1, cnt[i] = 1
• i>1时，dp[i] = Max(dp[i], dp[j] + 1), 0<=j<i,num[j]<num[i]
• 当dp[j] + 1 > dp[i]时，意味着有新的最长递增子序列，记录其个数cnt[j]
• 当dp[j] + 1 == dp[i]时，意味着同一长度的多个递增子序列，cnt[j]个数累加
• 最终取dp最大的cnt值，如果dp最大值有多个则进行累加

代码

    class Solution {
        public int findNumberOfLIS(int[] nums) {
            int n = nums.length, maxLen = 0, ans = 0;
            int[] dp = new int[n];
            int[] cnt = new int[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]) {
                            //又找到1个当前长度的子序列，累加次数
                            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)

[adfvcdxv]

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

[smallppgirl]

方法 ： DP

代码

class Solution:
    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

时间 O(n2)

空间 O(n)