Dynamic Programming - Top Interview Questions[Medium] (6/9) : Python

leetcode.com/problems/jump-game/solution/

내 답이 솔루션이랑 좀 다르네.. 솔루션 시간내서 읽어보자

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        i = 0
        next_dest = 1 + i + nums[i]
        while i < next_dest and i < n:
            next_dest = max(next_dest, 1 + i + nums[i])
            i += 1
        
        return True if next_dest >= n else False
            

 

 

leetcode.com/problems/unique-paths/solution/

솔루션에는 2d dp가 있네. 나는 1d dp로 함. 그리고 솔루션에는 math도 있는데 아직 안봄.

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [0 for i in range(n)]
        dp[0] = 1
        for i in range(m):
            for j in range(1, n):
                dp[j] += dp[j-1]
                    
        return dp[n-1]

2차원 배열 1로 초기화하는 방법

d = [[1] * n for _ in range(m)]

 

 

 

 

leetcode.com/problems/coin-change/solution/

단순 그리디가 아님

3번 바텀업으로 답보고 구현함

머리 맑을때 다시 보기

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x-coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1

 

 

 

 

 

 

 

leetcode.com/problems/longest-increasing-subsequence/solution/