Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.
Given n = 12, return 3 because 12 = 4 + 4 + 4
Given n = 13, return 2 because 13 = 4 + 9
分析：
首先把所有 1-n 的square numbers找出来。然后利用DP去求。Assume count[j] is the least number of perfect square numbers which sum to j.
count[j] = Math.min(count[j - list.get(k)] + 1, count[j]);
Here list contains all the square numbers from 1 to n, and 1 <= list.get(k) <= j
1 public class Solution { 2 /** 3 * @param n a positive integer 4 * @return an integer 5 */ 6 public int numSquares(int n) { 7 ArrayList<Integer> list = new ArrayList<Integer>(); 8 int i = 1; 9 while (i * i <= n) { 10 list.add(i * i); 11 i++; 12 } 13 int[] count = new int[n + 1]; 14 count[0] = 0; 15 16 for (int j = 1; j <= n; j++) { 17 count[j] = Integer.MAX_VALUE; 18 for (int k = 0; k < list.size(); k++) { 19 if (list.get(k) <= j) { 20 if (count[j] > count[j - list.get(k)] + 1) { 21 count[j] = count[j - list.get(k)] + 1; 22 } 23 } else { 24 break; 25 } 26 } 27 } 28 return count[n]; 29 } 30 }
原文：http://www.cnblogs.com/beiyeqingteng/p/5662188.html