Número mínimo de cuadrados cuya suma es igual al número dado N | conjunto 2

Un número siempre se puede representar como una suma de cuadrados de otros números. Tenga en cuenta que 1 es un cuadrado, y siempre podemos dividir un número como (1*1 + 1*1 + 1*1 + …) . Dado un número N , la tarea es representar N como la suma de números cuadrados mínimos.

Ejemplos:  

Entrada: 10 
Salida: 1 + 9 
Estas son todas las formas posibles 
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 
1 + 1 + 1 + 1 + 1 + 1 + 4 
1 + 1 + 4 + 4 
1 + 9 
Elija uno con números mínimos

Entrada : 25 
Salida : 25 

Prerrequisitos: Número mínimo de cuadrados cuya suma sea igual al número dado N
Enfoque: Esta es una aplicación típica de programación dinámica . Cuando partimos de N = 6, podemos llegar a 2 restando el cuadrado de uno, es decir, 4 veces, y restando el cuadrado de dos, es decir, cuatro, 1 vez. Entonces, el subproblema para 2 se llama dos veces. 
Dado que se vuelven a llamar los mismos subproblemas, este problema tiene la propiedad Superposición de subproblemas. El problema de suma cuadrada so-min tiene las dos propiedades (ver this y this ) de un problema de programación dinámica. Al igual que otros problemas típicos de Programación Dinámica (DP), el recálculo de los mismos subproblemas se puede evitar mediante la construcción de una tabla de array temporal[][]de forma ascendente. 
A continuación se muestra la implementación del enfoque anterior: 

// C++ program to represent N as the
// sum of minimum square numbers.
#include <bits/stdc++.h>
using namespace std;
 
// Function for finding
// minimum square numbers
vector<int> minSqrNum(int n)
{
  // A[i] of array arr store
  // minimum count of
  // square number to get i
  int arr[n + 1], k;
 
  // sqrNum[i] store last
  // square number to get i
  int sqrNum[n + 1];
  vector<int> v;
 
  // Initialize
  arr[0] = 0;
  sqrNum[0] = 0;
 
  // Find minimum count of
  // square number for
  // all value 1 to n
  for (int i = 1; i <= n; i++)
  {
    // In worst case it will
    // be arr[i-1]+1 we use all
    // combination of a[i-1] and add 1
    arr[i] = arr[i - 1] + 1;
    sqrNum[i] = 1;
 
    k = 1;
    // Check for all square
    // number less or equal to i
    while (k * k <= i)
    {
      // if it gives less
      // count then update it
      if (arr[i] > arr[i - k * k] + 1)
      {
        arr[i] = arr[i - k * k] + 1;
        sqrNum[i] = k * k;
      }
      k++;
    }
  }
 
  // Vector v stores optimum
  // square number whose sum give N
  while (n > 0)
  {
    v.push_back(sqrNum[n]);
    n -= sqrNum[n];
  }
  return v;
}
 
// Driver code
int main()
{
  int n = 10;
 
  vector<int> v;
 
  // Calling function
  v = minSqrNum(n);
 
  // Printing vector
  for (auto i = v.begin();
            i != v.end(); i++)
  {
    cout << *i;
    if (i + 1 != v.end())
      cout << " + ";
  }
  return 0;
}

// Java program to represent
// N as the sum of minimum
// square numbers.
import java.util.*;
class GFG{
 
// Function for finding
// minimum square numbers
static Vector<Integer> minSqrNum(int n)
{
  // A[i] of array arr store
  // minimum count of
  // square number to get i
  int []arr = new int[n + 1];
  int k = 0;
 
  // sqrNum[i] store last
  // square number to get i
  int []sqrNum = new int[n + 1];
  Vector<Integer> v = new Vector<>();
 
  // Initialize
  arr[0] = 0;
  sqrNum[0] = 0;
 
  // Find minimum count of
  // square number for
  // all value 1 to n
  for (int i = 1; i <= n; i++)
  {
    // In worst case it will
    // be arr[i-1]+1 we use all
    // combination of a[i-1] and add 1
    arr[i] = arr[i - 1] + 1;
    sqrNum[i] = 1;
 
    k = 1;
    // Check for all square
    // number less or equal to i
    while (k * k <= i)
    {
      // if it gives less
      // count then update it
      if (arr[i] > arr[i - k * k] + 1)
      {
        arr[i] = arr[i - k * k] + 1;
        sqrNum[i] = k * k;
      }
      k++;
    }
  }
 
  // Vector v stores optimum
  // square number whose sum give N
  while (n > 0)
  {
    v.add(sqrNum[n]);
    n -= sqrNum[n];
  }
  return v;
}
 
// Driver code
public static void main(String[] args)
{
  int n = 10;
 
  Vector<Integer> v;
 
  // Calling function
  v = minSqrNum(n);
 
  // Printing vector
  for (int i = 0; i <v.size(); i++)
  {
    System.out.print(v.elementAt(i));
    if (i+1 != v.size())
      System.out.print(" + ");
  }
}
}
 
