完美平方问题（279）——动态规划

概述

给出一个正整数n，把n拆成几个数的平方和，求最少可以拆成几个数。例如：
n=12, 返回3，因为12=2^2+2^2+2^2

原题

https://leetcode.com/problems/perfect-squares/description/
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.

思路

动态规划
要求n的完美平方数p(n)，
假如n的完美平方式子中包含1，则p(n) = p(n-1) + 1；
假如n的完美平方式子中包含4，则p(n) = p(n-4) + 1；
假如n的完美平方式子中包含9，则p(n) = p(n-9) + 1；
……
因此，要求p(n)，只需先求p(n-1), p(n-4), p(n-9) …… 再找出它们中的最小值，再加一。

代码

class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 用上限n初始化结果数组
        nums = [i for i in range(n+1)]
        # 从1开始填充结果数组
        for i in range(1, n+1):
            j=1
            # 所有可能包含的平方数j
            while j*j <= i:
                nums[i] = min(nums[i], nums[i-j*j]+1)
                j += 1
        return nums[n]