Leetcode 동적 계획 알고리즘 예제 설명

계단 오 르 기 (Leetcode 70)

code 1

code 2

약탈 (LeetCode 198)

code

최대 필드 와 (LeetCode 53)

code

금광 발굴

code

거스름돈 (LeetCode 322)

code

삼각형 (LeetCode 120)

code

LeetCode 1025: Discover Game

code

동적 계획 동적 계획 알고리즘 은 분 치 법 과 유사 하 다. 그 기본 사상 도 해결 해 야 할 문 제 를 몇 개의 키 문제 로 분해 하고 먼저 서브 문 제 를 해결 한 다음 에 이런 서브 문제 의 해결 에서 원래 의 문 제 를 해결 할 수 있다.동적 계획 은 분 해 를 통 해 서브 문 제 를 얻 는 것 이 서로 독립 된 것 이 아니 라 일부 서브 문 제 는 여러 차례 중복 계산 되 었 다.따라서 해 결 된 하위 문제 의 답 을 저장 하고 필요 할 때 이미 구 한 답 을 찾 으 면 대량의 중복 계산 을 피하 고 시간 을 절약 할 수 있다.동적 계획 문 제 를 푸 는 절차: 1. 상태 전이 방정식 을 찾 아 라. 2. 위 에서 아래로 내 려 오 는 재 귀 알고리즘 (Top - down approach) 을 설계 하 라. 3. 아래 에서 위로 내 려 오 는 교체 알고리즘 (Bottom - up approach) 으로 바 꾸 자.
계단 오 르 기 (Leetcode 70)
제목 은 여기 서 재 귀 를 많이 소 개 했 을 뿐 입 니 다.

        if n == 1:
            return 1
        elif n == 2:
            return 2
        else:
            s1 = self.climbStairs(n-1)
            s2 = self.climbStairs(n-2)
            return s1+s2

Time Limit Exceeded
code 1

class Solution:
    def climbStairs(self, n: int) -> int:
        if n<4:return n
        result=[1,2,3]
        for i in range(3,n):
            result.append(result[i-1]+result[i-2])
        return result[n-1]

Runtime: 36 ms, faster than 55.93% of Python3 online submissions for Climbing Stairs.
Memory Usage: 13.1 MB, less than 5.18% of Python3 online submissions for Climbing Stairs.
사고방식 해석: 주로 파악 하 는 관건 은 문 제 를 귀속 가능 한 하위 문제 로 나 누 는 것 이다.현재 계단 수 는 n 급 이 고 가지 고 있 는 주 행 법 은 n - 1 급 계단 의 주 행 법 과 n - 2 급 계단 의 주 행 법의 합 (한 번 에 1 급 또는 2 급 계단 만 갈 수 있 도록 제한) 은 상태 전이 방정식 을 잘 알 고 있다. 재 귀 의 장점 은 프로그램 구조 가 간단 하고 논리 적 이 며 계산 속도 가 느 리 고 공간 복잡 도가 높다 는 것 이다.더 많은 상황 에서 재 귀 를 교체 로 바 꾸 는 것 을 고려 하면 계산 속 도 를 효과적으로 높 일 수 있다.
code 2

class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1 or n == 0:
            return 1
        i = 2
        temp1 = 1
        temp2 = 1
        while i <= n:
            temp1 += temp2
            if i == n:
                return temp1
            i += 1
            temp2 += temp1
            if i == n:
                return temp2
            i += 1

실행 시간 과 차지 하 는 메모리 와 code 1 의 차이 가 많 지 않 습 니 다.
사고방식 해석: i 층 계단 의 주 법 총 수 를 얻 으 려 면 i - 1 층 과 i - 2 층 의 주 법 만 알 고 두 가 지 를 더 하면 i 층 을 얻 을 수 있다.코드 에서 temp 1 과 temp 2 는 각각 i - 1 과 i - 2 층 의 주 법 수 를 나타 내 는데 사실은 교체 하 는 사상 이다 (구체 적 인 교체 과정 에서 그림 을 그 려 서 서 서 너 천 을 걸 으 면 이해 할 수 있다).
약탈 (LeetCode 198)
code

