leetcode 300(lis, dp), 334(구현), 646(lis, dp)

300 https://leetcode.com/problems/longest-increasing-subsequence/

lis문제이다. 예전에 백준에서 많이 풀었었다. 오랫만이니 리마인드해보자. https://qkqhxla1.tistory.com/763

from bisect import bisect_left

class Solution(object):
    def lengthOfLIS(self, nums):
        if not nums:
            return 0
        
        dp_len = max(nums)+1 if max(nums) > 0 else len(nums)+1
        def lis(line):
            dp = [0 for i in xrange(dp_len)]
            size = 0
            for i in xrange(len(line)):
                h = bisect_left(dp[:size],line[i])
                if h==size: 
                    size += 1
                dp[h] = line[i]
            return size

        return lis(nums)

334 https://leetcode.com/problems/increasing-triplet-subsequence/

가장 작은수를 first, 그다음수를 second라고 한다. 숫자를 순회하면서 

가장 작은수보다 더 작은수가 나올경우 가장 작은수를 바꿔주고 다음 수로 넘어간다. 

가장 작은수보다는 큰데 그 다음수보다는 작을 경우 그 다음수를 바꿔주고 넘어간다.

가장 작은수, 그다음수보다 크면 앞의 가장 작은수, 그 다음수는 앞 로직에서 숫자의 증가함이 증명되었기 때문에 바로 True를 리턴한다.

class Solution(object):
    def increasingTriplet(self, nums):
        first, second = 99999999999, 99999999999
        for n in nums:
            if n <= first:
                first = n
            elif n <= second:
                second = n
            else:
                return True
        return False

646 https://leetcode.com/problems/maximum-length-of-pair-chain/

O(n^2) lis에서 조금 변형해서 풀었다. 근데 답보니까 그리디가 훨씬 빠름

class Solution(object):
    def findLongestChain(self, pairs):
        if not pairs:
            return 0
        
        len_pairs = len(pairs)
        pairs = sorted(pairs, key=lambda x:[x[1], x[0]])
        
        dp = [-1 for i in xrange(1001)]
        def lis(s):
            if dp[s+1]!=-1:
                return dp[s+1]

            dp[s+1] = 0
            for i in xrange(s+1, len_pairs):
                if s == -1 or pairs[s][1] < pairs[i][0]:
                    dp[s+1] = max(dp[s+1], lis(i)+1)
            return dp[s+1]

        return lis(-1)