力扣（322.279）补8.1

322.零钱兑换

我一开始想用二维dp，但是错了。

标答用的一维dp。

int coinChange(int* coins, int coinsSize, int amount){

    int dp[amount+1];

    for(int i=1;i<=amount;i++)

    dp[i]=amount+1;

这里的初始化，我用memset不太行。部分用例没过。

    dp[0]=0;

这里容易错。

    for(int i=1;i<=amount;i++){

        for(int j=0;j

            if(i>=coins[j])

            dp[i]=fmin(dp[i],dp[i-coins[j]]+1);

        }

    }

    return dp[amount]>amount?-1:dp[amount];

 

}

279.完全平方数

这题和322，非常像，我自己也能做出来，就是每个数可出现多次的组合，求最少元素的组合。

那就直接套公式了呗。

int numSquares(int n){

    int dp[n+1];

    for(int i=0;i<=n;i++){

        dp[i]=n+1;

    }

    dp[0]=0;

    for(int i=1;i<=n;i++){

        for(int j=1;j*j<=i;j++){

            dp[i]=fmin(dp[i-j*j]+1,dp[i]);

        }

    }

    return dp[n]；

}