Может кто-нибудь объяснить мне этот код

Question

// Dynamic Programming 
using System.IO; 
using System; 

class Program 
{ 
    static void Main() 
    { 
     Console.WriteLine("Hello, World!"); 
     int val = 12; 
     int[] table = new int[val+1]; 
     table[0] = 0; 

     for (int i=1; i<=val; i++){ 
      int maxsqrt = (int) Math.Sqrt(i); 
      int localmin = i; 
      for (int j=1; j<=maxsqrt; j++){ 
       if (table[i-j*j] < localmin) { 
        localmin = table[i-j*j]; 
       } 
      } 
      table[i] = localmin + 1; 
    } 

     Console.WriteLine("Min Val:"+ table[val]); 
    } 
} 

Я нашел это решение в режиме онлайн для следующей задачи:

Учитывая ряд «п», найти наименьшее число безупречного квадратных чисел суммы, необходимой для получения «п»

Пример: n = 12, возврат 3 (4 + 4 + 4) = (2^2 + 2^2 + 2^2) NOT (3^2 + 1 + 1 + 1) n = 6, return 3 (4 + 1 + 1) = (2^2 + 1^2 + 1^2)

Я не могу понять код.

Answer 1

Обнаружили еще более простой способ решить эту проблему:

import java.util.*; 

class Program2{ 
    int[] min; 

    Program2(){ 
     min = new int[13]; 
     Arrays.fill(min, Integer.MAX_VALUE); 
    } 
    public void findMin(int n){ 
     min[0] = 0; 
     for(int i=1 ; i<=n ; i++){ 
      for(int j=1 ; j*j<=i ; j++){ 
       min[i] = Math.min(min[i], min[i - j*j] + 1); 
      } 
     } 
    } 

    public static void main(String[] args){ 
     Program2 obj = new Program2(); 

     obj.findMin(12); 
     System.out.println("Min Value: " + obj.min[12]); 
    } 
} 

Answer 2

Это в основном эффективное выполнение рекурсивного решения:

f(x) = min{ f(x-1^2), f(x-2^2) , ..., f(x-floor(sqrt(x))^2) } + 1 

который в основном скотина решение силы проблемы