[leetcode] 322. Coin Change 문제 해결 보고서

1470 단어 LeetCode동적 기획
제목 링크:https://leetcode.com/problems/coin-change/
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 .
Example 1: coins =  [1, 2, 5] , amount =  11 return  3  (11 = 5 + 5 + 1)
Example 2: coins =  [2] , amount =  3 return  -1 .
Note: You may assume that you have an infinite number of each kind of coin.
사고방식: 동적 기획의 제목은 가방과 약간 비슷하다. 그 상태 이동 방정식은 다음과 같다.
	dp[i] = min(dp[i - coins[j]]+1, dp[i])
초기화할 때 dp 배열을 dp[0]=0을 제외하고 INT 로 설정MAX. 용량이 커질 때마다 모든 동전을 훑어보고 어떤 동전을 가져가면 현재 용량에서 동전의 수량을 최소화할 수 있는지 찾아낸다.
코드는 다음과 같습니다.
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        if(coins.size() == 0 || amount ==0) return 0;
        vector<int> dp(amount+1, INT_MAX);
        dp[0] = 0;
        for(int j = 1; j <= amount; j++)
            for(int i = 0; i < coins.size(); i++)
                if(j - coins[i] >= 0 && dp[j-coins[i]] != INT_MAX)
                    dp[j] = min(dp[j-coins[i]]+1, dp[j]);

        return dp[amount]!=INT_MAX?dp[amount]:-1;
    }
};
참조:https://www.hrwhisper.me/leetcode-coin-change/

좋은 웹페이지 즐겨찾기