《leetcode》：Perfect Squares

本文主要是介绍《leetcode》：Perfect Squares，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

思路

这个题自己也没有做出来，哎，水平不够也；

思路来自于：https://segmentfault.com/a/1190000003768736

    public int numSquares(int n) {int[] dp=new int[n+1];Arrays.fill(dp, Integer.MAX_VALUE);//将所有平方和的结果置为1for(int i=0;i*i<=n;i++){dp[i*i]=1;}/** 如果一个数x可以表示为一个任意数a加上一个平方数bｘb，也就是x=a+bｘb，那么能组成这个数x最少的平方数个数，* 就是能组成a最少的平方数个数加上1（因为b*b已经是平方数了）。* */for(int a=0;a<n;a++){for(int b=0;a+b*b<=n;b++){dp[a+b*b]=Math.min(dp[a]+1, dp[a+b*b]);}}return dp[n];}

这篇关于《leetcode》：Perfect Squares的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---