azl397985856 commented 2 years ago

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位有符号整数。

KennethAlgol commented 2 years ago


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

zwx0641 commented 2 years ago

class Solution { public int findNumberOfLIS(int[] nums) { int[] dp = new int[nums.length]; int[] comb = new int[nums.length]; Arrays.fill(dp, 1); Arrays.fill(comb, 1);

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

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

}

RMadridXDH commented 2 years ago

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

charlestang commented 2 years ago

思路

动态规划。使用 dp 数组，记录以第 i 个元素为结尾的子序列的长度。使用 cnt 数组，记住第 i 个元素为结尾的子序列的数量。

dp[i] = dp[j] + 1, if nums[i] > nums[j]

cnt[i] = cnt[j], if dp[j] + 1 > dp[i]

     = cnt[i] + cnt[j], if dp[j] + 1 = dp[i]

为什么是这样的呢？因为如果相同长度的子序列出现了两个，那么排列可能性就会增加，需要单独计数。

代码

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1] * n
        cnt = [1] * n
        maxLen, ans = 1, 1

        for i in range(1, n):
            for j in range(i):
                if nums[i] > 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] > maxLen:
                maxLen = dp[i]
                ans = cnt[i]
            elif dp[i] == maxLen:
                ans += cnt[i]
        return ans

时间复杂度 O(n^2)

空间复杂度 O(n)

youzhaing commented 2 years ago

思路

动态规划

代码

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n, max_len, ans = len(nums), 0, 0
        #dp记录长度，cnt记录该长度下不同序列的个数
        dp, cnt = [0] * n, [0] * n
        for idx1, num in enumerate(nums):
            dp[idx1] = 1
            cnt[idx1] = 1
            for idx2 in range(idx1):
                if num > nums[idx2]: #idx1数字较大才可以记录
                    if dp[idx2] + 1 > dp[idx1]:
                        #找idx1前面的最长的序列
                        dp[idx1] = dp[idx2] + 1
                        cnt[idx1] = cnt[idx2]
                    elif dp[idx2] + 1 == dp[idx1]:
                        cnt[idx1] += cnt[idx2]
            if dp[idx1] > max_len:
                max_len = dp[idx1]
                ans = cnt[idx1]
            elif dp[idx1] == max_len:
                ans += cnt[idx1]
        return ans

复杂度

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

空间复杂度：O(N)

chakochako commented 2 years ago

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        d, cnt = [], []
        for v in nums:
            i = bisect(len(d), lambda i: d[i][-1] >= v)
            c = 1
            if i > 0:
                k = bisect(len(d[i - 1]), lambda k: d[i - 1][k] < v)
                c = cnt[i - 1][-1] - cnt[i - 1][k]
            if i == len(d):
                d.append([v])
                cnt.append([0, c])
            else:
                d[i].append(v)
                cnt[i].append(cnt[i][-1] + c)
        return cnt[-1][-1]

def bisect(n: int, f: Callable[[int], bool]) -> int:
    l, r = 0, n
    while l < r:
        mid = (l + r) // 2
        if f(mid):
            r = mid
        else:
            l = mid + 1
    return l

QinhaoChang commented 2 years ago

n=len(nums) lis=[1]*n

lis[i] is the length of LIS having last element as nums[i]

    noOfLIS=[1]*n
    #noOfLIS[i] is the no. of LIS having last element as nums[i]
    for i in range(n):
        for j in range(i):
            if nums[i]>nums[j]: 
                if lis[j]+1==lis[i]:
                    noOfLIS[i]+=noOfLIS[j]#update by no. of LIS till jth position
                if lis[j]+1>lis[i]:
                    noOfLIS[i]=noOfLIS[j]#set to no. of LIS till jth position
                lis[i]=max(lis[i],lis[j]+1)
    ans=0
    maxi=max(lis)
    for i in range(n):
        if lis[i]==maxi:
            ans+=noOfLIS[i]
    return ans

LannyX commented 2 years ago

思路

DP

代码

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

复杂度分析

时间复杂度：O(n2)
空间复杂度：O(n)

zhangzz2015 commented 2 years ago

思路

利用dp方法计算LIS方法，我们需要记录两个状态，1个为以i 结尾子序列最长长度，以及该长度有多少个子序列。dp1[i]为最长的长度，dp2[i]为该长度下的个数。
dp1[i] j from 0, to i-1, if(nums[i]>nums[j]) if(dp1[j]+1> imax) 跟新imax 以及该长度的个数，如果dp1[j]+1 == imax ，则累加个数。
时间复杂度为O(n^2)，空间复杂度为 O(n)。

