Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.
給出一個正整數(shù)n，找到相加得到n的最少個數(shù)的完全平方數(shù)字（比如1， 4， 9， 16）
For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.
動態(tài)規(guī)劃解。這種類型的題目已經(jīng)接觸很多了，比較加上每個完全平方數(shù)字得到的個數(shù)，取最小的那個就可以了。定義dp[i]：相加得到i的最少個數(shù)的完全平方數(shù)字，遞推式：dp[i] = min(dp[i], dp[i - square_number]) (square_number < i)
class Solution(object): def numSquares(self, n): """ :type n: int :rtype: int """ dp = [0] + [n + 1] * n for i in range(1, n + 1): index = 1 square_number = 1 while square_number <= i: dp[i] = min(dp[i - square_number] + 1, dp[i]) index += 1 square_number = pow(index, 2) return dp[n]新聞熱點
疑難解答
