동적 기획으로 변화를 꾀하다💰

나는 리코더의 Coin Change question과 애증 관계가 있다.나는 알고리즘 수업에서 몇 시간 동안 공부했다. 몇 달 후, 한 인터뷰에서 나는 이 문제의 변체에 대해 질문을 받아 완전히 망쳤다.이것은 꾸준히 연습하는 것이 얼마나 중요한지 증명한다!
Backtoback SWE's video은 내가 이 문제에 대한 이해를 크게 도왔다.나는 네가 그의 동영상을 보면 그가 문제를 해결할 것이라고 강력하게 건의한다.
우리 뛰어들어가자!

문제는

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

다음과 같은 입력/출력 예도 제공됩니다.Input: coins = [1, 2, 5], amount = 11Output: 3Explanation: 11 = 5 + 5 + 1문제는 최소 수량의 동전이 주어진 총수와 같아야 한다는 것이다.이 문제 에는 동적 기획 해결 방안 이 하나 있는데, 가장 좋은 단서 는 '최소' 라는 단어 를 사용하는 것 이다동적 기획 문제는 일반적으로 제약이 있는 최적화 문제를 해결할 수 있다. 이것이나 저것의 최소치, 최대치, 최단치를 찾아야 한다...나는 내가 어떻게 우연히 이 점을 발견했는지 기억이 나지 않지만, 예일대 컴퓨터과학과에는 프로그래밍 기술의 데이터 구조에 관한 500여 페이지의 PDF가 있다.섹션 5.1.4로 스크롤하면 제목을 클릭하여 section on dynamic programming을 볼 수 있습니다.

메서드
나의 첫 번째 경향은 동전 하나하나를 힘껏 검사하고 다른 동전으로 조합을 검사해서 내가 총수에 도달할 수 있는지 없는지를 보는 것이다.그러나 네가 이미 짐작한 바와 같이 이런 방법은 효율이 매우 낮다.
DP 알고리즘의 중요한 요소 중 하나는 중첩 구조와 하위 문제이다.우리는 또한 하나의 표를 기억표로 사용할 것이다. 우리는 그것을 데이터 구조로 사용하여 우리가 앞으로 다시 계산할 필요가 없는 값을 저장할 것이다.모든 동전에 대해 우리는 같은 하위 문제를 해결하려고 시도한다. "어느 값이 더 큽니까?"이것이 바로 메모리표를 사용하여 계산된 값을 저장하는 것이 알고리즘에 이렇게 중요한 이유다.

솔루션
여느 때와 마찬가지로, 내가 고려하고 작성한 첫 번째 코드는 입력이 0인 경우이다.

def coin_change(coins: List[int], amount: int):
    if not amount:
        return 0

그래서 나는 이런 상황에서 if not blah 문법을 사용하는 것이 좀 이상하다고 생각한다. 우리가 토론하는 것은 숫자의 수량이기 때문에 다른 옵션은 if amount == 0:일 수 있다.나는 코드 블록의 문법이python과 더 비슷하다고 생각하지만, 나도python 전문가는 아니다.나는 다른 사람들의 이것에 대한 생각/의견을 매우 듣고 싶다!
다음 코드는 저희 memoization table을 구축하는 것입니다.기억의 상용 응용 프로그램 중 하나는 피보나치 서열 알고리즘이지만, 이 예에서 우리는 하나의 목록을 사용하여 계산 값을 저장할 것이다.

    cols = amount + 1
    # create table with number of columns is amount + 1
    T = [0 if idx == 0 else float('inf') for idx in range(cols)]
    # set 0th index to 0, otherwise, set each idx to infinity

우선, 나는 내 기억표의 열 (또는 색인) 총수를 나타내는 변수 cols을 만들 것이다.우리가 왜 amount+1열을 원하는지 곧 알게 될 것이다.다음 줄은 목록 이해를 사용하여 표를 구성하는 것입니다.for 순환이나 더 좋은 목록 이해 등 다른 방법도 있다.하지만 다시 한 번, 나는 이것이 구렁이 같은 방식이라고 생각한다.
우리의 예시 입력과 일치합니다. 위의 코드가 실행된 후에 빈 목록이 있어야 합니다. 그 중에는 0 11개의 infs가 포함되어 있어야 합니다.T = [0, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf, inf]테이블의 다른 인덱스를 inf로 설정할 필요가 없습니다. 이 값보다 큰 값만 있으면 되는 해결 방안을 보았습니다.우리의 알고리즘이 실행된 후에 T[cols]의 값이 무엇이든지 우리의 답이 될 것이다.이 예에서 T[12]의 값은 우리가 원래 정한 금액 11에 필요한 최소 동전 수를 더한 것이다.
우리는 우리의 알고리즘의 다음 단계를 시작할 것이다!나는 이 해결 방안이 이렇게 초라하다는 것에 놀랐다.기본 사상은 다음과 같다. 우리는 주어진 동전 목록에 있는 동전 하나하나를 검사해야 한다. 우리는 동전 하나하나와 우리의 기억표에 있는 현재의 동전(이 예는 amount)을 검사해서 어느 값이 더 큰지 확인해야 한다(이것은 우리의 중첩자 문제이다).

    for j in range(len(coins)):
        for i in range(1, cols): 