关键点

代码

语言支持：C++

C++ Code:


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

        //  use dp method. 

        // dp1[i]   j from 0, to i-1,  if(nums[i]>nums[j])  find max. and if has couple max.  Sum. 
        // dp2[i]   
    // [1,2,4,3,5,4,7,2]
    //  1 2 3 5 7 
    //  1 2 4 5 7
    //  1 2 3 4 7     
        vector<int> dp1(nums.size()); 
        vector<int> dp2(nums.size()); 
        int imaxLIS =0; 
        for(int i=0; i< nums.size(); i++)
        {
            int imax =1;
            int ret =1; 
            for(int j=0; j<i; j++)
            {
                if(nums[i]>nums[j])
                {
                    if(dp1[j]+1>imax)
                    {
                        imax = dp1[j]+1; 
                        ret=dp2[j]; 
                    }
                    else if(dp1[j]+1==imax)
                    {
                        ret+=dp2[j]; 
                    }
                }
            }
            dp1[i] = imax; 
            dp2[i] = ret;             
            imaxLIS = max(imaxLIS, imax); 
        }
        int ret =0; 
        for(int i=0; i< nums.size(); i++)
        {
            if(dp1[i] == imaxLIS)
            {
                ret += dp2[i]; 
            }
        }
        return ret;         
    }
};

Toms-BigData commented 2 years ago

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

思路

dp

golang代码

func findNumberOfLIS(nums []int) (ans int) {
    maxLen := 0
    n := len(nums)
    dp := make([]int, n)
    cnt := make([]int, n)
    for i, x := range nums{
        dp[i] = 1
        cnt[i] = 1
        for j, y := range nums[:i]{
            if x > y {
                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
}

复杂度

时间:O(n2) 空间:O(n)

xinhaoyi commented 2 years ago

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

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

示例 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位有符号整数。

思路一

动态规划

dp[i]：到nums[i]为止的最长递增子序列长度 count[i]：到nums[i]为止的最长递增子序列个数

初始化状态 dp = [1] * n：代表最长递增子序列的长度至少为1 count = [1] * n：代表最长递增子序列的个数至少为1

状态转移对于每一个数nums[i]，看在它之前的数nums[j]（0<= j < i ）是否比当前数nums[i]小，如果nums[i] > nums[j]，那么相当于到nums[j]为止的最长递增子序列长度到nums[i]增加了1，到nums[i]为止的最长递增子序列长度就变成了dp[i] = dp[j] + 1；但是因为满足nums[i] > nums[j] 的nums[j]不止一个，dp[i]应该取这些dp[j] + 1的最大值，并且这些dp[j] + 1还会有相等的情况，一旦相等，到nums[i]为止的最长递增子序列个数就应该增加了。因此，具体的状态转移如下，在nums[i] > nums[j]的大前提下：

如果dp[j] + 1 > dp[i]，说明最长递增子序列的长度增加了，dp[i] = dp[j] + 1，长度增加，数量不变 count[i] = count[j] 如果dp[j] + 1 == dp[i]，说明最长递增子序列的长度并没有增加，但是出现了长度一样的情况，数量增加 count[i] += count[j]

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        //如果dp[j] + 1 > dp[i]，说明最长递增子序列的长度增加了，dp[i] = dp[j] + 1，长度增加，数量不变 count[i] = count[j]
        //如果dp[j] + 1 == dp[i]，说明最长递增子序列的长度并没有增加，但是出现了长度一样的情况，数量增加 count[i] += count[j]
        int n = nums.length;
        //特殊处理
        if(n == 1) return 1;

        //定义两个状态量数组
        int[] dp = new int[n];
        int[] count = new int[n];

        //填充初值
        Arrays.fill(dp, 1);
        Arrays.fill(count, 1);
        int maxLength = 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];
                    }
                }
            }
            maxLength = Math.max(maxLength, dp[i]);
        }

        int res = 0;
        for(int i = 0; i < n; i++){
            if(dp[i] == maxLength){
                res += count[i];
            }
        }
        return res;
    }
}

复杂度分析

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

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

qiaojunch commented 2 years ago

