673. Number of Longest Increasing Subsequence

題目網址：https://leetcode.cn/problems/number-of-longest-increasing-subsequence/

題意：給一 array nums, 返回最長嚴格遞增 subsequence 的個數。

Solution：

想法：可看到下圖 5 的部分重複計算, 故利用 DP, dp[i] 代表 nums[i] 開頭的最大 LIS 長度

• 特殊情況: 最長的 LIS 不只一個, 則 cnt 要相加

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        const int n = nums.size();
        vector<int> dp(n, 1) , cnt(n, 1);
        int maxLis = 0, res = 0;

        for (int i = n - 1; i >= 0; --i) {
            for (int j = i + 1; j < n; ++j) {
                if (nums[j] > nums[i]) {
                    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] > maxLis) {
                maxLis = dp[i];
                res = cnt[i];
            } else if (dp[i] == maxLis) {
                res += cnt[i];
            }
        }

        return res;
    }
};

• time：$O(n^2)$ ➔ for loop
• space：$O(n)$ ➔ dp 和 cnt