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

• 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;
}``````

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