리트코드

다이나믹 프로그래밍

• 509. Fibonacci Number

class Solution:
    def fib(self, n: int) -> int:
        if n == 0:
            return 0
        
        elif n == 1:
            return 1
        
        return self.fib(n - 1) + self.fib(n - 2)

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

• 53. Maximum Subarray

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

• 만약 앞 전까지 더한 것들이 음수가 되었다면, 본인이 더해질 때 차라리 0에서 다시 출발하여 본인이 더해지는 것이 낫다.
  • 합이, 즉 dp의 요소들이 음수가 되는 것이 아니라, nums[i]가 음수라도 별 다른 것을 하지 않는 이유는, 뒤에 어떤 큰 숫자가 올지 모르기 때문이다.
• 위와 같이 한다면, 연속적으로 숫자를 더해나가다가 합이 음수가 되면 차라리 0부터 시작하는 것이 낫다는 방식이다.
  • 그리고 dp의 요소들에게는 0이 되기 전, 즉 연속적으로 숫자를 더한 값들이 들어있을 것이다. 여기서 max값을 뽑아내면 된다.

• 70. Climbing Stairs

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
        
        dp = [0] * (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]

• 만약 4개의 계단을 올라야한다고 가정하면,
  • 3번째 계단까지 올라왔던 수에서 계단을 한 번에 1칸 더 오르면 되니 3번째 계단까지 오른 경우의 수 하나와,
  • 2번째 계단까지 올라왔던 수에서 계단을 한 번에 2칸 더 오르면 되니 2번째 계단까지 오른 경우의 수 하나를 더하면 된다.
  • 즉 dp[4] = dp[4 - 1] + dp[4 - 2]이다.