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

다른풀이도 많이 있지만, dp만 찍고 넘어감

dp배열의 인덱스에 주의하자.

- 배열크기 n+1

- 시작부분 셋팅

- 루프 인덱스

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [0 for i in range(n+1)]
        dp[1] = 1
        dp[2] = 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

leetcode.com/problems/best-time-to-buy-and-sell-stock/

문제가 쉬운것 같지만, 아직도 설계를 버벅인다.

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for price in prices:
            if price < min_price:
                min_price = price
            elif price - min_price > max_profit:
                max_profit = price - min_price
        return max_profit

leetcode.com/problems/maximum-subarray/

이건 좀 다시 살펴봐야 할 필요가 있음.

1. 분할정복

2. 그리디

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        curr_sum = max_sum = nums[0]
        
        for i in range(1, n):
            curr_sum = max(nums[i], curr_sum + nums[i])
            max_sum = max(max_sum, curr_sum)
        
        return max_sum

3. DP 카데인's

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        max_sum = nums[0]
        
        for i in range(1, n):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
            max_sum = max(nums[i], max_sum)
            
        return max_sum

leetcode.com/problems/house-robber/

위에꺼랑 이거랑 꼭 머릿속에 집어 넣어버리자.

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev_max = 0
        curr_max = 0
        for x in nums:
            curr_max, prev_max = max(curr_max, prev_max + x), curr_max
        return curr_max

리트코드 코딩 인터뷰 문제 목록(EASY) - Java

Array - Top Interview Questions[EASY] (1/9) : Java

String - Top Interview Questions[EASY] (2/9) : Java

Linked List - Top Interview Questions[EASY] (3/9) : Java

Trees - Top Interview Questions[EASY] (4/9) : Java

Sorting and Searching - Top Interview Questions[EASY] (5/9) : Java

Dynamic Programming - Top Interview Questions[EASY] (6/9) : Java

Design - Top Interview Questions[EASY] (7/9) - Java

Math - Top Interview Questions[EASY] (8/9) - Java

Others - Top Interview Questions(EASY) - (9/9) : Java

리트코드 코딩 인터뷰 문제 목록(EASY) - Python

Array - Top Interview Questions[EASY] (1/9) : Python