Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Example 1:
Input: n =12Output: 3 Explanation:12 = 4 + 4 + 4.
Example 2:
Input: n =13Output: 2 Explanation:13 = 4 + 9.
public static int numSquares(int n) { int[] dp = new int[n+1]; for(int i = 1; i <= n ;i++) dp[i] = Integer.MAX_VALUE; for(int i = 0; i <= n; i++) for(int j = 1 ;i+j*j <= n;j++) dp[i+j*j]= dp[i+j*j]>dp[i]+1 ? dp[i]+1 : dp[i+j*j]; return dp[n]; }
原文：https://www.cnblogs.com/tiandiou/p/9693560.html