LEET

void CountArry(int *NumArry, int amount, const int *coins, int coinsSize) { for(int i = 0; i <= amount; i++) { NumArry[i] = amount + 1; } NumArry[0] = 0; // for (int i = 0; i < coinsSize; i++) { // NumArry[coins[i]] = 1; // } } int Min(const int num1, const int num2) { if (num1 > num2) { return num2; } else { return num1; } } int coinChange(int* coins, int coinsSize, int amount){ int *NumArry = (int *)malloc(sizeof(int) * (amount + 1)); CountArry(NumArry, amount, coins, coinsSize); for(int i = 1; i <= amount; i++) { for (int j = 0; j < coinsSize; j++) { if (i >= coins[j]) { NumArry[i] = Min(NumArry[i - coins[j]] + 1, NumArry[i]); } } } int ret = NumArry[amount]; if (NumArry[amount] > amount) { free(NumArry); return -1; } free(NumArry); return ret; }

犯错点总结：1、注释处没有考虑到[1] 0的情况，导致NumArry在malloc的时候只有一个元素，而注释处会给NumArry[1]复制当然这里是没有必要赋值的。

void CountArry(int *NumArry, int amount, const int *coins, int coinsSize) { for(int i = 0; i <= amount; i++) { NumArry[i] = amount + 1; } NumArry[0] = 0; // for (int i = 0; i < coinsSize; i++) { // NumArry[coins[i]] = 1; // } }

2、动态规划原理没搞清，动态啊规划思想是前一步所有可能+1到now时刻，哪一步最少，now时的次数就最少，这里刚开始没有+1，导致计算时结果都是0

for(int i = 1; i <= amount; i++) { for (int j = 0; j < coinsSize; j++) { if (i >= coins[j]) { NumArry[i] = Min(NumArry[i - coins[j]] + 1, NumArry[i]); } } }

3、第三个误去就是对小于1次可能性的删选，当没有可能得到结果时，要返回-1，这里首先要搞清楚什么时候会出现这中情况。

从道理上来讲，当我10的时候，可能性大于10，那么这种情况肯定时错误的，为了营造这种可能性，首先初始化的时候，把除了0的地方都复制为N+1,因此，没走正常渠道，结果就是N+1.

int ret = NumArry[amount]; if (NumArry[amount] > amount) { free(NumArry); return -1; } free(NumArry); return ret; for(int i = 0; i <= amount; i++) { NumArry[i] = amount + 1; }