Perfect Squares

Given a positive integer

n, find the least number of perfect square numbers (for example,`1, 4, 9, 16, ...`

) which sum ton.For example, given

n=`12`

, return`3`

because`12 = 4 + 4 + 4`

; givenn=`13`

, return`2`

because`13 = 4 + 9`

.

Credits:

Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.Show Similar Problems

Dynamic programming.

dp[i] = min(dp[k*k] + dp[i – k*k]), k = 0,1,2,3,…,sqrt(i)

class Solution { public: int numSquares(int n) { int dp[n + 1]; for(int i = 1; i <= n; i++){ dp[i] = n; int k = 1; while(k*k <= i){ if(k*k == i){ dp[i] = 1; } else{ dp[i] = dp[i] > dp[k*k] + dp[i - k*k]? dp[k*k] + dp[i - k*k]: dp[i]; } k++; } } return dp[n]; } };