leetcode279完全平方数

快来打我* 2022-09-03 12:29 113阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]  
思路

1.  **动态规划**
2.  后一个的结果和前一个有关
3.  表达式为`f[i]=(j=1->j<=sqrt(i)) min(f(i),f(i-j*j)+1)`
4.  动态规划的题目一般都是有累计或累加的过程 5 = 4+1，f(5) = f(4-1 \* 1)+1，f(5)=f(5-2 \* 2)+1，求取f(5)最小值

#include<stdio.h>
    #include<string.h>
    #include<math.h>
    #define min(a,b) ((a)<(b)?a:b)
    int numSquares(int n){ 
        int flag[n+1];
        int i=0,j=0;
        for(i=0;i<=n;i++)
            flag[i]=n+1;
        i=1;
        flag[0] = 0;
    
        for(i=1 ;i<=n;i++){ 
            for(j=1;j<=sqrt(i);j++){ 
                flag[i] = min(flag[i],flag[i-j*j]+1);
            }
        }
        return flag[n];
    }
    
    int main(){ 
        int n=13;
        int re = numSquares(n);
        printf("re = %d\n",re);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTY3MjQwNA_size_16_color_FFFFFF_t_70]: /images/20220829/c0897b7cddaf4d898544a62a37ad133d.png

发表评论取消回复

表情：

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

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

相关阅读

相关 279. 完全平方数——（LeetCode刷题）

279. 完全平方数给你一个整数 n ，返回和为 n 的完全平方数的最少数量。完全平方数是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的

柔光的暖阳◎/ 2024年04月01日 19:46/ 0 赞/ 77 阅读

相关 LeetCode-279.完全平方数

目录题目思路回溯法动态规划动态规划(压缩) 题目来源 [279.完全平方数][279.] 题目思路

柔光的暖阳◎/ 2024年03月25日 20:21/ 0 赞/ 109 阅读

相关 Leetcode 279. 完全平方数

Leetcode 279. 完全平方数 1、问题分析 2、问题解决 3、总结 1、问题分析题目链接：[https://leetcode-cn.

墨蓝/ 2023年02月14日 03:06/ 0 赞/ 28 阅读

相关 279. 完全平方数

题目： [279. 完全平方数][279.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_te

你的名字/ 2022年11月25日 00:58/ 0 赞/ 192 阅读

相关 279. 完全平方数

2021-06-11 LeetCode每日一题链接：[https://leetcode-cn.com/problems/perfect-squares/][https_

女爷i/ 2022年10月06日 06:52/ 0 赞/ 205 阅读

相关 279. 完全平方数

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

心已赠人/ 2022年10月06日 05:42/ 0 赞/ 214 阅读

相关 leetcode279完全平方数

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

快来打我*/ 2022年09月03日 12:29/ 0 赞/ 114 阅读

相关 LeetCode 279 完全平方数

https://leetcode-cn.com/problems/perfect-squares/ ![在这里插入图片描述][2f27a9f8cc0b4daeab65061

柔光的暖阳◎/ 2022年09月03日 10:24/ 0 赞/ 209 阅读

相关 leetcode 279 完全平方数

前言题目：[279. 完全平方数][279.] 参考题解：[完全平方数-代码随想录][-] -------------------- 提交代码完全背包问题

刺骨的言语ヽ痛彻心扉/ 2022年08月28日 03:52/ 0 赞/ 193 阅读

相关 LeetCode279——完全平方数

我的LeetCode代码仓：[https://github.com/617076674/LeetCode][https_github.com_617076674_LeetCod

偏执的太偏执、/ 2022年03月10日 07:24/ 0 赞/ 218 阅读