Leetcode 279. Perfect Squares

Problem

Given an integer n, return the least number of perfect square numbers that sum to n.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself. For example, 1, 4, 9, and 16 are perfect squares while 3 and 11 are not.

Algorithm

Dynamic programmi服务器托管网ng (DP).

Code

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [0] * (n + 1)
        for i in range(n+1):
            dp[i] = i 
        for i in range(1, 101):
            if i * 服务器托管网i > n: break
            for j in range(1, n+1):
                if j >= i * i and dp[j] > dp[j - i * i] + 1:
                    dp[j] = dp[j - i * i] + 1
        return dp[n] 

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: 如何避免JavaScript中的内存泄漏？

前言 过去，我们浏览静态网站时无须过多关注内存管理，因为加载新页面时，之前的页面信息会从内存中删除。 然而，随着单页Web应用（SPA）的兴起，应用程序消耗的内存越来越多，这不仅会降低浏览器性能，甚至会导致浏览器卡死。因此，在编码实践中，开发人员需要更加关注与…