279. Perfect Squares

Problem from leetcode Perfect Squares

---

有两种方法可以解决这道题，一种是brute force search，另一种是动态规划。

1. 暴力枚举 brute force time complexity: exponential
2. 完全背包 dynamic programming time complexity: O(n^3/2) | space complexity: O(n)

---

1, 暴力枚举 brute force

class Solution {
public:
    int numSquares(int n) {
        int digit = sqrt(n);
        if(digit*digit == n) return 1;
        
        int minimum = n;//this is the maximum number
        dfs(n, 0, digit, 0, minimum);
        return minimum;
    }
    void dfs(int n, int curSum, int curDigit, int curNum, int& minimum)
    {
        if(curSum > n) return;
        if(curSum == n)
        {
            minimum = minimum>curNum?curNum:minimum;
            return;
        }
        if(curDigit <= 0) return; 
        if(curDigit == 1) 
        { 
            curNum += n-curSum; 
            minimum = minimum>curNum?curNum:minimum;
            return;
        }
        //either use curDigit or not use
        if(n-curSum >= curDigit*curDigit)
            dfs(n, curSum+curDigit*curDigit, curDigit, curNum+1, minimum);
        dfs(n, curSum, curDigit-1, curNum, minimum);
    }
};

As expected, brute force will result in Time Limit Exceeded.

---

2, dynamic programming

这其实是一道完全背包问题，不过我们不需要像往常写完全背包一样写这道题，有更简单的写法，而且时间复杂度都是O(n^3/2)

class Solution {
public:
    int numSquares(int n) {
        if(n==1 || n==2 || n==3) return n;
        
        //dp[i] store the result of "i"
        int dp[n+1];
        memset(dp, 0, sizeof(dp));
        
        dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3;
        for(int i = 4; i < n+1; ++i) 
        { 
            //now divide i to two parts: i = left + right 
            int right = 1; 
            dp[i] = i; 
            while(i >= right*right)
            {
                dp[i] = dp[i]>dp[i-right*right]+1?dp[i-right*right]+1:dp[i];
                ++right;
            }
        }
        return dp[n];
    }
};

Java:

public class Solution {
    public int numSquares(int n) {
        if(n==1 || n==2 || n==3) return n;
        
        //dp[i] store the result of "i"
        int[] dp = new int[n+1];
        
        dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3;
        for(int i = 4; i < n+1; ++i) 
        { 
            //now divide i to two parts: i = left + right 
            int right = 1; 
            dp[i] = i; 
            while(i >= right*right)
            {
                dp[i] = dp[i]>dp[i-right*right]+1?dp[i-right*right]+1:dp[i];
                ++right;
            }
        }
        return dp[n];
    }
}

Python:

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n==1 or n==2 or n==3: return n
        dp = [0]*(n+1)
        dp[1], dp[2], dp[3] = 1,2,3
        for i in range(4, n+1):
            dp[i] = i
            right = 1
            while i >= right*right:
                dp[i] = dp[i] if dp[i]<dp[i-right*right]+1 else dp[i-right*right]+1
                right += 1
        return dp[n]