아직 시간을 맞추고 풀기엔 감이 많이 죽어있는 상태인것 같다.
꾸준히 풀어보자.
https://leetcode.com/problems/min-cost-climbing-stairs/description/
Dynamic Programming 방식으로 풀면 된다.
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도
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
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
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]
LEAVE A COMMENT