leetcode Perfect Squares

279. 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.

For example, given n = 

12

, return 

3

 because 

12 = 4 + 4 + 4

; given n = 

13

, return 

2

 because 

13 = 4 + 9

.

import java.util.Arrays;

public class Solution {

public static int numSquares(int n) {

        int[] num = new int[n+1];

        Arrays.fill(num, 10);

        for(int i=1;i*i<=n;i++){

        num[i*i] = 1;

        }

        for(int i=0;i<n;i++){

        for(int j=1;i+j*j<=n;j++){

        num[i+j*j] = Math.min(num[i]+1,num[i+j*j]);

        }

        }

        return num[n];

    }

    public static void main(String args[]){

        Scanner reader = new Scanner(System.in);

        try{

            int n = reader.nextInt();

            if(n>0){

                System.out.print(numSquares(n));

            }

        }catch(Exception e){

            System.out.print("WRONG");

        }

    }

}