1259. Programmation dynamique de poignée de main disjointe

1259. Poignée de main disjointe 

Nombre pair L'homme se tient dans un cercle,Nombre total de personnes num_people .Tout le monde serre la main de quelqu'un d'autre que lui,Donc au total, il y aura num_people / 2 Poignée de main secondaire.

Connectez les gens qui se serrent la main,Veuillez retourner le nombre de schémas de poignée de main où les connexions ne se croisent pas.

Comme les résultats peuvent être importants,Veuillez retourner à la réponse Module 10^9+7 Après les résultats.

Exemple 1：

Entrée：num_people = 2
Produits：1

Exemple 2：

Entrée：num_people = 4
Produits：2
Explication：Il y a deux options au total,La première option est [(1,2),(3,4)] ,La deuxième option est [(2,3),(4,1)] .

Exemple 3：

Entrée：num_people = 6
Produits：5

Exemple 4：

Entrée：num_people = 8
Produits：14

Conseils：

• 2 <= num_people <= 1000
• num_people % 2 == 0

Résultats des questions

Succès, Cette question est probablement particulièrement simple dans les questions difficiles

Méthodes：Planification dynamique

1. Supposons qu'il y ait x Particuliers, On a choisi l'un d'eux a,C'est a Serrer la main d'un homme , Pour assurer une solution ultérieure , Les deux parties séparées doivent être égales
2. a Après la poignée de main ,Il en reste.,x-2 Personne ne serre la main ,x Après la poignée de main , Diviser le reste du personnel en deux parties par une ligne de poignée de main , Supposons qu'une partie soit y Particuliers, Le reste est x-2-y Particuliers
3. C'est y Problème de poignée de main , Juste pour x Sous - question de la poignée de main ,Enumeration Tout ce qui est possible y Et x-2-y Possibilité de poignée de main , Les deux n'interfèrent pas , Traitement multiplicatif

Optimisation

1. Parce que c'est un nombre pair , Tout ce qui compte, c'est le nombre de paires de mains , L'espace peut être réduit à n/2
2. Un côté est divisé en y Les gens, Un côté est divisé en x-2-y Les gens, Même résultat que l'inverse , Alors, pour les deux nombres différents ,Peut être multiplié par2, Cela réduit de moitié le nombre de cycles ,En particulier,,Quand y=x-2-yHeure,Il n'y a qu'une seule possibilité.,

class Solution {
        public int numberOfWays(int numPeople) {
            int half = numPeople/2;
            long[] dp = new long[half+1];
            long MOD = (long) (1e9+7);
            dp[0]=1;
            for(int i = 1; i <= half; i++){
                for(int j = 0; j < i-j-1; j++){
                    dp[i]+=dp[j]*dp[i-j-1]*2;
                    dp[i] = dp[i]%MOD;
                }

                if(i%2!=0){
                    dp[i]+=dp[i/2]*dp[i-i/2-1];
                    dp[i] = dp[i]%MOD;
                }
            }
            return (int) dp[half];
        }
    }

Complexité temporelle：O(n)
Complexité spatiale：O(n)