[322] Coin Change

費了九牛二虎之力～終於有一丁點懂了～於是寫(x)模仿(o)了一個先sorting 的版本

#define MIN(a, b)    (a<b)?a:b
int comp(const void *a , const void *b)
{
    return (*(int *)a - *(int*)b);
}

int coinChange(int* coins, int coinsSize, int amount){
    qsort((void *)coins,coinsSize,sizeof(int),comp);
    int total[amount+1];

    total[0]=0;
    int i, j;
    for (i=1;i<=amount;i++)
    {
        total[i] =INT_MAX;
        for (j=0;j<coinsSize;j++)
        {
            if (i-coins[j]<0)
                break;
            if (total[i - coins[j]] != INT_MAX)
                total[i]= MIN(total[i], total[i-coins[j]]+1);
        }
    }
    return total[amount] == INT_MAX? (-1):total[amount];
}

然後發現極慢XD 看了半天還是沒有很確定為什麼可以有不用sorting 的版本?!
int coinChange(int* coins, int coinsSize, int amount){
    int total[amount+1];

    total[0]=0;
    int i, j;
    for (i=1;i<=amount;i++)
    {
        total[i] =INT_MAX;
        int tmpMin = INT_MAX;
        for (j=0;j<coinsSize;j++)
        {
            if (i-coins[j] >=0)
            {
                if (tmpMin>=total[i-coins[j]])
                    tmpMin=total[i-coins[j]];
            }
        }
        if (tmpMin != INT_MAX)
            total[i] = tmpMin + 1;
    }
    return total[amount] == INT_MAX? (-1):total[amount];
}