동전 문제 (고전 dp)

1266 단어 ACM - 동적 계획
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.
상태: d (i) 는 i를 조합하는 데 가장 적은 동전 수를 정의합니다.
상태 이동 방정식: d(i)=min{d(j)+1}i>=j+v
(참고: memset은 -1과 0만 초기화할 수 있습니다)
AC 소스:
class Solution {
public:
    int coinChange(vector& coins, int amount) {
        int d[10000];
        for(int i=1;i<=amount;++i)
                d[i]=(1<<20);
        d[0]=0;
        for(int i=1;i<=amount;++i)
        {
            for(int j=0;j=coins[j])
                    d[i]=min(d[i],d[i-coins[j]]+1);
            }
        }
        if(d[amount]>=(1<<20))
            return -1;
        else
            return d[amount];
        
    }
};

좋은 웹페이지 즐겨찾기