LeetCode 322. Coin Change

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#define min(a,b) (((a) > (b)) ? (b) : (a))
int cmpfunc (const void * a, const void * b) {
    return ( *(int*)a - *(int*)b );
}
int coinChange(int* coins, int coinsSize, int amount) {
    qsort(coins, coinsSize, sizeof(int), cmpfunc);
   
    int* dp=(int*)malloc(sizeof(int)*(amount+1));
    dp[0]=0;
    for(int i=1;i<=amount;++i){
        int tmp=INT_MAX;
        for(int j=0;j<coinsSize;++j){
            if(i>=coins[j]){
                tmp=min(dp[i-coins[j]],tmp);
            }
            else{
                break;
            }
        }
        if(tmp!=INT_MAX){
            dp[i]=tmp+1;
        }
        else{
            dp[i]=INT_MAX;
        }
       
    }
    if(dp[amount]==INT_MAX){
        return -1;
    }
    else{
        return dp[amount];
    }
}



Leave a Reply

Your email address will not be published. Required fields are marked *