[LintCode/LeetCode] Perfect Squares

sydMobile 發(fā)布于2019-08-14 16:23 / 3241人閱讀

摘要：動(dòng)態(tài)規(guī)劃法建立空數(shù)組從到每個(gè)數(shù)包含最少平方數(shù)情況，先所有值為將到范圍內(nèi)所有平方數(shù)的值賦兩次循環(huán)更新，當(dāng)它本身為平方數(shù)時(shí)，簡(jiǎn)化動(dòng)態(tài)規(guī)劃法四平方和定理法

Problem

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

Example

Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9

Note

這道題在OJ有很多解法，公式法，遞歸法，動(dòng)規(guī)法，其中公式法時(shí)間復(fù)雜度最優(yōu)（four square theorem）。
不過(guò)我覺(jué)得考點(diǎn)還是在動(dòng)規(guī)吧，也更好理解。

Solution

1. 動(dòng)態(tài)規(guī)劃法

public class Solution {
    public int numSquares(int n) {
        //建立空數(shù)組dp：從0到n每個(gè)數(shù)包含最少平方數(shù)情況，先f(wàn)ill所有值為Integer.MAX_VALUE;
        int[] dp = new int[n+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        //將0到n范圍內(nèi)所有平方數(shù)的dp值賦1；
        for (int i = 0; i*i <= n; i++) {
            dp[i*i] = 1;
        }
        //兩次循環(huán)更新dp[i+j*j]，當(dāng)它本身為平方數(shù)時(shí)，dp[i+j*j] < dp[i]+1
        for (int i = 0; i <= n; i++) {
            for (int j = 0; i+j*j <= n; j++) {
                dp[i+j*j] = Math.min(dp[i]+1, dp[i+j*j]);
            }
        }
        return dp[n];
    }
}

2. 簡(jiǎn)化動(dòng)態(tài)規(guī)劃法

public class Solution {
    public int numSquares(int n) {
        int[] dp = new int[n+1];
        for (int i = 0; i <= n; i++) {
            dp[i] = i;
            for (int j = 0; j*j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}

3. 四平方和定理法

public class Solution {
    public int numSquares (int n) {
        int m = n;
        while (m % 4 == 0)
            m = m >> 2;
        if (m % 8 == 7)
            return 4;
        int sqrtOfn = (int) Math.sqrt(n);
        if (sqrtOfn * sqrtOfn == n) //Is it a Perfect square?
            return 1;
        else {
                for (int i = 1; i <= sqrtOfn; ++i){
                    int remainder = n - i*i;
                    int sqrtOfNum = (int) Math.sqrt(remainder);
                    if (sqrtOfNum * sqrtOfNum == remainder)
                        return 2;
                }
            }
        return 3;
    }
}