Self 모의고사 문제

1. Min Cost Climbing Stairs

https://leetcode.com/problems/min-cost-climbing-stairs/description/

Dynamic Programming 방식으로 풀면 된다. $O(n)$에 쉽게 풀린다.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        INF = 1e+9
        def _cost(i):
            if i == n - 1:
                return cost[-1]
            elif i >= n:
                return 0
            if m[i] < INF:
                return m[i]
            m[i] = cost[i] + min(_cost(i + 1), _cost(i + 2))
            return m[i]

        m = [INF] * n 
        ans = min(_cost(0), _cost(1))
        return ans

여기서 m[i] 를 구하기 위해 m[i - 1], m[i - 2] 두 개만 있으면 되므로 space complexity도 $O(1)$에 풀 수 있다.

class Solution:
    def minCostClimbingStairs(self, cost: List[int]) -> int:
        n = len(cost)
        INF = 1e+9
        m = [INF] * n
        for i in range(n):
            m[i] = cost[i] + (0 if i < 2 else min(m[i - 1], m[i - 2]))
        ans = min(m[-2:])
        return ans

2. Jump Game VI

https://leetcode.com/problems/jump-game-vi/

Well explained solution: link, YouTube

• Dynamic Programming Solution

  class Solution:
      def maxResult_topdown(self, nums: List[int], k: int) -> int:
          # Dynamic Programing: O(n^2) -> TLE (57 / 72 testcases passed)
          n = len(nums)
          m = {}
          def backtrack(i):
              if i == 0: 
                  return nums[i]
              if i in m:
                  return m[i]
              m[i] = -1e+8
              for j in range(i - 1, max(i - k - 1, -1), -1):
                  m[i] = max(m[i], backtrack(j) + nums[i])
              return m[i]
          ans = backtrack(n - 1)
          return ans
  
      def maxResult_buttomup(self, nums: List[int], k: int) -> int:
          # Dynamic Programing: O(n^2)
          n = len(nums)
          m = [-1e+8] * n
          m[0] = nums[0]
          for i in range(1, n):
              for j in range(i - 1, max(i - k - 1, -1), -1):
                  m[i] = max(m[i], m[j] + nums[i])
          return m[n - 1]

multiset(또는 heap) 을 사용하면 O(nlogk) (space는 O(k)), deque를 사용하면 O(n)이 됨 (deque안 원소를 최대 k개를 갖도록 하고, 안에서 descending order를 유지)

• Optimized Dynamic Programming: Heap Solution

  이 솔루션 부터 통과함

  import heapq
  
  class Solution:
      def maxResult(self, nums: List[int], k: int) -> int:
          # Dynamic Programing with Max-Heap, O(nlogk) -> Pass
          n = len(nums)
          _nums = [-e for e in nums]
          heap = [(-nums[0], 0)]
          ans = -heap[0][0]
          for i in range(1, n):
              while heap and (heap[0][1] < i - k): # can't reach current index from index stored in q
                  heapq.heappop(heap)
              ans = nums[i] + (-heap[0][0])  # update max score for current index
              heapq.heappush(heap, (-ans, i))
          return ans

Max Heap은 다음과 같이 사용 가능하다.

arr = [-e for e in arr] 
heapq.heapify(arr)  # build_heap
heapq.heappush(arr, -value)  # push
heapq.heappop(heap)  # pop minimum value
arr[0]  # get max value
heapq.nsmallest(arr)  # get n largest values

• Further Optimized Dynamic Programming: Deque Solution

  from collections import deque
  
  class Solution:
      def maxResult(self, nums: List[int], k: int) -> int:
          # Dynamic Programing with Deque, asymptotically O(n) ignoring contant time
          n = len(nums)
          Q = deque([0]) # Q is incrementally sorted in descending order
          m = [-1e+8] * n
          m[0] = nums[0]
          for i in range(1, n):
              if Q and (Q[0] < i - k): # can't reach current index from index stored in q
                  Q.popleft()
              m[i] = nums[i] + m[Q[0]]  # update max score for current index
              while Q and (m[Q[-1]] <= m[i]):  # keep descending order in deque
                  Q.pop()
              Q.append(i)
          return m[n - 1]