좋은 순환😅 우리는 우리의 화폐 목록 T을 교체하고 인덱스 1부터 우리의 메모리표에 있는 모든 인덱스를 방문하고 있습니다.색인 0은 0이다. 왜냐하면 [1, 2, 5]의 값마다 주어진 동전을 만드는 데 필요한 수량을 대표하기 때문이다.따라서 우리의 목표 금액이 T일 때 우리는 0개의 동전을 필요로 한다.마찬가지로 우리의 목표 금액이 0일 때 우리는 11개의 동전을 필요로 한다.??은 우리가 다음에 찾아야 할 것이다!

             coin = coins[j]
             if(i >= coins[j]):
                 T[i] = min(T[i], T[i - coin] + 1)

우선, 나는 ??이라는 변수를 설정하고, 그것을 주어진 목록에 있는 현재 동전으로 설정했다.우리의 예에서 처음에는 1이었다.이것은 반드시 필요한 것은 아니지만, 그것은 내가 머릿속의 조리를 유지하는 데 도움을 줄 수 있다.그리고 나는 coin이 색인 j의 현재 동전보다 크거나 같은지 확인하고 싶다. 만약 이 조건이 사실이라면, 우리는 최종적으로 i에 분배되는 값을 결정할 것이다.우리는 현재 값 T[i] 또는 T[i]의 최소값을 검사하여 이 값을 비교적 작은 자를 기준으로 선택합니다.우리는 동전 조합에 새 동전을 추가할 것이기 때문에 T[i - coin] + 1이 필요하다.우리는 + 1에서 현재 동전의 가치를 공제합니다. 왜냐하면 현재 동전의 가치가 이 금액을 계산할 수 있는지 확인하고 있기 때문입니다.예를 들어, i이 2이고 현재 i이 5인 경우 값 5는 금액을 2로 만드는 데 사용할 수 없습니다.(너무 곤혹스러운 해석이 아니었으면 좋겠다. 마찬가지로 Backtoback SWE는 더 잘 설명했다.
정말, 그렇습니다!마찬가지로 동적 기획의 핵심 특성은 중첩된 하위 문제가 존재하기 때문에 코드는 종종 몇 줄만 남는다(최종적으로 여러 번 운행한다).흔히 볼 수 있는 장애는 동적 프로그래밍 솔루션을 사용하는 것과 귀속 솔루션 간의 차이점 (그리고 그 중 하나를 언제 사용하는지) 을 아는 것이다.나는 여전히 모든 차이를 100% 이해할 수 없지만, 내가 관찰한 것은, 만약 입력이 coin이 매우 크다면, 귀속 해결 방안은 최소 n번의 시스템 창고에 대한 함수 호출을 실행해야 하기 때문이다.이것은 창고가 넘칠 수 있다. 이것이 바로 동적 프로그래밍이 귀속 문제에 최적화를 적용하는 것과 비슷한 이유이다.
코드가 끝났을 때, 우리는 최종적으로 11개의 동전을 만드는 데 필요한 최소 수량을 되돌려야 한다.가능한 조합이 없다면, 우리는 n으로 돌아간다.나는 이미 되돌아오는 문장에 더욱 익숙해졌지만, 때때로 더 간단한 문장이 더 좋다는 것을 깨달았다.다음은 단지 "-1의 마지막 인덱스 값이 T이면 -1로 돌아가고, 그렇지 않으면 infinity의 마지막 인덱스 값으로 돌아간다"고 말했을 뿐이다.T의 마지막 색인 값이 무한대일 경우 유효한 조합이 없음을 나타냅니다.

    return -1 if (T[-1] == float('inf')) else T[-1]

너도 쓸 수 있다.

    if (T[-1] == float('inf')):
        return -1
    else:
        return T[-1]

선택은 너에게 가장 의미 있는 것이다.
다음은 완벽한 솔루션입니다.

def coinChange(self, coins: List[int], amount: int) -> int:
        if amount == 0:
            return 0

        cols = amount + 1
        T = [0 if idx == 0 else float('inf') for idx in range(cols)]

        for j in range(len(coins)):
            for i in range(1, cols): 
                coin = coins[j]
                if(i >= coins[j]):
                    T[i] = min(T[i], T[i - coin] + 1)

        return -1 if (T[-1] == float('inf')) else T[-1]

복잡성
시간의 복잡도는 O(수량x동전) 또는 O(ac)이다.나는 더욱 흔히 볼 수 있는 것은 O(mn)로 표시하는 것이라고 생각한다.
공간의 복잡도는 O(a)이고 그 중에서 a는 총량이다.T 하위 문제를 계산하고 저장하고 있습니다.

감사합니다.
나는 이 문장이 매우 길고, 텍스트가 매우 무겁고, 저열한 해석으로 가득 차 있다는 것을 알고 있지만, 당신들이 읽고 견지해 주셔서 감사합니다.🙂