class Solution: def findNumberOfLIS(self, nums: List[int]) -> int: if not nums: return 0 n = len(nums) m, dp, cnt = 0, [1] n, [1] n for i in range(n): for j in range(i): if nums[j] < nums[i]: if dp[i] < dp[j]+1: dp[i], cnt[i] = dp[j]+1, cnt[j] elif dp[i] == dp[j]+1: cnt[i] += cnt[j] m = max(m, dp[i])
return sum(c for l, c in zip(dp, cnt) if l == m)

Time: o(n^2)

Tesla-1i commented 2 years ago

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        d, cnt = [], []
        for v in nums:
            i = bisect(len(d), lambda i: d[i][-1] >= v)
            c = 1
            if i > 0:
                k = bisect(len(d[i - 1]), lambda k: d[i - 1][k] < v)
                c = cnt[i - 1][-1] - cnt[i - 1][k]
            if i == len(d):
                d.append([v])
                cnt.append([0, c])
            else:
                d[i].append(v)
                cnt[i].append(cnt[i][-1] + c)
        return cnt[-1][-1]

def bisect(n: int, f: Callable[[int], bool]) -> int:
    l, r = 0, n
    while l < r:
        mid = (l + r) // 2
        if f(mid):
            r = mid
        else:
            l = mid + 1
    return l

AlduinLeung commented 2 years ago


/**
 * @param {number[]} nums
 * @return {number}
 */
var findNumberOfLIS = function(nums) {
  const dp = new Array(nums.length).fill(1);
  const cnt = new Array(nums.length).fill(1);
  let res = 0, maxlen = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        // Math.max...的写法
        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];
      res = cnt[i];
    } else if (dp[i] === maxlen) {
      res += cnt[i];
    }
  }
  return res;
};

haixiaolu commented 2 years ago

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # dp

        dp = {}  # key = index, value = [length of Longest Increasing Sub, count]
        lenLIS, res = 0, 0 # length of LIS, count of LIS

        # i = start of subsequence
        for i in range(len(nums) - 1, -1, -1): # backwards
            max_length, max_count = 1, 1 # lenght, count of LIS start from i

            for j in range(i + 1, len(nums)):
                if nums[j] > nums[i]: # make sure increasing order
                    length, count = dp[j] # length, count of LIS start from j
                    if length + 1 > max_length:
                        max_length, max_count = length + 1, count 
                    elif length + 1 == max_length: 
                        max_count += count

            if max_length > lenLIS:
                lenLIS, res = max_length, max_count
            elif max_length == lenLIS:
                res += max_count

            dp[i] = [max_length, max_count]

        return res

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

yan0327 commented 2 years ago

func findNumberOfLIS(nums []int) int {
    n := len(nums)
    out := 0
    maxLen := 0
    dp := make([]int,n)
    count := make([]int,n)
    for i,x := range nums{
        dp[i] = 1
        count[i] = 1
        for j,y := range nums[:i]{
            if x > y{
                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] > maxLen{
            maxLen = dp[i]
            out = count[i]
        }else if dp[i] == maxLen{
            out += count[i]
        }
    }
    return out
}

falconruo commented 2 years ago

思路:

动态规划

复杂度分析:

时间复杂度: O(N^2), N为数组长度
空间复杂度: O(N)

代码(C++):

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

        if (n <= 1) return n;

        vector<int> dp(n, 1);
        vector<int> ct(n, 1);

        int maxL = 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;
                        ct[i] = ct[j];
                    }
                    else if (dp[j] + 1 == dp[i])
                        ct[i] += ct[j];
            maxL = max(maxL, dp[i]);
        }

        int res = 0;
        for (int i = 0; i < n; ++i) {
            if (dp[i] == maxL)
                res += ct[i];
        }

        return res;
    }
};

davidcaoyh commented 2 years ago

class Solution { public int findNumberOfLIS(int[] nums) { int dp[] = new int[nums.length]; int count[] = new int[nums.length]; Arrays.fill(dp,1); Arrays.fill(count,1);

    for(int i = 1; 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];
                }
            }
        }
    }

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

}

}

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

ZacheryCao commented 2 years ago

Idea

Dynamic programming + binary search

Code

class Solution(object):
    def findNumberOfLIS(self, nums):
        if not nums: return 0
        m=min(nums)-1
        a,b=[{m:1}],[m]
        for x in nums:
            i,t=bisect_left(b,x)-1,0
            if i==len(a)-1:
                a.append({})
                b.append(x)
            for y in list(a[i].keys()):
                if y<x: t+=a[i][y]
                else: del a[i][y]
            a[i+1][x]=a[i+1].get(x,0)+t
            b[i+1]=min(b[i+1],x)
        return sum(a[-1].values())

