卖萌的弱渣

I am stupid, I am hungry.

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.

Solution

  • 初始化将dp数组置为无穷大；令dp[y * y] = 1，其中：y * y <= n

  • 状态转移方程：

dp[x + y * y] = min(dp[x + y * y], dp[x] + 1)

  • 其中：dp [i] 表示凑成i所需的平方和数字的最小个数，并且 x + y * y <= n
(Perfect-Squares.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

import sys
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # dp[i+j*j] = min(dp[i]+1, dp[i+j*j])

        dp = [sys.maxint]*(n+1)
        i = 1
        while i*i <= n:
            dp[i*i] = 1
            i += 1
        for i in range(1,n+1):
            j = 1
            while i+j*j <=n:
                dp[i+j*j] = min(dp[i]+1, dp[i+j*j])
                j += 1
        return dp[n]
if __name__ == "__main__":
    sol = Solution()
    print sol.numSquares(5673)