給一個正整數 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

總結

以上是生活随笔為你收集整理的完美平方的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。