[Leetcode] Perfect Squares 完美平方數(shù)

Moxmi 發(fā)布于2019-08-14 12:33 / 887人閱讀

摘要：動態(tài)規(guī)劃復(fù)雜度時(shí)間空間思路如果一個(gè)數(shù)可以表示為一個(gè)任意數(shù)加上一個(gè)平方數(shù)，也就是，那么能組成這個(gè)數(shù)最少的平方數(shù)個(gè)數(shù)，就是能組成最少的平方數(shù)個(gè)數(shù)加上因?yàn)橐呀?jīng)是平方數(shù)了。

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.

動態(tài)規(guī)劃 復(fù)雜度

時(shí)間 O(N^2) 空間 O(N)

思路

如果一個(gè)數(shù)x可以表示為一個(gè)任意數(shù)a加上一個(gè)平方數(shù)bｘb，也就是x=a+bｘb，那么能組成這個(gè)數(shù)x最少的平方數(shù)個(gè)數(shù)，就是能組成a最少的平方數(shù)個(gè)數(shù)加上1（因?yàn)閎*b已經(jīng)是平方數(shù)了）。

代碼

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        // 將所有非平方數(shù)的結(jié)果置最大，保證之后比較的時(shí)候不被選中
        Arrays.fill(dp, Integer.MAX_VALUE);
        // 將所有平方數(shù)的結(jié)果置1
        for(int i = 0; i * i <= n; i++){
            dp[i * i] = 1;
        }
        // 從小到大找任意數(shù)a
        for(int a = 0; a <= n; a++){
            // 從小到大找平方數(shù)bｘb
            for(int b = 0; a + b * b <= n; b++){
                // 因?yàn)閍+b*b可能本身就是平方數(shù)，所以我們要取兩個(gè)中較小的
                dp[a + b * b] = Math.min(dp[a] + 1, dp[a + b * b]);
            }
        }
        return dp[n];
    }
}