【Leetcode 279】Perfect Squares
难度: 中等(Medium)
题目:
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的平方序列,然后将n拆分为两部分,一个是某个平方数的整数倍,另一个是余数,在所有拆分的可能中选择需要次数最小的即可。计算余数所需最少次数与问题具有相同结构,因而可递归求解,并且在求解过程中会涉及计算重复问题,所以需保留中间解的答案。
代码:
1 | def getLeast(self, squares, dp, n): |
评论系统未开启,无法评论!