Complexity:

Time: O(N log N) Space: O(N)

feifan-bai commented 2 years ago

思路

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(N^N)
空间复杂度：O(1)

tongxw commented 2 years ago

思路

LIS模板：dp(i) = max(dp(j) + 1) 0<=j < i 然后针对每个dp(i)，当出现LIS时，对LIS进行计数

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        int[] counts = new int[n];
        int maxLen = 1;
        for (int i=0; i<n; i++) {
            dp[i] = 1;
            counts[i] = 1;
            for (int j=0; j<i; j++) {
                if (nums[i] > nums[j]) {
                    int len = dp[j] + 1;
                    if (len > dp[i]) {
                        dp[i] = len;
                        counts[i] = counts[j];
                    } else if (len == dp[i]) {
                        counts[i] += counts[j];
                    }
                }
            }

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

        int total = 0;
        for (int i=0; i<n; i++) {
            if (dp[i] == maxLen) {
                total += counts[i];
            }
        }

        return total;
    }
}

TC: O(n^2) SC: O(n)

pwqgithub-cqu commented 2 years ago

思路 DP

代码 class Solution { public int findNumberOfLIS(int[] nums) { int[] dp = new int[nums.length]; int[] count = new int[nums.length]; Arrays.fill(dp, 1); int max = 1; for(int i = 0; i < nums.length; i++){ count[i] = 1; for(int j = 0; j < i; j++){ if(nums[j] < nums[i]){ 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]; } } } max = Math.max(max, dp[i]); } int ans = 0; for(int i = 0; i < dp.length; i++){ if(dp[i] == max){ ans += count[i]; } } return ans; } } 复杂度分析

时间复杂度：O(n2) 空间复杂度：O(n)

LinnSky commented 2 years ago

思路

动态规划

代码

     var findNumberOfLIS = function(nums) {
        let dp = [];
        for (let i of nums) { // O(n)
            if (dp.length === 0) {
                dp.push([[i],[1]]); // [[tailElementArr, prefixArr]]
            } else {
                let l = 0, r = dp.length - 1;
                while (l < r) { // O(logN)
                    // find first >= i
                    let m = Math.floor((l+r)/2);
                    let c = dp[m][0];
                    if (c[c.length-1] >= i) r = m;
                    else l = m + 1;
                }
                if (dp[l][0][dp[l][0].length - 1] >= i) {
                    if (l === 0) {
                        dp[l][0].push(i);
                        dp[l][1].push(dp[l][1][dp[l][1].length - 1] + 1);
                    } else {
                        let ll = 0, rr = dp[l-1][0].length - 1;
                        // find < i first
                        while (ll < rr) {
                            let mm = Math.floor((ll+rr)/2);
                            if (dp[l-1][0][mm] < i) rr = mm;
                            else ll = mm + 1;
                        }
                        let c = dp[l-1][1];
                        let cnt = ll-1 >= 0 ? c[c.length-1] - c[ll-1] : c[c.length-1];
                        dp[l][0].push(i);
                        dp[l][1].push(dp[l][1][dp[l][1].length-1] + cnt);
                    }
                } else {
                    let ll = 0, rr = dp[l][0].length - 1;
                    // find < i first
                    while (ll < rr) {
                        let mm = Math.floor((ll+rr)/2);
                        if (dp[l][0][mm] < i) rr = mm;
                        else ll = mm + 1;
                    }
                    let c = dp[l][1];
                    let cnt = ll-1 >= 0 ? c[c.length-1] - c[ll-1] : c[c.length-1];
                    dp.push([[i], [cnt]]);
                }
            }
        }
        return dp[dp.length-1][1][dp[dp.length-1][1].length - 1];
    }

ZJP1483469269 commented 2 years ago

