[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];
}
20240610 更新又來了！
好像有懂一點點了，然後才發現這幾天寫的跑出來結果都很慢是因為自己耍笨？！
#define MIN(A,B) (A<B)?(A):(B)
int coinChange(int* coins, int coinsSize, int amount){
    if (amount==0)
        return 0;
    int64_t *dp = calloc (amount+1, sizeof(int64_t));
    dp[0]=0;
    for (int k=1;k<= amount; k++)
        dp[k]= INT_MAX;
    for (int i=0; i< coinsSize; i++)
    {
        for (int j=coins[i]; j<=amount; j++)
        {
            if (dp[j-coins[i] != INT_MAX])
                dp[j] = MIN(dp[j], dp[j-coins[i]]+1);
        }
    }
    return (dp[amount] == INT_MAX)? (-1): dp[amount];
}