@ 代码随想录算法训练营第8周（C语言）|Day50（动态规划）

Day41、动态规划（包含题目 ● 322. 零钱兑换 ● 279.完全平方数）

322. 零钱兑换

题目描述

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

题目解答

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

    //dp[j]表示凑成金额为j的硬币最少数量
    int dp[amount+1];
    //由于是求凑成金额所需最少的硬笔数量,应初始化为INT_MAX
    for(int i=0;i<=amount;i++)
        dp[i]=INT_MAX;
    //base case 
    dp[0]=0;
    
    for(int i=0;i<coinsSize;i++)
    {
        for(int j=coins[i];j<=amount;j++)
        {
            //dp[j-coins[i]]凑不成，其值为INT_MAX直接跳过
            if(dp[j-coins[i]]!=INT_MAX)
                dp[j]=fmin(dp[j],dp[j-coins[i]]+1);
        }
    }
    //如果未能凑成则返回-1
    return dp[amount]==INT_MAX?-1:dp[amount];
}

题目总结

最小完全背包问题。

279.完全平方数

题目描述

给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, …）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。

给你一个整数 n ，返回和为 n 的完全平方数的最少数量。

完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

题目解答

int numSquares(int n) {
    int i;
    for(i=1;i<=n;i++){
        if((i*i)>n){
            break;
        }
    }
    int nums[i];
    for(int j=0;j<i;j++){
        nums[j]=j*j;
    }

    int dp[n+1];
    for(int j=0;j<=n;j++){
        dp[j]=INT_MAX;
    }
    dp[0]=0;
    for(int k=1;k<i;k++){
        for(int j=nums[k];j<=n;j++){
            if(dp[j-nums[k]]!=INT_MAX){
                dp[j]=dp[j]<dp[j-nums[k]]+1?dp[j]:dp[j-nums[k]]+1;
            }
        }
    }
    return dp[n];
}