LintCode 完美平方题目分析代码

题目

给一个正整数 n, 找到若干个完全平方数(比如1, 4, 9, ... )使得他们的和等于 n。你需要让平方数的个数最少。

样例 给出 n = 12, 返回 3 因为 12 = 4 + 4 + 4。 给出 n = 13, 返回 2 因为 13 = 4 + 9。

分析

动态规划,dp[i]表示n=i时,最小的个数。 显然可以求出dp值为1的值,并以此进行判断

代码

public class Solution {
    /**
     * @param n a positive integer
     * @return an integer
     */
    public int numSquares(int n) {
        // Write your code here
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        
        for(int i=0;i*i<=n;i++) {
            dp[i*i] = 1;
        }
        
        for(int i=1;i<=n;i++) {
            for(int j=1;j*j<=i;j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }

        return dp[n];
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏desperate633

二维数组中的查找代码

9720
来自专栏和蔼的张星的图像处理专栏

488. 快乐数

一个数是不是快乐是这么定义的:对于一个正整数,每一次将该数替换为他每个位置上的数字的平方和,然后重复这个过程直到这个数变为1,或是无限循环但始终变不到1。如果可...

19930
来自专栏前端儿

前缀式计算

输入有多组测试数据,每组测试数据占一行,任意两个操作符之间,任意两个操作数之间,操作数与操作符之间都有一个空格。输入的两个操作数可能是小数,数据保证输入的数都是...

18310
来自专栏C/C++基础

常见排序算法分类

  此篇博客不讨论排序算法的思想,时间复杂度,空间复杂度,实现代码。只介绍常见排序算法有哪些,并按照什么进行分类。   排序算法分为两大类: 比较类...

16620
来自专栏轮子工厂

一口气吃下数组的存储方式

Long long ago,我们讲到了数组《聊一聊数组背后的那点事》,这个已经是迈进指针的第一步了,主要的内容是一维数组,今天我们将讲述二维数组。当结束了今天的...

23010
来自专栏武培轩的专栏

Leetcode#561. Array Partition I(数组拆分 I)

给定长度为 2n 的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), ..., (an, bn) ,使得从1 到 n 的 ...

23420
来自专栏书山有路勤为径

同字符词语分组

已知一组字符串,将所有anagram(由颠倒字母顺序而构成的字)放到一起输出。 例如:["eat", "tea", "tan", "ate", "nat", ...

10210
来自专栏老秦求学

题目1054:字符串内排序

题目描述: 输入一个字符串,长度小于等于200,然后将输出按字符顺序升序排序后的字符串。 输入: 测试数据有多组,输入字符串。 输出: 对于每组输入,输出处理后...

35570
来自专栏数据结构与算法

U9249 【模板】BSGS

题目描述 给定a,b,p,求最小的非负整数x 满足a^x≡b(mod p) 若无解 请输出“orz” 输入输出格式 输入格式: 三个整数,分别为a,b,p 输出...

37270
来自专栏机器学习从入门到成神

2014百度研发真题及其解析-求比指定数大且最小的“不重复数”

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

16420

扫码关注云+社区

领取腾讯云代金券