673. Number of Longest Increasing Subsequence ★★★

673. Number of Longest Increasing Subsequence

 

https://youtu.be/Tuc-rjJbsXU?si=n0lvzu2hxl6XtygW

 

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # DP를 사용하는데, 
        # lenLIS: LIS 길이도 저장해야되고,
        # Count: LIS 개수도 저장해야 함
        """
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |       |       |       |       |       |    
        Count   |       |       |       |       |       |    

        lenLIS 자기자신 포함하므로, 초기값 1로 세팅
        Count 는 초기값 1으로 세팅
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |   1   |   1   |   1   |   1   |   1   |    
        Count   |   1   |   1   |   1   |   1   |   1   |    

        i=4일때. 첫 숫자이므로 lenLIS[4]= 1, Count[4]=1
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |       |       |       |       |   1   |    
        Count   |       |       |       |       |   1   |

        i는 뒤에서부터 4부터 0으로.. 감소하면서.

        i=3
        if nums[3] < nums[4] 이면 
            LensLIS[3] = 1+ LensLIS[4]
            Count[3] = Count[4]
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |       |       |       |   2   |   1   |    
        Count   |       |       |       |   1   |   1   |

        i=2
        if nums[2] < nums[3] 이 아니지만 
        if nums[2] < nums[4] 이 만족하므로, 
            LensLIS[2] = 1+ LensLIS[4]
            Count[2] = Count[4]
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |       |       |   2   |   2   |   1   |    
        Count   |       |       |   1   |   1   |   1   |

        i=1
        if nums[1] < nums[2] 이 만족하므로
            LensLIS[1] = 1+ LensLIS[2] <- LensLIS[2:] 에서 최대값
            Count[1] += Count[2]
        if nums[1] < nums[3] 이 만족하므로
            LensLIS[1] = 1+ LensLIS[3] <- LensLIS[2:] 에서 최대값
            Count[1] += Count[3]
        if nums[1] < nums[4] 이 만족하지만
            LensLIS[4] <- LensLIS[2:] 에서 최대값이 아니라서 
            pass
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |       |   3   |   2   |   2   |   1   |    
        Count   |       |   2   |   1   |   1   |   1   |

        i=0
        if nums[0] < nums[1] 이 만족하므로
            LensLIS[0] = 1+ LensLIS[1] <- LensLIS[1:] 에서 최대값
            Count[0] = Count[1]
        나머지는 nums[0] < nums[j] 만족하지만 
            LensLIS[j] <- LensLIS[1:] 에서 최대값이 아니라서            
            pass
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |   4   |   3   |   2   |   2   |   1   |    
        Count   |   2   |   2   |   1   |   1   |   1   |
        """
        dp = {} # DP cache, hash map, key = index, value = [lengh of LIS, count]
        lenLIS, res = 0, 0 # lengh of LIS, count of LIS

        # i = start of subseq
        for i in range(len(nums)-1, -1, -1):
            maxLen, maxCnt = 1, 1 # len, cnt of LIS start from i

            for j in range(i+1, len(nums)):
                if nums[i] < nums[j]: # make sure increasing order
                    lengh, count = dp[j] # len, cnt of LIS start from j

                    if lengh + 1 > maxLen:
                        maxLen, maxCnt = lengh+1, count
                    elif lengh + 1 == maxLen: # find another subseq
                        maxCnt += count
            
            if maxLen > lenLIS:
                lenLIS, res = maxLen, maxCnt
            elif maxLen == lenLIS: # find another subseq
                res += maxCnt

            dp[i] = [maxLen, maxCnt]

        return res

 

정리한 코드

class Solution:
    def findNumberOfLIS(self, nums: List[int]) -> int:
        # DP를 사용하는데, 
        # lenLIS: LIS 길이도 저장해야 되고,
        # Count: LIS 개수도 저장해야 함
        """
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |       |       |       |       |       |    
        Count   |       |       |       |       |       |    

        lenLIS 자기자신 포함하므로, 초기값 1로 세팅
        Count 는 초기값 1로 세팅
        i       |   0   |   1   |   2   |   3   |   4   |    
        nums    |   1   |   3   |   5   |   4   |   7   |    
        lenLIS  |   1   |   1   |   1   |   1   |   1   |    
        Count   |   1   |   1   |   1   |   1   |   1   |    
        """

        dp = {}  # DP cache, hash map, key = index, value = [length of LIS, count]
        lenLIS, res = 0, 0  # 전체 LIS 길이와 해당 개수를 저장

        # i = start of subsequence
        for i in range(len(nums) - 1, -1, -1):  # 배열을 뒤에서부터 순회
            maxLen, maxCnt = 1, 1  # 현재 위치에서 시작하는 LIS 길이와 개수 초기화

            for j in range(i + 1, len(nums)):  # i 이후의 요소를 탐색
                if nums[i] < nums[j]:  # 증가하는 순서일 경우
                    lengh, count = dp[j]  # dp[j]에서 길이와 개수를 가져옴

                    if lengh + 1 > maxLen:  # 더 긴 LIS 발견 시
                        maxLen, maxCnt = lengh + 1, count  # 길이와 개수 업데이트
                    elif lengh + 1 == maxLen:  # 같은 길이의 LIS 발견 시
                        maxCnt += count  # LIS 개수 누적
            
            """
            i = 4
            nums[4] = 7
            lenLIS[4] = 1, Count[4] = 1
            
            i = 3
            nums[3] = 4
            lenLIS[3] = max(1, 1 + lenLIS[4]) = 2
            Count[3] = Count[4] = 1
            
            i = 2
            nums[2] = 5
            lenLIS[2] = max(1, 1 + lenLIS[4]) = 2
            Count[2] = Count[4] = 1
            
            i = 1
            nums[1] = 3
            lenLIS[1] = max(1, 1 + lenLIS[2]) = 3
            Count[1] = Count[2] + Count[3] = 2
            
            i = 0
            nums[0] = 1
            lenLIS[0] = max(1, 1 + lenLIS[1]) = 4
            Count[0] = Count[1] = 2
            """
            
            if maxLen > lenLIS:  # 새로운 최대 LIS 길이를 발견하면
                lenLIS, res = maxLen, maxCnt  # 전체 길이와 개수 업데이트
            elif maxLen == lenLIS:  # 같은 길이의 LIS 발견 시
                res += maxCnt  # 전체 LIS 개수 추가

            dp[i] = [maxLen, maxCnt]  # 현재 위치의 LIS 길이와 개수를 저장

            # 상태를 디버깅으로 출력
            print(f"i = {i}, nums[i] = {nums[i]}, maxLen = {maxLen}, maxCnt = {maxCnt}, dp = {dp}")

        return res  # 전체 LIS 개수 반환