随想录算法训练营第四十五天|322.零钱兑换、279.完全平方数

322.零钱兑换

public class Solution {
    public int CoinChange(int[] coins, int amount) {
        int[] dp=new int [amount+1];
        int max=int.MaxValue;
        for(int i=0;i<dp.Length;i++)
        {
            dp[i]=max;
        }
        dp[0]=0;
        for(int i=0;i<coins.Length;i++)
        {
            for(int j=coins[i];j<=amount;j++)
            {
                if(dp[j-coins[i]]!=max)
                {
                    dp[j]=Math.Min(dp[j],dp[j-coins[i]]+1);
                }
            }
        }
        return dp[amount]==max?-1:dp[amount];
    }
}

此题可以采用完全背包来做，因为每个数可以多次使用，同时只考虑方法数所以先物品后背包和先背包后物品均可实现，状态转移方程为Dp[j]=Math.Min(Dp[j],Dp[j-coins[i]]+1)，最终返回结果时候看是否为最大值，最大值则说明零钱找不齐，返回-1。

279.完全平方数

public class Solution {
    public int NumSquares(int n) {
        int[]dp=new int[n+1];
        int max=int.MaxValue;
        for(int i=0;i<dp.Length;i++)
        {
            dp[i]=max;
        }
        dp[0]=0;
        for(int i=1;i*i<=n;i++)
        {
            for(int j=i*i;j<=n;j++)
            {
                dp[j]=Math.Min(dp[j-i*i]+1,dp[j]);
            }
        }
        return dp[n];
    }
}

在上一题的基础上将每个Coins[i]改为I*I即可满足题意。

原文地址：https://blog.csdn.net/ShengHuoWeiYang/article/details/136359118

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！