class Solution {
    public int findNumberOfLIS(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][2];
        int max = 1;
        for(int i = 0 ;i < n ;i++){
            dp[i][1] = 1;
            dp[i][0] = 1;
            for(int j = 0 ; j < i ;j++){
                if(nums[i] > nums[j]){
                    if(dp[i][0] < dp[j][0] + 1){
                        dp[i][1] = dp[j][1];
                        dp[i][0] = dp[j][0] + 1;
                    }else if(dp[i][0] == dp[j][0] + 1){
                        dp[i][1] += dp[j][1];
                    }    
                }

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

zhiyuanpeng commented 2 years ago

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)

CoreJa commented 2 years ago

思路

这个题还有贪心+二分+前缀和优化大法，明天再实现！

DP：和300类似，只是题目变成了数LIS的个数。可以用相同的方法求LIS的长度，dp数组设为llis，则llis[i]表示以nums[i]结尾的LIS的长度。同时基于llis维护一个nlis数组表示以nums[i]结尾的LIS的个数[^dp定义]。则显然有这样的状态转移方程$nlis[i]=\sum_{0\leq j<i} nlis[j]\quad (llis[j]+1=llis[i], nums[i]>nums[j]) $。即nlis[i]为其前面所有llis[j]+1=llis[i]的nlis[j]的和。也很容易理解，长度为n的LIS个数一定是长度为n-1的LIS个数的和。复杂度$O(n^2)$
贪心+二分法：LC300思路的延续。300中维护的LIS候选人是一维数组，它留下的是长度为i的LIS末尾元素的最小值，舍弃了其他结果，而673算的是lis的个数，所以我们维护一个二维的LIS候选人，它会保留所有历史信息，同时它是有序的，此外它还要额外记录一个信息：该元素为结尾的LIS的个数，也就是DP思路中的nlis，其推导也和DP一样，通过对长度为i-1的行中小于该元素的nlis求和即可。所以这个LIS候选人是个二维二元的tuple，它其实就是原先dp方案的浓缩，区别在于它是有序的，所以可以通过二分法来快速定位。复杂度$O(n(\log n+\log m+m))$，m某一长度的LIS的个数。具体的，遍历nums 的过程中，对于nums[i]
- 如果它比所有LIS候选人的最小值都大，那它对LIS的长度增加有贡献，另起一行，统计nlis
- 否则就二分查找，找到离它最近但大于它的那一行，加入该行，统计nlis
返回最后一行的nlis之和。

代码

class Solution:
    # DP：和300类似，只是题目变成了数LIS的个数。可以用相同的方法求LIS的长度，dp数组设为`llis`，则`llis[i]`表示以`nums[i]`
    # 结尾的LIS的长度。同时基于`llis`维护一个`nlis`数组表示**以`nums[i]`结尾的LIS的个数**[^dp定义]。则显然有这样的状态转
    # 移方程$nlis[i]=\sum_{0\leq j<i} nlis[j]\quad (llis[j]+1=llis[i], nums[i]>nums[j]) $。即`nlis[i]`为其前面所有
    # `llis[j]+1=llis[i]`的nlis[j]的和。也很容易理解，长度为n的LIS个数一定是长度为n-1的LIS个数的和。复杂度$O(n^2)$
    def findNumberOfLIS1(self, nums: List[int]) -> int:
        n = len(nums)
        llis = [1] * n
        nlis = [1] * n
        for i in range(n):
            for j in range(i):
                if nums[i] > nums[j]:
                    if llis[j] + 1 > llis[i]:
                        llis[i] = llis[j] + 1
                        nlis[i] = nlis[j]
                    elif llis[j] + 1 == llis[i]:
                        nlis[i] += nlis[j]
        l = max(llis)
        return sum([nlis[i] for i in range(n) if llis[i] == l])

    # 贪心+二分法：LC300思路的延续。300中维护的**LIS候选人**是一维数组，它留下的是长度为`i`的LIS末尾元素的最小值，舍弃了其
    # 他结果，而673算的是lis的个数，所以我们维护一个二维的**LIS候选人**，它会保留所有历史信息，同时它是有序的，此外它还要额
    # 外记录一个信息：该元素为结尾的LIS的个数，也就是DP思路中的`nlis`，其推导也和DP一样，通过对长度为`i-1`的行中小于该元素
    # 的`nlis`求和即可。
    # 所以这个LIS候选人是个二维二元的`tuple`，它其实就是**原先dp方案的浓缩**，区别在于它是**有序的**，所以可以通过二分法来
    # 快速定位。复杂度$O(n(\log n+\log m+m))$，m某一长度的LIS的个数。具体的，遍历`nums` 的过程中，对于`nums[i]`
    # - 如果它比所有LIS候选人的最小值都大，那它对LIS的长度增加有贡献，另起一行，统计`nlis`
    # - 否则就二分查找，找到离它最近但大于它的那一行，加入该行，统计`nlis`
    # 返回最后一行的`nlis`之和。
    def findNumberOfLIS(self, nums: List[int]) -> int:
        ans = [[(nums[0], 1)]]
        for i in range(1, len(nums)):
            if nums[i] > ans[-1][0][0]:
                left = len(ans)
                ans.append([])
            else:
                left, right = 0, len(ans) - 1
                while left < right:
                    mid = (left + right) // 2
                    if nums[i] > ans[mid][0][0]:
                        left = mid + 1
                    else:
                        right = mid
            cnt = 0
            if left:
                idx = bisect.bisect_left(ans[left - 1], nums[i], key=lambda x: x[0])
                for t in range(idx):
                    cnt += ans[left - 1][t][1]
            else:
                cnt = 1
            ans[left] = [(nums[i], cnt)] + ans[left]
        return sum([x for _, x in ans[-1]])

z1ggy-o commented 2 years ago

思路

因为最长子序列可能不止一个，只知道子序列的长度不能得到答案。所以，我们需要知道两个东西，一个是最长子序列有多长，一个是各个最长子序列有几个。

我们在构建子序列的过程中，记录以各个数为结尾的最长子序列的长度。同时，还要记录以各个数结尾的最长子序列的个数。

具体来看，以 nums[i] 为结尾的最长子序列，是 nums[i] 之前其他数字结尾的最长子序列的末尾加上 nums[i]。以 nums[i] 之前数字结尾的每个最长子数列都可以和 nums[i] 结合成新的最长子数列。以此，我们可以知道以各个数字为结尾的最长子数列的个数。

代码

CPP

class Solution {
public:
    int findNumberOfLIS(vector<int> &nums) {
        // dp[i]: lenght of the longest seq that ends of nums[i]
        vector<int> dp(nums.size(), 1);
        // cnt[i]: # of longest seq that ends of nums[i] (or how many dp[i])
        vector<int> cnt(nums.size(), 1);

        int max_len = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {  // can create a new seq
                    if (dp[j] + 1 > dp[i]) { // get a longer seq
                        dp[i] = dp[j] + 1;
                        cnt[i] = cnt[j];  // new seq based on previous seq, thus cnt does not change
                    } else if (dp[i] == dp[j] + 1) {  // find a new prefix
                        cnt[i] += cnt[j];  // every previous longest seq can combine with nums[i] to get a new longest seq
                    }
                }
            }
            max_len = max(max_len, dp[i]);
        }

        int ans = 0;
        for (int i = 0; i < dp.size(); i++) {
            if (dp[i] == max_len)
                ans += cnt[i];
        }

        return ans;
    }
};

