(UVA) Squares - Solution

Link to the problem: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=655&page=show_problem&problem=2402

The solution below used Dynamic Programming to solve this problem.


import java.io.*;
import java.util.*;

class Main {
    public int number;
    public int minTerms;
    public int[] array;
   
    public int rec(int num) {
        if (num < 0) {
            return 10000000;
        }
       
        if (num == 0) {
            return 0;
        }
       
        if (array[num] != -1) {
            return array[num];
        }
       
        int min = 10000000;
        for (int i = 1; i*i <= num; i++) {
            min = Math.min(min, rec(num-i*i)+1);
        }
        array[num] = min;
       
        return min;
    }
   
    public void process() throws NumberFormatException, IOException {
        Scanner sc = new Scanner(System.in);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        array = new int[10001];
        Arrays.fill(array, -1);
        for (int i = 0; i < 10001; i++) {
            rec(i);
        }
       
        int numTests = sc.nextInt();
        for (int i = 0; i < numTests; i++) {
            number = sc.nextInt();
            minTerms = rec(number);
           
            bw.write(minTerms+"\n");
        }
                                      
        bw.flush();
        bw.close();
       
        return;
    }
   
    public static void main(String[] args) throws NumberFormatException, IOException {
        Main m = new Main();
        m.process();
       
        System.exit(0);
    }
}