// This code is contributed by gauravrajput1

# Python3 program to represent N as the
# sum of minimum square numbers.
 
# Function for finding
# minimum square numbers
def minSqrNum(n):
 
    # arr[i] of array arr store
    # minimum count of
    # square number to get i
    arr = [0] * (n + 1)
     
    # sqrNum[i] store last
    # square number to get i
    sqrNum = [0] * (n + 1)
    v = []
 
    # Find minimum count of
    # square number for
    # all value 1 to n
    for i in range(n + 1):
         
        # In worst case it will
        # be arr[i-1]+1 we use all
        # combination of a[i-1] and add 1
        arr[i] = arr[i - 1] + 1
        sqrNum[i] = 1
 
        k = 1;
         
        # Check for all square
        # number less or equal to i
        while (k * k <= i):
             
            # If it gives less
            # count then update it
            if (arr[i] > arr[i - k * k] + 1):
                arr[i] = arr[i - k * k] + 1
                sqrNum[i] = k * k
 
            k += 1
 
    # v stores optimum
    # square number whose sum give N
    while (n > 0):
        v.append(sqrNum[n])
        n -= sqrNum[n];
         
    return v
 
# Driver code
n = 10
 
# Calling function
v = minSqrNum(n)
 
# Printing vector
for i in range(len(v)):
    print(v[i], end = "")
     
    if (i < len(v) - 1):
        print(" + ", end = "")
         
# This article is contributed by Apurvaraj

// C# program to represent
// N as the sum of minimum
// square numbers.
using System;
using System.Collections.Generic;
class GFG{
 
// Function for finding
// minimum square numbers
static List<int> minSqrNum(int n)
{
  // A[i] of array arr store
  // minimum count of
  // square number to get i
  int []arr = new int[n + 1];
  int k = 0;
 
  // sqrNum[i] store last
  // square number to get i
  int []sqrNum = new int[n + 1];
  List<int> v = new List<int>();
 
  // Initialize
  arr[0] = 0;
  sqrNum[0] = 0;
 
  // Find minimum count of
  // square number for
  // all value 1 to n
  for (int i = 1; i <= n; i++)
  {
    // In worst case it will
    // be arr[i-1]+1 we use all
    // combination of a[i-1] and add 1
    arr[i] = arr[i - 1] + 1;
    sqrNum[i] = 1;
 
    k = 1;
    // Check for all square
    // number less or equal to i
    while (k * k <= i)
    {
      // if it gives less
      // count then update it
      if (arr[i] > arr[i - k * k] + 1)
      {
        arr[i] = arr[i - k * k] + 1;
        sqrNum[i] = k * k;
      }
      k++;
    }
  }
 
  // List v stores optimum
  // square number whose sum give N
  while (n > 0)
  {
    v.Add(sqrNum[n]);
    n -= sqrNum[n];
  }
  return v;
}
 
// Driver code
public static void Main(String[] args)
{
  int n = 10;
 
  List<int> v;
 
  // Calling function
  v = minSqrNum(n);
 
  // Printing vector
  for (int i = 0; i <v.Count; i++)
  {
    Console.Write(v[i]);
    if (i+1 != v.Count)
      Console.Write(" + ");
  }
}
}
 
// This code is contributed by gauravrajput1

<script>
 
// Javascript program to represent N as the
// sum of minimum square numbers.
 
// Function for finding
// minimum square numbers
function minSqrNum(n)
{
  // A[i] of array arr store
  // minimum count of
  // square number to get i
  var arr = Array(n+1), k;
 
  // sqrNum[i] store last
  // square number to get i
  var sqrNum = Array(n+1);
  var v = [];
 
  // Initialize
  arr[0] = 0;
  sqrNum[0] = 0;
 
  // Find minimum count of
  // square number for
  // all value 1 to n
  for (var i = 1; i <= n; i++)
  {
    // In worst case it will
    // be arr[i-1]+1 we use all
    // combination of a[i-1] and add 1
    arr[i] = arr[i - 1] + 1;
    sqrNum[i] = 1;
 
    k = 1;
    // Check for all square
    // number less or equal to i
    while (k * k <= i)
    {
      // if it gives less
      // count then update it
      if (arr[i] > arr[i - k * k] + 1)
      {
        arr[i] = arr[i - k * k] + 1;
        sqrNum[i] = k * k;
      }
      k++;
    }
  }
 
  // Vector v stores optimum
  // square number whose sum give N
  while (n > 0)
  {
    v.push(sqrNum[n]);
    n -= sqrNum[n];
  }
  return v;
}
 
// Driver code
var n = 10;
var v = [];
// Calling function
v = minSqrNum(n);
// Printing vector
for(var i = 0; i<v.length; i++)
{
    document.write(v[i]);
  if (i + 1 != v.length)
    document.write( " + ");
}
 
 
</script>

1 + 9

Complejidad del tiempo: O(n ^3/2 )

Espacio Auxiliar: O(n)