Leetcode - 673. Number of Longest Increasing Subsequence

문제

주어진 배열에서 가장 긴 subsequence 즉 LIS의 갯수를 구하라.

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].

아이디어

• 우선 LIS 길이를 구한 뒤, 배열을 backtracking을 통해 순회하면서 LIS길이를 만나면 총 갯수를 카운트 한다. 답은 맞지만 TLE가 발생한다.

• DP로 풀이하는 방법: memoization에 추가로 count배열을 생성한다.
  아래 주석을 참고. 기존의 LIS풀이법 처럼 mem[]배열을 생성하면서 동시에 cnt[]배열도 생성한다.

  • mem[i]는 nums[i]로 끝나는 LIS의 최대 길이를 의미한다.
  • cnt[i]값은 nums[i]로 끝나는 가장 긴 subsequence의 총 갯수를 의미한다. 아래와같이 더해서 구할 수 있다.
    cnt[i] = sum(cnt[j]) for j<i && (nums[j] < nums[i]) && (mem[j] + 1 == mem[i])
    -> i보다 작은 j들 중에서, mem[i]보다 1작은 mem[j]에 해당하는 cnt[j]를 모두 더하면 된다.
  • 코드가 이해하기가 쉽지 않았음. discussion참고함.

풀이

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        // mem[i]는 nums[i]로 끝나는 LIS의 최대 길이를 의미
        vector<int> mem(nums.size(), 1);
        
        // cnt[i] 는 nums[i] 로 끝나는 LIS의 총 갯수를 의미
        // 아래와 같이 계산될 수 있음.
        // cnt[i] = sum(cnt[j]) for j<i && (nums[j] < nums[i]) && (mem[j] + 1 == mem[i])
        vector<int> cnt(nums.size(), 1);
        int maxlen = 1;
        int maxcnt = 0;
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    if (mem[j] + 1 > mem[i]) {
                        mem[i] = mem[j] + 1;
                        // 최종적으로 mem[i] 보다 1작은 경우의 cnt[i]를 모두 더할것인데
                        // cnt[i]의 첫 초기값을 더해놓는다.
                        cnt[i] = cnt[j]; 
                        
                    } else if (mem[j] + 1 == mem[i]) {
                        // 동일한 경우의 두번째 부터는 누적해서 더함.
                        cnt[i] += cnt[j];
                    }
                }
            }
            maxlen = std::max(mem[i], maxlen);
        }
        for (int i = 0; i < nums.size(); i++) {
            if (mem[i] == maxlen)
                maxcnt += cnt[i];
        }
        return maxcnt;
    }
};

backtracking 방법 (TLE)

class Solution {
public:
    int maxcnt = 0;
    int maxlen = 1;
    
    void back_tracking(vector<int>& nums, int cur, int len) {
        if (len == maxlen) {
            maxcnt++;
            return;
        }
        for (int i = cur + 1; i < nums.size(); i++) {
            if (nums[cur] < nums[i]) {
                back_tracking(nums, i, len + 1);
            }
        }
    }
    
    int findNumberOfLIS(vector<int>& nums) {
        vector<int> mem(nums.size(), 1);
        
        for (int i = 0; i < nums.size(); i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    mem[i] = std::max(mem[i], mem[j]+1);
                }
            }
            maxlen = std::max(maxlen, mem[i]);
        }
        //cout << maxlen;
        // backtracking reached maxlen
        for (int i = 0; i < nums.size(); i++) {
            back_tracking(nums, i, 1);
        }
        return maxcnt;
    }
};