279. Perfect Squares(完全平方和数/ 交换硬币题322）

叁歲伎倆 2023-02-13 14:53 15阅读 0赞

给定一个正整数Ñ，找到完全平方数的数量最少（例如，1, 4, 9, 16, …），其总和Ñ。  
范例1：  
输入： n = 12  
输出： 3  
说明：12 = 4 + 4 + 4.

范例2：  
输入： n = 13  
输出： 2  
说明：13 = 4 + 9.

思路：  
看到这题的时候就想起了leetcode332里面的硬币交换，只不过现在是对于硬币的种类数额换成了完全平方数。  
存好了vector之后，就开始动态规划的。  
对于数额为 i 的sum，方法数为数额 i - 一个coin后的数 +1的最小值。遍历每一个coin后得出来的 dp\[target\] 就是ret。  
（前一个coin的结果会影响后一个coin的结果。因为都是一个dp。所以最后就是所有的coin的结果综合的minnum）

code:

//硬币的组合 coin change
    class Solution { 
    public:
        int numSquares(int n) { 
         //first：设置coin的数组
        vector<int> perfect;
            for(int i=1;i<=n; i++)
                if(i*i<=n)
                    perfect.push_back(i*i);
            //second :开始动作
            return  numSquares(n,perfect);
        }
    private:
        //dp[i]=min(dp[i],dp[i-coin]+1)
        int numSquares(int target, vector<int> &perSqua){ 
            vector<int> dp(target+1,target+1);  //存储每一种的和的方法数
            dp[0]=0;            //和为0的不需要，同时也是基础
            for(auto per:perSqua)
                for(int i=per;i<=target; ++i){ 
                    dp[i]=min(dp[i], dp[i-per]+1);
                }
            return dp[target];
        }
    };

发表评论取消回复

表情：

评论列表（有 0 条评论，15人围观）

还没有评论，来说两句吧...

相关阅读

相关 LeetCode #279 Perfect Squares

Question Given a positive integer n, find the least number of perfect square numbers (f

我会带着你远行/ 2023年08月17日 17:47/ 0 赞/ 111 阅读

相关 279. Perfect Squares(完全平方和数/ 交换硬币题322）

给定一个正整数Ñ，找到完全平方数的数量最少（例如，1, 4, 9, 16, …），其总和Ñ。范例1：输入： n = 12 输出： 3 说明：12 = 4 +

叁歲伎倆/ 2023年02月13日 14:53/ 0 赞/ 16 阅读

相关 leetcode 279. Perfect Squares | 279. 完全平方数（动态规划，Java）

题目 [https://leetcode.com/problems/perfect-squares/][https_leetcode.com_problems_perfe

左手的ㄟ右手/ 2022年10月11日 13:50/ 0 赞/ 167 阅读

相关 [leetcode] 279. Perfect Squares（DP）（平方数）

Given a positive integer n, find the least number of perfect square numbers (for example

青旅半醒/ 2022年10月02日 11:59/ 0 赞/ 149 阅读

相关 Perfect Squares（C++完全平方数）

（1）动态规划 class Solution { public: int numSquares(int n) {

￡神魔★判官ぃ/ 2022年09月06日 15:29/ 0 赞/ 171 阅读

相关 Perfect Squares（C++完全平方数）

（1）动态规划 class Solution { public: int numSquares(int n) {

古城微笑少年丶/ 2022年09月06日 15:28/ 0 赞/ 176 阅读

相关 Perfect Squares（C++完全平方数）

（1）动态规划 class Solution { public: int numSquares(int n) {

矫情吗；*/ 2022年09月06日 15:28/ 0 赞/ 191 阅读

相关 leetcode 279. Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example

不念不忘少年蓝@/ 2022年08月20日 13:14/ 0 赞/ 29 阅读

相关 279. Perfect Squares

本周依旧是做与图论相关的题目，作为对图论知识的巩固。题目：279. Perfect Squares Given a positive integer n, find t

ゝ一纸荒年。/ 2021年10月01日 02:22/ 0 赞/ 222 阅读

相关 LeetCode : 279. Perfect Squares 数值平方和最小个数

试题 Given a positive integer n, find the least number of perfect square numbers (for ex

我不是女神ヾ/ 2021年06月24日 16:11/ 0 赞/ 369 阅读