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`

.
Credits:

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

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

**Understand the problem:**

This is a DP problem.

-- Define dp[n + 1], where dp[i] means the least number of perfect square numbers for integer i.

-- Initialization. dp[0] = 0. dp[i] = Integer.MAX_VALUE since we calculate the min number

-- Transit function, dp[i] = min(dp[i], dp[i - j * j]), where j * j <= i

-- Final state: dp[n]

**Code (Java):**

public class Solution { public int numSquares(int n) { if (n <= 0) { return 0; } int[] dp = new int[n + 1]; for (int i = 1; i <= n; i++) { dp[i] = Integer.MAX_VALUE; for (int j = 1; j * j <= i; j++) { dp[i] = Math.min(dp[i], dp[i - j * j] + 1); } } return dp[n]; } }

## No comments:

## Post a Comment