Number of Longest Increasing Subsequence

시간이 좀 남아서 DP 문제를 풀고 있는데 생각을 많이 하는 연습을 할 수 있어서 좋은거같다. 앞서 LIS 문제를 풀게 되면서 가장 긴 구간을 찾는 문제에 대한 이해는 잘 할 수 있었다.

결국 이런 구간 문제는 내가 현재 위치한 곳에서 전 구간에 캐싱된 숫자를 기준으로 업데이트를 해줘야한다. 그런데 이 문제는 전 구간에서 찾은 LIS 외에도 해당 LIS 가 얼마나 발생했냐도 알아야한다. 처음에는 map 으로 접근하는 방법을 선택했는데 아이디어를 조금만 바꾸면 되는것이었다.

영상에서 이 문제를 분석했는데 제일 괜찮은 해석이었다. LIS 는 그대로 업데이트를 해주지만 만약에 LIS 가 같다면? 그때는 count 값을 캐싱된 값으로 업데이트 해주면서 유지하면은 된다. 나중에 다시 풀어도 좋을 문제다.

class Solution {
public:
    int findNumberOfLIS(vector<int>& nums) {
        int n = nums.size(); 
        if(n <= 1) return n; 
        vector<int> lis(n,1); 
        vector<int> count(n,1); 

        for(int i = 0; i < n; i++){
            for(int j = 0; j < i; j++){
                if(nums[j] < nums[i]){
                    if(lis[j] >= lis[i]){
                        lis[i] = lis[j] + 1; 
                        count[i] = count[j]; 
                    } else if(lis[i] == lis[j] + 1){
                        count[i] += count[j]; 
                    }

                }
                
            }
        }
        int longest = *max_element(lis.begin(),lis.end()); 
        int answer = 0; 
        for(int i = 0; i < n; i++){
            if(lis[i] == longest) answer += count[i]; 
        }
        return answer; 
        
    }
};