class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int

        """
        if nums==[]:
            return 0
        if len(nums)==1:
            return max(nums)
        dp = [0]*len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[1],nums[0])
        for i in range(2,len(nums)):
            dp[i] = max(dp[i-1],dp[i-2]+nums[i])
            
        return dp[len(nums)-1]

사고방식: dp [i] 는 0 - i 가구 에서 약탈 할 수 있 는 최대 금액 을 나타 낸다.dp [i] = max (dp [i - 1], dp [i - 2] + nums [i]) 가 있 습 니 다.제 (i - 1) 호 가 를 약탈 한 최대 금액 + 제 i 호 를 약탈 하지 않 고 제 (i - 2) 호 와 약탈 한 최대 금액 + 제 i 호 를 약탈 합 니 다. 둘 중 최대 치 입 니 다.
최대 필드 와 (LeetCode 53)
code

class Solution:
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length=len(nums)
        for i in range(1,length):
            #               ，      ，     ，        
            subMaxSum=max(nums[i]+nums[i-1],nums[i])
            nums[i]=subMaxSum#         nums[i]，  nums      
        return max(nums)

금광 을 캐다
제목: 현재 금광 수 n, 인원수 w, 모든 금광 에 대응 하 는 금광 수량 은 g [n] 이 고 필요 한 인원 은 p [n] 이다. 현재 가장 좋 은 인원 배분 방안 을 찾 아 최종 적 으로 얻 은 금광 수량 이 가장 많다.
문제 풀이 방향: 상태 전이 방정식 dp [n, w] = max (dp [n - 1, w], dp [n - 1, w - p [n - 1]] + g [n - 1] n 좌 금광, w 개인 상황 에서 가장 좋 은 금광 수 = max {(n 좌 금광 을 발굴 하지 않 을 때 인원 배치 의 최대 가치, n 좌 금광 을 발굴 할 때 나머지 인원 배치 의 최대 가치 + n 좌 금광 의 금광 수)} 주의 점: j
code

def mine(n,w,g=[],p=[]):
    arr=[0]*w
    for i in range(w):
        if i+1>=p[0]:
            arr[i]=g[0]
    res=copy.deepcopy(arr)
    print(res)
    ####             
    ####res   i-1         
    ####arr   i         
    for i in range(1,n):
        for j in range(w):
            if j+1

找零钱（LeetCode 322）

题目： 钱总数amount，现有零钱列表coins，寻找零钱组合使得使用到的零钱数目最少（使用数字可重复）

思路： dp[i]表示amount为i的时候的最少次数
状态转移方程：dp[i]=min(dp[i-coin]) for coin in coins
关键点： dp=[o] + [float(‘inf’)] * amount 排除在选择min时候的干扰

code

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

삼각형 (LeetCode 120)
제목: 삼각형 더미 입 니 다. 위 에서 아래로 의 경로 와 최소 경 로 를 찾 습 니 다.
사고: 상태 전이 방정식 dp [i] [j] = min (dp [i - 1] [j - 1] + triangle [i] [j], dp [i - 1] [j] + triangle [i] [j]) 주의 점: 경계 상황 j0 과 ji 의 상황
code

class Solution:
    def minimumTotal(self, triangle: List[List[int]]) -> int:
        lens=len(triangle)
        dp=[0]*lens
        dp[0]=triangle[0]
        for i in range(1,lens):
            for j in range(i+1):
                if j==0:
                    dp[i]=[dp[i-1][j]+triangle[i][j]]
                elif j==i:
                    dp[i].append(dp[i-1][j-1]+triangle[i][j])
                else:
                    dp[i].append(min((dp[i-1][j-1]+triangle[i][j]),(dp[i-1][j]
                                                                    +triangle[i][j])))
        return min(dp[-1])

LeetCode 1025: Discover Game
제목: Alice 와 Bob 은 돌아 가면 서 게임 을 하고 숫자 N 을 선택 합 니 다. 가능 한 한 x 를 선택 하여 두 가지 조건 을 만족 시 킵 니 다. 1, N% x = = 0 2, 0 한 측 이 현재 의 두 가지 조건 을 만족 시 키 지 못 하면 실패 합 니 다. Alice 가 승 리 를 얻 으 면 True 로 돌아 갑 니 다. 그렇지 않 으 면 Bob 승리 가 False 로 돌아 갑 니 다.
사고방식: 동적 기획 이 현재 있 는 i, for j in rang (1, i), i% j = = 0 이 존재 하고 dp [i - j] = = False 와 나머지 조건 을 만족 시 키 는 상황 에서 임의의 수치 가 dp [i - j] 를 상대방 이 실패 하면 본 측 이 승리 한다.그렇지 않 으 면 상대방 이 성공 하여 본 측 이 실패 합 니 다.동시에 작은 지름길 이 있다.만약 i = 2t 즉 i 가 2 의 배수 이 고 dp [t] = False 라면 i 는 True (i% t = = 0 은 다음 j 의 for 순환 의 특수 한 사례 이기 때 문)
code

class Solution:
   def divisorGame(self, N: int) -> bool:
       dp=[False]*(N+1)
       for i in range(2,N+1):
           if i%2==0 and dp[int(i/2)]==False:
               dp[i]=True
           else:
               for j in range(1,i):
                   if i%j==0:
                       if dp[i-j]==False:
                           dp[i]=True
                           break
       return dp[N]