Perfect Squares

题目
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

答案

class Solution {
    public int numSquares(int n) {
        // f[i]: numSquares(i)
        // think: how does f[i] depend on f[j], j < i?
        // f[i] = f[i - some perfect square]
        int[] f = new int[n + 1];
        f[0] = 0;
        for(int i = 1; i <= n; i++) {
            f[i] = Integer.MAX_VALUE;
            for(int j = 1; j*j <= n; j++) {
                if(i - j*j < 0) break;
                f[i] = Math.min(f[i], f[i - j*j] + 1);
            }
            //System.out.println(f[i]);
        }
        return f[n];
    }
}