复杂度分析

时间：O(n^2), each iteration, we do 1, 2, 3, ..., n-1 operations
空间：O(n)

hx-code commented 2 years ago

xianxianxianyu commented 2 years ago

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

ChenJingjing85 commented 2 years ago

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [1 for _ in range(n)] #以i结尾的最长递增子序列(长度)
        dp2 = [1 for _ in range(n)] #以i结尾的最长递增子序列(个数)
        for i in range(1, n):
            for j in range(0, i):
                if nums[i] > nums[j] :
                    if dp[j] + 1 == dp[i]:
                        dp2[i] += dp2[j]
                    elif dp[j] + 1 > dp[i]:
                        dp[i]  = dp[j]+1
                        dp2[i] = dp2[j]
        m = max(dp)
        ans = 0
        for i in range(n):
            if dp[i] == m:
                ans += dp2[i]
        return ans

JudyZhou95 commented 2 years ago

代码

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)

复杂度

TC: O(N^2) SC: O(N)

1149004121 commented 2 years ago

最长递增子序列的个数

思路

要知道以num结尾的最长子序列个数，就要知道比前面比num小的并以其结尾的最长子序列个数及长度。参考「300. 最长递增子序列」的写法，保存一个递增栈，由于要计数，每次替换数字的行为换成保存一个该层的列表，并在列表结尾加入新数，而这个列表必然有单调不增。

代码

