LeetCode279. 完全平方数

LeetCode279. 完全平方数,第1张

思路

首先该题的数字可以重复使用,所以是一个完全背包问题。


动规五部曲

1.定义dp数组

dp[i]表示:和为 i的完全平方数的最少数量


2.递推公式

dp[j]=Math.min(dp[j-i*i]+1,dp[j]);

3.初始化

因为求的是最少的数量

dp[0]=0;其他元素要最大。


4.遍历顺序

可以先遍历物品也可以先遍历背包。


其中i*i就是物品的价值。


5.打印dp数组

数组的最后一个元素如果不是初始值就是最后的结果,如果是的话,就返回-1.

代码
class Solution {
    public int numSquares(int n) {
        int dp[] = new int[n+1];
        dp[0]=0;
        for(int i = 1;i<=n;i++){
            dp[i] =100000;
        }
        for(int i = 1;i<=n;i++){
             for(int j=i*i;j<=n;j++){
                dp[j]=Math.min(dp[j-i*i]+1,dp[j]);
            }
        }
        if(dp[n] == 100000){
            return -1;
        }
        return dp[n];
       

    }
}

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/563220.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-02
下一篇 2022-04-02

发表评论

登录后才能评论

评论列表(0条)

保存