279. Perfect Squares

Description

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, return3because12 = 4 + 4 + 4; given n=13, return2because13 = 4 + 9.

Discussion

Method

vector<int> dp(n+1, 0);

for(i , i^2 < n):

dp\[i^2\] = 1;

set insert i^2

for i: 2 to n

dp[i] = min(dp[i - set] + 1 if dp[i - set] != 0)