Leetcode 279. Carré parfait carré complet (moyen)

Un.、Objet

Étiquettes: Planification dynamique

https://leetcode.cn/problems/perfect-squares

Pour vous donner un entier n ,Retour Et pour n Le nombre minimum de carrés complets de .

Nombre carré complet Est un entier,Sa valeur est égale au carré d'un autre entier;En d'autres termes,,Sa valeur est égale au produit d'un entier auto - multiplié.Par exemple,1、4、9 Et 16 Ce sont des carrés complets,Et 3 Et 11 Non, pas du tout..

Exemple 1：

Entrée：n = 12Produits：3Explication：12 = 4 + 4 + 4

Exemple 2：

Entrée：n = 13Produits：2Explication：13 = 4 + 9

Conseils：

1 <= n <= 104

2.、Comment résoudre le problème

Planification dynamique,dp[i]ReprésentationiIl y a plusieurs additions de nombres carrés complets,Taux d'énumérationiPetit carré complet,L'équation de transfert d'état estdp[i] = min(dp[i-k] + 1) ,kC'est le carré complet

Trois、Comment résoudre le problème

3.1 JavaRéalisation

class Solution {
 public int numSquares(int n) {
 // Trouver moins quenLe carré complet de
 List<Integer> squares = new ArrayList<>();
 for (int i = 1; i < n + 1; i++) {
 int tmp = i * i;
 if (tmp < n + 1) {
 squares.add(tmp);
 } else {
 break;
 }
 }

 int[] dp = new int[n + 1];
 for (int i = 1; i < n + 1; i++) {
 dp[i] = Integer.MAX_VALUE;
 }
 for (int i = 1; i < n + 1; i++) {
 for (int square : squares) {
 if (i < square) {
 break;
 }
 dp[i] = Math.min(dp[i], dp[i - square] + 1);
 }
 }

 return dp[n];
 }
}


Quatre、Résumé des notes

• 2022/6/21  Une fois par jour leetcode,Prenez l'habitude