完美平方

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

样例

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

高级版本的动态规划
简单的动态规划 一般都是从dp[n]到dp[n+1] 
这里是 dp[n]到dp[n+i* i]
而且i是0到一个不溢出的最大值。 这个思路比较难想到，是一个难点
另一个就是dp长度是n+1，i和j都是从0开始， 这个边界条件的处理让程序简单起来

 

这个看起来很优美简洁的程序有一个很大的问题。 但是lintcode 竟然过了。。。

就是输入值是最大值的时候，第八行直接报错。

可能这个题考察的不是这个。想兼容这种情况  可以dp[n]用一个变量来单独保存，就是程序里面判断起来可能low一点儿，大家有没有更好的方法呢？（假装有人会看）

 

 

 

public class Solution {/** @param n: a positive integer* @return: An integer*/public int numSquares(int n) {// write your code hereint[] dp = new int[n+1];for(int i =0; i<=n; i++){dp[i] = Integer.MAX_VALUE;//初始化数组 }for(int i = 0;i*i <= n; i++){dp[i*i] = 1; //把最小的这种完全平方的存进去 }for(int i = 0; i <= n; i++){//这里从零开始 边界条件的处理让整个程序简介起来for(int j = 0; i+j*j <= n; j++){//和正常dp不同的地方，不是从dp[n]到dp[n+1]的操作 而是每次都是从dp[n]到若干个dp的逼近dp[i+j*j] = Math.min(dp[i]+1,dp[i+j*j]);}}return dp[n];} }

 

转载于:https://www.cnblogs.com/tobemaster/p/7858558.html

总结

以上是生活随笔为你收集整理的完美平方的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。