function findNumberOfLIS(nums: number[]): number {
    let d: number[][] = [];
    let cnt: number[][] = [];
    for(let num of nums){
        let layer = binarySearch1(d, num);
        let c = 1;
        if(layer > 0){
            let index = binarySearch2(d[layer - 1], num);
            c = cnt[layer - 1][cnt[layer - 1].length - 1] - cnt[layer - 1][index];
        };
        if(layer === d.length){
            let dList = [];
            dList.push(num);
            d.push(dList);
            let cntList = [0];
            cntList.push(c);
            cnt.push(cntList);
        }else{
            d[layer].push(num);
            cnt[layer].push(c + cnt[layer][cnt[layer].length - 1]);
        }
    };
    return cnt[cnt.length - 1][cnt[cnt.length - 1].length - 1];

    //返回应该插入的那一层
    function binarySearch1(d, target): number{
        let l = 0, r = d.length;
        while(l < r){
            let mid = (l + r) >>> 1;
            if(d[mid][d[mid].length - 1] < target){
                l = mid + 1;
            }else{
                r = mid;
            }
        };
        return l;
    };
    //返回比layer-1层中比target小的数的坐标
    function binarySearch2(list, target){
        let l = 0, r = list.length - 1;
        while(l < r){
            let mid = (l + r) >>> 1;
            if(list[mid] < target){
                r = mid;
            }else {
                l = mid + 1;
            };
        };
        return l;
    }
};

复杂度分析

时间复杂度：O(NlogN)。
空间复杂度：O(N)。

arteecold commented 2 years ago

最长子序列有多长，各个最长子序列有几个

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)

O(N)^2

Richard-LYF commented 2 years ago

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

    n, max_len, ans = len(nums), 0, 0

    dp =[1] * n

    cnt =[1] * n

    for i in range(n):
        for j in range(i):
            if nums[j]<nums[i]:
                if dp[i]< dp[j] + 1:
                    dp[i] = dp[j] + 1
                    cnt[i] = cnt[j] 
                elif dp[i] == dp[j] + 1:
                    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

on2 on

callmeerika commented 2 years ago

思路

动态规划

代码

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

复杂度

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

hdyhdy commented 2 years ago

思路：动态规划

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

    for i, x := range nums {
        dp[i] = 1
        cnt[i] = 1
        for j, y := range nums[:i] {
            if x > y {
                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 
}

时间复杂度：O（n2）空间复杂度：O(n)

GaoMinghao commented 2 years ago

思路

动态规划，这道题一开始的思路是模拟BFS用树来解决，像这样

    public int findNumberOfLIS_SLOW(int[] nums) {
        Queue<Integer> queue = new LinkedList<>();
        for(int i = 0; i < nums.length; i ++) {
            queue.add(i);
        }
        int ans = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            ans = size;
            for(int i = 0; i < size; i++) {
                int currentIndex = queue.poll();
                for(int j = currentIndex+1; j < nums.length; j++) {
                    if(nums[j] > nums[currentIndex])
                        queue.add(j);
                }
            }
        }
        return ans;
    }

但是发现超时，想说，可以将一些重复的情况进行记录，避免重复计算，但是试了一波发现没办法很好的追踪每一个值的访问情况，就看了下题解，题目可以说是求最长子序列长度的变体，但是需要更多一个变量来追踪可以达到这个长度的方法数，这个部分没有想到

代码

    public int findNumberOfLIS(int[] nums) {
        if(nums.length == 1)
            return 1;
        int longest = 1;
        int[][] dp = new int[nums.length][2];
        for(int i = 0; i < dp.length; i++) {
            dp[i][0] = dp[i][1] = 1;
        }
        for(int i = 0; i < nums.length; i++) {
            for(int j = i+1; j < nums.length; j++) {
                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 = Math.max(longest, dp[j][0]);
                    } else if(dp[i][0] + 1== dp[j][0]) {
                        dp[j][1] += dp[i][1];
                    }
                }
            }
        }
        int sum = 0;
        for (int[] ints : dp) {
            if (ints[0] == longest)
                sum += ints[1];
        }
        return sum;
    }

时间复杂度

O(N^2)

ozhfo commented 2 years ago

思路

动态规划

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        for(int i = 0; i < dp.length; i++) dp[i] = 1;
        int[] count = new int[nums.length];
        for(int i = 0; i < count.length; i++) count[i] = 1;

        int maxCount = 0;
        for (int i = 1; i < nums.length; 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.length; i++) {
            if (maxCount == dp[i]) result += count[i];
        }
        return result;
    }
}

复杂度

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

732837590 commented 2 years ago

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

shamworld commented 2 years ago

