[DSA] 1. 1-D Dynamic Programming

 

TABLE OF CONTENTS

 

• Solution
  
  • Brute Force = Decision Tree
  • Memoization(=Caching) = Backtracking(=dfs)(Base Case → Cache Hit → 내려가기 → 올라왔을때)
  • DP = Bottom-UP Approach(=Memoization logic을 거꾸로 적용해서 표/그림/공식 제작)

1. Climbing Stairs

한번에 계단을 1개 혹은 2개씩만 올라갈 수 있을때 n개의 계단을 오를 수 있는 방법의 수를 구하라

# O(n), O(n)
class Solution(object):
    def climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2

        dp = [0] * (n + 1)
        dp[n - 1] = 1
        dp[n - 2] = 2

        for i in range(n - 3, -1, -1):
            dp[i] = dp[i + 1] + dp[i + 2]

        return dp[0]

# O(n), O(1)로 최적화
class Solution(object):
    def climbStairs(self, n):
        if n == 1:
            return 1
        if n == 2:
            return 2

        one_step_before = 2
        two_steps_before = 1

        for i in range(n - 3, -1, -1):
            current = one_step_before + two_steps_before
            two_steps_before = one_step_before
            one_step_before = current

        return one_step_before

 

2. House Robber

adjacent(바로 근접)에는 갈 수 없을 때 최대로 뽑아낼 수 있는 Output을 구하라

# O(n), O(n)
class Solution(object):
    def rob(self, nums):
        n = len(nums)
        dp = [0] * n

        for i in range(n-1, -1, -1):
            if (i == n-1) :
                dp[i] = max(0, 0 + nums[i])
            elif (i == n-2) :
                dp[i] = max(dp[i + 1], 0 + nums[i])
            elif i < n-2 : 
                dp[i] = max(dp[i + 1], nums[i] + dp[i + 2])

        return dp[0]

# O(n), O(1)로 최적화
class Solution(object):
    def rob(self, nums):
        n = len(nums)
        prev1, prev2 = 0, 0

        for i in range(n - 1, -1, -1):
            if (i == n-1) :
                current = max(0, 0 + nums[i])
                prev2 = prev1
                prev1 = current
            elif (i == n-2) :
                current = max(prev1, 0 + nums[i])
                prev2 = prev1
                prev1 = current
            elif i < n-2 : 
                current = max(prev1, prev2 + nums[i])
                prev2 = prev1
                prev1 = current

        return prev1

 

3. House Robber II

adjacent(바로 근접)에는 갈 수 없을 때 최대로 뽑아낼 수 있는 Output을 구하라. 단, 여기선 nums가 circle의 형태로 arrange 되어 있다

# O(n), O(n)
class Solution(object):
    def rob(self, nums):
        def houserobber(nums):
            n = len(nums)
            dp = [0] * n

            for i in range(n-1, -1, -1):
                if (i == n-1) :
                    dp[i] = max(0, 0 + nums[i])
                elif (i == n-2) :
                    dp[i] = max(dp[i + 1], 0 + nums[i])
                elif i < n-2 : 
                    dp[i] = max(dp[i + 1], dp[i + 2] + nums[i])

            return dp[0]

        if len(nums) == 1: # edge case : nums[1:]의 경우 index out of range
            return nums[0]
        return max(houserobber(nums[1:]), houserobber(nums[:-1]))

# O(n), O(1)로 최적화
class Solution(object):
    def rob(self, nums):
        def houserobber(nums):
            n = len(nums)
            prev1, prev2 = 0, 0

            for i in range(n - 1, -1, -1):
                if (i == n-1) :
                    current = max(0, 0 + nums[i])
                    prev2 = prev1
                    prev1 = current
                elif (i == n-2) :
                    current = max(prev1, 0 + nums[i])
                    prev2 = prev1
                    prev1 = current
                elif i < n-2 : 
                    current = max(prev1, prev2 + nums[i])
                    prev2 = prev1
                    prev1 = current

            return prev1

        if len(nums) == 1: # edge case : nums[1:]의 경우 index out of range handling
            return nums[0]
        return max(houserobber(nums[1:]), houserobber(nums[:-1]))

 

4. Longest Palindromic Substring

Palindrome(데칼코마니)이 가능한 가장 긴 substring을 찾아라

class Solution(object):
    def longestPalindrome(self, s):
        res = ""
        resLen = 0

        for i in range(len(s)):
            # odd length palindrome
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l : r + 1]
                    resLen = r - l + 1
                l -= 1
                r += 1

            # even length palindrome
            l, r = i, i + 1
            while l >= 0 and r < len(s) and s[l] == s[r]:
                if (r - l + 1) > resLen:
                    res = s[l : r + 1]
                    resLen = r - l + 1
                l -= 1
                r += 1

        return res

 

5. Palindromic Substrings

