moins nombre de numéros carrés parfaits qui résume jusqu'à n

Question

La question est:

Etant donné un entier positif n, trouver le plus petit nombre de nombres carrés parfaits (par exemple, 1, 4, 9, 16,. ..) qui somme à n. Link à la question

Exemple

Étant donné n = 12, 3 revenir parce que 12 = 4 + 4 + 4; donné n = 13, retour 2 car 13 = 4 + 9.

NOTE

L'approche que j'ai pris est similaire à un problème entier avec doublons Knapsack permis. J'ai d'abord calculé tous les carrés parfaits qui sont inférieurs au nombre n. Maintenant, une fois que je les ai, le problème est similaire au problème Integer Knapsack. J'ai un numéro n et une liste de nombres. je veux choisir le nombre minimum de nombres de la liste telle que leur somme soit égale à n. Ce problème a une solution DP que j'ai utilisée. Sur les 586 cas de test, j'ai passé 562 cas de test et j'ai obtenu TLE sur le suivant. La valeur de n pour que TESTCASE 3428.

La solution i soumettais:

class Solution(object): 
    def numSquares(self,n): 
     if(n == 0): 
      return 0 
     if(n == 1): 
      return 1 
     squares = self.findSquares(n) # returns a list of perfect squares <= n 
     rows = len(squares) 
     cols = n + 1 
     mat = [] 
     for i in range(rows): 
      mat.append([0] * cols) 

     for i in range(cols): 
      mat[0][i] = i 

     for i in range(rows): 
      mat[i][0] = 0 

     min = mat[0][cols - 1] 
     for i in range(1,rows): 
      for j in range(1,cols): 
       if(j < squares[i]): 
        mat[i][j] = mat[i - 1][j] 

       else: 
        mat[i][j] = self.min(mat[i - 1][j], (j // squares[i] + (mat[i][j % squares[i]]))) 
       if(j == cols - 1 and mat[i][j] < min): 
        min = mat[i][j] 
     ''' 
     for i in range(rows): 
      for j in range(cols): 
       print(mat[i][j],end=" ") 
      print() 
      ''' 
     return min 

    def min(self,a,b): 
     if(a <= b): 
      return a 
     else: 
      return b 


    def findSquares(self,n): 

     i = 1 
     squares = [] 
     while (i * i <= n): 
      squares.append(i * i) 
      i = i + 1 
     return squares 
''' 
x = Solution() 

print(x.numSquares(43)) 
''' 

Merci à l'avance.

Answer 1

Vous pouvez simplifier votre solution:

def numSquares(self,n): 
    if(n == 0): 
     return 0 
    if(n == 1): 
     return 1 
    squares = self.findSquares(n) 
    rows = len(squares) 
    cols = n + 1 
    mat = [n] * cols 
    mat[0] = 0 

    for s in squares: 
     for j in range(s,cols): 
      mat[j] = min(mat[j], 1 + mat[j - s]) 

    return mat[n] 

On évite ainsi l'utilisation:

1. la fonction self.min
2. la division/opération module dans la boucle interne.
3. le tableau 2d

et est à peu près deux fois plus vite.