Perfect Squares

LeetCode
,

第54天。

今天的题目是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.

这道题一开始看到还挺懵的，首先，它是需要用square number来做加法的，那我是不是要先判断一个数是不是一个square number,简单的思路就是将所有不大于n的square number生成出来，直接比较即可，假设我们就是用这样的方法，那么现在我们可能就有了所有不大于n的square number的序列。

然后继续回到原来的问题，我好像是不需要求出这个表达式是由什么数组成的，而是只需要求出这个表达式由多少个Square number组成的就好了，这有点像动态规划的问题，我们用动态规划的思路去想这个问题：

我们要求numSquares(n)，我们可以先尝试的假定这个表达式中有一个1,那么就可以写成numSquares(n) = numSquares(n-1)+1,那如果我们假定这个表达式中有一个4,那么就可以写成是numSquares(n) = numSquares(n-4)+1,我们可以按照这样思路写出这样的递推式：

numSquares(n) = Min{numSquares(n-k) + 1 | k is square number and k <= n}

这样的话，我们就可以写出这样的表达式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def numSquares(self, n):
    """
    :type n: int
    :rtype: int
    """
    dp = [sys.maxsize]*(n+1)
    dp[0] = 0
    for i in range(1,n+1):
        j = 1
        t = j**2
        while t <= i:
            dp[i] = min(dp[i],dp[i-t]+1)
            j+=1
            t = j**2
    return dp[-1]

很不幸，这样的方法会在6000之后的数据中超时，然后想了一早上的方式去优化，后来用c++去实现了一遍，然后。。。就过来，花了那么久的时间竟然因为语言的问题而一直解决不了。。。算了，以后还是用c++写吧，反正有时候用python,写的也很乱，还不如c++简洁：

1
2
3
4
5
6
7
8
9
10
11
12
int numSquares(int n) {
    vector<int> dp(n+1,INT_MAX);
    dp[0] = 0;
    int t;
    for(int i = 1;i <= n;i++) {
        for(int j=1;(t = j*j) <= i;j++){
            dp[i] = min(dp[i],dp[i-t]+1);
        }
        //cout << dp[i] << endl;
    }
    return dp[n];
}