###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 673. Number of Longest Increasing Subsequence

## [題目連結:] https://leetcode.com/problems/number-of-longest-increasing-subsequence/

## 題目:
Given an integer array ```nums```, return the number of longest increasing subsequences.

**Notice** that the sequence has to be **strictly** increasing.

**Example 1:**

Input: nums = [1,3,5,4,7]
Output: 2
Explanation: The two longest increasing subsequences are [1, 3, 4, 7] and [1, 3, 5, 7].

**Example 2:**

Input: nums = [2,2,2,2,2]
Output: 5
Explanation: The length of the longest increasing subsequence is 1, and there are 5 increasing subsequences of length 1, so output 5.

## 解題想法:
* 此題為給一數組，求最長嚴格遞增的子數組個數

* 使用DP:
* 定義兩組:
* **dp[i]:以nums[i]為結尾的最長LIS長度**
* 初始皆為1，因為自己一個數字長度為1
* **count[i]:以nums[i]為結尾的最長LIS個數**
* 初始個數皆為1
* 對於迴圈的進行:
* 雙迴圈
* 外圈第一圈: 控制邊界
* for **i** in range(1,n)
* 內圈第二圈: 控制範圍
* for **j** in range(**i**)
* j在前、i在後~
* 轉移方程式:
* 最低門檻: 前面的j需要小於後面的i才可構成嚴格遞增
* if nums[j]<nums[i]:
* go 後續Case判斷
* Case1: if dp[j]>=dp[i]
* **意義**: 若較小的nums[j]為結尾構成的長度>=較大的nums[i]為結尾構成的長度
* 則**dp[i]=dp[j]+1** (繼承dp[j]的長度並加上1(即加上nums[i]))
* 則**count[i]=count[j]** (**數量**直接繼承)
* Case2: else if dp[j]+1==dp[i]
* **意義**: 若較小的nums[j]為結尾構成的長度(dp[j])比較短，加上nums[i]後，長度==較大的nums[i]為結尾構成的長度(dp[i])
* 則dp數組不用更動
* 則**count[i]+=count[j]**
* 數組擴張
* **意義:** 因為count[j]紀錄的是滿足dp[j]長度的個數，藉由加上nums[i]後可以使dp[j]長度+1等於dp[i]，所以表示count[j]個數全部都可以累加給count[i]，因為長度一樣
* 紀錄最後數量:
* 累加最大dp[i]對應的count[i]值即為解

## Python:

class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #dp[i]:以nums[i]為結尾的最長LIS
        #count[i]:以nums[i]為結尾的最長LIS個數
        dp=[1 for _ in range(len(nums))]
        count=[1 for _ in range(len(nums))]
        for i in range(1,len(nums)):
            for j in range(i):
                #前面j小於後面i才要考慮
                if nums[j]<nums[i]:
                    if dp[j]>=dp[i]:
                        dp[i]=dp[j]+1
                        count[i]=count[j]
                    #原本dp[j]較短 加上 nums[i]後 長度==dp[i]，則:
                    #count[i]+=count[j] if  dp[j]+1 == dp[i] 
                    elif dp[j]+1==dp[i]:
                        count[i]+=count[j] #組數擴張!!
        res=0
        MaxLen=max(dp)
        for pos,val in enumerate(count):
            if dp[pos]==MaxLen:
                res+=val
        return res

nums = [1,3,5,4,7]
result=Solution()
ans=result.findNumberOfLIS(nums)
print(ans)

## C++:
* 取數組最大值用max_element，為pointer
* [https://shengyu7697.github.io/std-max_element/]

#include<bits/stdc++.h>
using namespace std;

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(n, 1), count(n, 1);
        for (int i=1; i<n; i++){
            for (int j=0; j<i; j++){
                if (nums[j]<nums[i]){
                    if (dp[j]>=dp[i]){
                        dp[i]=dp[j]+1; //length+1
                        count[i]=count[j];
                    }
                    else if (dp[j]+1==dp[i])
                        count[i]+=count[j];
                }
            }
        }
        //max_element: get the max value
        //use pointer get reference
        int maxLen= *max_element(dp.begin(), dp.end());
        int res=0;
        for (int pos=0; pos<n; pos++){
            if (dp[pos]==maxLen)
                res+=count[pos];
        }
        return res;
    }
};