279. Perfect Squares

https://leetcode.com/problems/perfect-squares/description/

解题思路：

1. 两个循环：核心是i + j * j <= n， 对dp[i + j * j]进行更新

代码：

class Solution {
public int numSquares(int n) {

    int[] dp = new int[n + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    for(int i = 0; i <= n; i++){
        for(int j = 1; i + j * j <= n; j++){
            dp[i+j*j] = Math.min(dp[i+j*j], dp[i] +1);
        }
    }
    return dp[n];
}

}