Palindromic(데칼코마니)을 만들어낼 수 있는 모든 Substrings의 갯수를 세라

class Solution(object):
    def countSubstrings(self, s):
        res = 0

        for i in range(len(s)) :
            # odd length palindrome 
            l, r = i, i
            while l >= 0 and r < len(s) and s[l] == s[r] :
                res += 1
                l -= 1
                r += 1
            
            # even length palindrome
            l, r = i, i +1
            while l >= 0 and r < len(s) and s[l] == s[r] :
                res += 1
                l -= 1
                r += 1
            
        return res

6. Decode Ways

숫자 문자열 S를 실제 문자로 Decode할 수 있는 총 방법의 수를 구하라

# DP(Bottom-up) : O(n), O(n)
class Solution(object):
    def numDecodings(self, s):
        n = len(s)
        dp = [0] * (n + 1)
        dp[n] = 1  # 결국 index가 끝까지 가게 되었단 것은 s가 통째로 전체 다 매칭이 되었다는 소리이다. 

        for i in range(n - 1, -1, -1):
            if s[i] == "0":
                dp[i] += 0
            elif s[i] in "123456789":
                dp[i] += dp[i + 1]

            if i + 1 < len(s) and ((s[i] == "1" and s[i + 1] in "0123456789") or (s[i] == "2" and s[i + 1] in "0123456")):
                dp[i] += dp[i + 2]

        return dp[0]


# DP(Bottom-up) : O(n), O(1)
class Solution:
    def numDecodings(self, s: str) -> int:
        next_to_next = 1
        next = 1
        for i in range(len(s) - 1, -1, -1):
            if s[i] == '0':
                current = 0
            elif s[i] in "123456789":
                current = next
                
            if i + 1 < len(s) and ((s[i] == "1" and s[i + 1] in "0123456789") or (s[i] == "2" and s[i + 1] in "0123456")):
                current += next_to_next
            next_to_next = next
            next = current

        return next

7. Coin Change

amount를 맞추려면 총 몇 개의 coin을 줘야하는지 그 minimum 값을 구하라. 만약 amount를 맞출 수 있는 방법이 없다면 -1을 return하라

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for a in range(1, amount + 1):
            for c in coins:
                if a - c >= 0:
                    dp[a] = min(dp[a], 1 + dp[a - c])
        return dp[amount] if dp[amount] != float('inf') else -1

8. Maximum Product Subarray

인접한 애들로만 만드는 Subarray 중에서 만들 수 있는 Product 중에서 가장 큰 값을 구하라

class Solution(object):
    def maxProduct(self, nums):
        res = nums[0]
        curMin, curMax = 1, 1

        for n in nums:
            tmp = curMax * n
            curMax = max(tmp, n * curMin, n)
            curMin = min(tmp, n * curMin, n)
            res = max(res, curMax)
        return res

9. Word Break

s에 들어있는 string이 wordDict의 substring으로 쪼개지는지 확인하라

class Solution(object):
    def wordBreak(self, s, wordDict):
        dp = [False] * (len(s) + 1)
        dp[len(s)] = True

        for i in range(len(s) - 1, -1, -1):
            for w in wordDict:
                if (i + len(w)) > len(s) :
                    dp[i] = False
                elif (i + len(w)) <= len(s):
                    if s[i : i + len(w)] == w:
                        dp[i] = dp[i + len(w)]
                    elif s[i : i + len(w)] != w:
                        dp[i] = False
                if dp[i]:
                    break

        return dp[0]

10. Longest Increasing Subsequence

Increasing Subsequence를 만들고자 할때 가장 긴 것의 길이를 구하라

class Solution(object):
    def lengthOfLIS(self, nums):
        LIS = [1] * len(nums)

        for i in range(len(nums) - 1, -1, -1):
            if i == len(nums) - 1 :
                LIS[i] = 1
                continue
            elif i < len(nums) - 1:
                LIS[i] = 1
                for j in range(i + 1, len(nums)):
                    if nums[i] < nums[j]:
                        LIS[i] = max(LIS[i], 1 + LIS[j])
        return max(LIS)

 

(Follow up) Can you come up with an algorithm that runs in O(n log(n)) time complexity?

class Solution(object):
    def lengthOfLIS(self, nums):
        sub = []

        def binarySearch(sub, val):
            lo, hi = 0, len(sub) - 1
            while lo <= hi:
                mid = lo + int((hi - lo)/2)
                if sub[mid] < val:
                    lo = mid + 1
                elif sub[mid] >= val:
                    hi = mid - 1
            return lo

        for val in nums:
            pos = binarySearch(sub, val)
            if pos == len(sub): 
                sub.append(val)
            elif pos != len(sub):
                sub[pos] = val
        return len(sub)

11. Partition Equal Subset Sum

2개의 Subset으로 Partitioning을 했을때 같은 Sum을 가지도록 Partitioning을 할 수 있는지 구하라