leetcode Perfect Squares

leetcode 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.

题目地址: leetcode Perfect Squares

题意: 给定一个整数n,找到最少的完全平方数使得他们的和为n

思路:

dp,设dp[i]为和i的最少完全平方数。

dp[i] = min(dp[i – j*j] + 1) {j *j <i}

 

code

c++

Python同样的代码会超时。。。

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode Perfect Squares
本文地址:https://www.hrwhisper.me/leetcode-perfect-squares/

听说长得好看的已经打赏了

Leetcode , , . permalink.

2 thoughts on “leetcode Perfect Squares

Leave a Reply

Your email address will not be published. Required fields are marked *