var findNumberOfLIS = function(nums) {
    let n = nums.length, maxLen = 0, ans = 0;
    //dp[i] 表示以nums[i]结尾的最长上升子序列的长度，cnt[i] 表示以 nums[i] 结尾的最长上升子序列的个数
    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;
};

guangsizhongbin commented 2 years ago

class Solution { public int findNumberOfLIS(int[] nums) { if (nums.length <= 1) return nums.length; int[] dp = new int[nums.length]; for(int i = 0; i < dp.length; i++) dp[i] = 1; int[] count = new int[nums.length]; for(int i = 0; i < count.length; i++) count[i] = 1;

    int maxCount = 0;
    for (int i = 1; i < nums.length; 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.length; i++) {
        if (maxCount == dp[i]) result += count[i];
    }
    return result;
}

}

yinhaoti commented 2 years ago

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)

stackvoid commented 2 years ago

思路

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]) {
                        cnt[i] += cnt[j];
                    }
                }
            }
            if (dp[i] > maxLen) {
                maxLen = dp[i];
                ans = cnt[i]; // 重置计数
            } else if (dp[i] == maxLen) {
                ans += cnt[i];
            }
        }
        return ans;
    }
}

算法复杂度

Time O(N^2) Space O(N)

CodingProgrammer commented 2 years ago

思路

DP

代码

class Solution {
    public int findNumberOfLIS(int[] nums) {
        if (nums.length <= 1) return nums.length;
        int[] dp = new int[nums.length];
        for(int i = 0; i < dp.length; i++) dp[i] = 1;
        int[] count = new int[nums.length];
        for(int i = 0; i < count.length; i++) count[i] = 1;

        int maxCount = 0;
        for (int i = 1; i < nums.length; 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.length; i++) {
            if (maxCount == dp[i]) result += count[i];
        }
        return result;
    }
}

复杂度

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

last-Battle commented 2 years ago

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

taojin1992 commented 2 years ago

// 学习题解逻辑写的
/*
Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of longest continuous increasing subsequence is 1, and there are 5 subsequences' length is 1, so output 5.

dp[i][0] 表示 以 nums[i] 结尾的最长上升子序列的长度，dp[i][1] 表示 以 nums[i] 结尾的长度为 dp[i][0] 的子序列的个数。

LIS 的一般过程是这样的：

for i in range(n):
    for j in range(i + 1, n):
        if nums[j] > nums[i]:

这道题也是类似，遍历到 nums[j] 的时候往前遍历所有的 满足 i < j 的 i。

- 如果 nums[j] <= nums[i]， nums[j] 无法和这个i拼接成递增子序列

- 否则说明我们可以拼接。但是拼接与否取决于拼接之后会不会更长。如果更长了就拼，否则不拼。

上面是 LIS 的常规思路，下面我们加一点逻辑。

- 如果拼接后的序列更长，那么 dp[j][1] = dp[i][1] （这点容易忽略）

- 如果拼接之后序列一样长， 那么 dp[j][1] += dp[i][1]。

- 如果拼接之后变短了，则不应该拼接

[1,3,5,4,7]

 1.1.1.1.1
 1.1.1.1.1

 j->3
 1.2.1.1.1
 1.1.1.1.1

 j->5
 1.2.3.1.1
 1.1.1.1.1

 j->4
 1.2.3.3.1
 1.1.1.1.1

 j->7, i=4
 1.2.3.3.4
 1.1.1.1.1

 j->7, i=5
 1.2.3.3.4
 1.1.1.1.2

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

Hacker90 commented 2 years ago

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)

machuangmr commented 2 years ago

代码

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

Yachen-Guo commented 2 years ago

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

fornobugworld commented 2 years ago

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

leetcode-pp / 91alg-6-daily-check

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

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

入选理由

题目地址

前置知识

题目描述

思路

代码

思路

代码

复杂度

lis[i] is the length of LIS having last element as nums[i]

思路

代码

思路

关键点

代码

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

思路

golang代码

复杂度

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

思路一

代码

复杂度分析

Time: o(n^2)

Idea

Code

Complexity:

思路

思路

代码

思路

代码

思路

代码

代码

复杂度

最长子序列有多长，各个最长子序列有几个

O(N)^2

on2 on

思路

代码

复杂度

思路

代码

时间复杂度

思路

代码

复杂度

思路

代码

算法复杂度

思路

代码

复杂度

dp[i][0] -> LIS

代码