[Mdp] lc673. 最長遞增子序列的個數(LIS+算法優化+算法拓展)

文章目錄

• • 1. 題目來源
  • 2. 題目解析

1. 題目來源

連結：673. 最長遞增子序列的個數

前置知識：

• [Mdp] lc300. 最長遞增子序列(LIS+LIS貪心優化+LIS詳解+模闆題)
• 本題拓展版，相同的最長上升子序列計數僅算一次。《算法競賽進階指南》, usaco training 4.3-----314. 低買

2. 題目解析

LIS 的簡單拓展，中間記錄方案數即可。

簡單回顧：

• 狀态定義：

  f[i]

  ：以

  i

  結尾的最長上升子序列個數。
• 狀态轉移：枚舉

  j

  ，範圍

  0~i-1

  ，當

  a[j] < a[i]

  即

  f[i]=max(f[i], f[j]+1)

  。
• 有貪心做法。

對标本題：

• 多開一個數組記錄以

  i

  結尾的最長上升子序列的個數即可。
• 狀态定義：

  g[i]

  ：以

  i

  結尾的最長上升子序列的個數。在此，即便最長上升子序列相同也是可以的。
• 狀态轉移：當

  a[i] > a[j]

  時，說明最長上升子序列可能被更新，分兩種情況對待。
  • 當

    f[i] < f[j] + 1

    時，說明以

    i

    結尾的最長上升子序列被更新。則最長上升子序列的個數也要被更新，即

    g[i]=g[j]

    ，即以

    i

    結尾的

    LIS

    數量等于以

    j

    結尾的

    LIS

    數量。
  • 當

    f[i]=f[j]+1

    時，說明以

    i

    結尾的最長上升子序列長度未被更新，但兩種情況都是符合最大值。則

    g[i]+=g[j]

    ，保留原來的以

    i

    結尾的

    LIS

    所有方案，再加上以

    j

    結尾的

    LIS

    所有方案。在此，重複情況也要進行統計。

例如：1,2,2,4 這個。那麼兩個 1，2，4 都是最長上升子序列。都需要計算并計數。在 《算法競賽進階指南》, usaco training 4.3-----314. 低買 中隻讓計算不重複的，是以還得考慮去重就更麻煩了。

本題可以用

LIS

貪心搞成 O ( n l o g n ) O(nlogn) O(nlogn)，也可樹狀數組。具體看官方題解評論區即可。

• 時間複雜度： O ( n 2 ) O(n^2) O(n2)
• 空間複雜度： O ( n ) O(n) O(n)

dp

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

        int mx = 0, cnt = 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 (mx < f[i]) mx = f[i], cnt = g[i];
            else if (mx == f[i]) cnt += g[i];
        }

        return cnt;
    }
};
           

go

func findNumberOfLIS(nums []int) int {
    n := len(nums)
    f := make([]int, n)
    g := make([]int, n)

    mx, cnt := 0, 0
    for i := 0; i < n; i ++ {
        f[i], g[i] = 1, 1
        for 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 mx == f[i] {
            cnt += g[i]
        } else if mx < f[i] {
            mx = f[i]
            cnt = g[i]
        }
    }

    return cnt
}