Two C solutions, 40ms and 36ms respectively, how can I improve?


  • 0
    Q

    I can see that there are submissions that run 32 ms and even 24 ms for all the test cases. I have two approaches, both use the dynamic programming algorithm, but runs 40 and 36 ms separately. The second is a little better because the inner loop (on the amount) starts at the current coin value, while the first has inner loop on the coins.

    int coinChange(int* coins, int coinsSize, int amount) {
        unsigned int* dp = (unsigned int*)malloc(sizeof(int)*(amount + 1));
        int i, j, ans, t;
        memset(dp, 0xff, sizeof(int) * (amount + 1));
        dp[0] = 0;
        for (i = 1; i <= amount; i++) {
            for (j = 0; j < coinsSize; j++) {
                if (coins[j] <= i) {
                    t = dp[i - coins[j]] + 1;
                    if (t > 0 && t < dp[i]) {
                        dp[i] = t;
                    }
                }      
            }
        }
        ans = dp[amount];
        free(dp);
        return ans;
    }
    
    int coinChange2(int* coins, int coinsSize, int amount) {
        unsigned int* dp = (unsigned int*)malloc(sizeof(int)*(amount + 1));
        int i, j, ans, t;
        memset(dp, 0xff, sizeof(int)*(amount + 1));
        dp[0] = 0;
        for (i = 0; i < coinsSize; i++) {
            for (j = coins[i]; j <= amount; j++) {
                t = dp[j - coins[i]] + 1;
                if (t > 0 && t < dp[j]) {
                    dp[j] = t;
                }
            }
        }
        ans = dp[amount];
        free(dp);
        return ans;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.