package com.algorithm.dynamicprogramming;

/**
 * 算法描述：给定一个正整数n，求和为n的最小个数完美平方数（例如，1，4，9，16，…）。 
 * Example 1:
 * Input: n = 12
 * Output: 3 Explanation: 12 = 4 + 4 + 4. 
 * 
 * Example 2:
 * Input: n = 13
 * Output: 2 Explanation: 13 = 4 + 9.
 * @author rich
 *
 */
public class PerfectSquares {

    public static void main(String[] args) {
        System.out.println(perfectSquares(4));
    }
    /**
     * 算法分析：当 
     * n = 1 1
     * n = 2 1+1 
     * n = 3 1+1+1 
     * n = 4 1+1+1+1 
     * n = 5 1+4 
     * n = 6 1+1+4 
     * n = 7 1+1+1+4
     * n = 8 4+4
     * n = 9 1+4+4
     * n = 10 1+1+4+4
     * n = 11 1+1+1+4
     * n = 12 4+4+4
     * n = 13 4+9
     * @param n
     * @return
     */
    public static int perfectSquares(int n) {
        int[] memo = new int[n+1];
        if (n == 1) return 1;
        memo[0] = 0;
        memo[1] = 1;
        for (int i = 2;i<=n;i++) {
            memo[i] = i;
            for (int j = 1;j*j <= i;j++) {
                memo[i] = Math.min(memo[i], memo[i-j*j]+1);
            }
        }
        return memo[n];
    }
}