Programmation dynamique LeetCode Day, partie 1

509. Nombre de Fibonacci

Les nombres de Fibonacci, communément notés F(n) forment une séquence, appelée séquence de Fibonacci, telle que chaque nombre est la somme des deux précédents, en partant de 0 et 1. Autrement dit,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), pour n > 1.
Étant donné n, calculez F(n).

Exemple 1 :

Entrée : n = 2
Sortie : 1
Explication : F(2) = F(1) + F(0) = 1 + 0 = 1.
Exemple 2 :

Entrée : n = 3
Sortie : 2
Explication : F(3) = F(2) + F(1) = 1 + 1 = 2.
Exemple 3 :

Entrée : n = 4
Sortie : 3
Explication : F(4) = F(3) + F(2) = 2 + 1 = 3.

Contraintes :

0 <= n <= 30
Page originale

Méthode de récursion

    public int fib(int n) {
        if(n==0){
            return 0;
        }     
        else if(n==1){
            return 1;
        }   
        else{
            return fib(n-1) + fib(n-2);
        }
    }

La méthode de récursion est comme DFS pour aller en profondeur puis faire le retour en arrière pour obtenir la réponse finale.
temps : O(2^n)
espace : O(1)

    private int[] dp = new int[31];
    public int fib(int n) {
        if(n<2){
            dp[n] = n;
            return n;
        }  

        if(n>=2 && dp[n]!=0){
            return dp[n];
        }

        dp[n] = fib(n-1) + fib(n-2);
        return dp[n];
    }




</p>
<p>nous pouvons utiliser un tableau global pour enregistrer le résultat afin d'éviter la récursion des mêmes éléments. par ex. la figure ci-dessous montre que f(17) et f(18) sont deux routes de récursion différentes et si nous utilisons la méthode de récursion normale, nous devons les calculer plus d'une fois. </p>

<p><img src="https://img.php.cn/upload/article/000/000/000/172127798860260.png" alt="Image description" loading="lazy"    style="max-width:90%"  style="max-width:90%"></p>

<p>temps : O(n), espace : O(n)</p>

<h2>
  
  
  Programmation dynamique
</h2>



<pre class="brush:php;toolbar:false">    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

La récursivité fonctionne de haut en bas puis en retour en arrière, la récursion mémoire sauvegardera les résultats de récursion pour éviter le double calcul. Désormais, la programmation dynamique fonctionne de bas en haut et enregistre le résultat de chaque étape dans le tableau dp.
heure : O(n)
espace : O(n)

Nous pouvons également mettre à jour dynamiquement le nombre limite au lieu d'un tableau. Cela permettra d'économiser de l'espace, en particulier pour un grand nombre d'éléments.

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int start = 0;
        int pre = 1;
        int res = pre;

        for(int i=2; i<=n; i++){
            res = start + pre;
            start = pre;
            pre = res;
        }
        return res;
    }

70. Monter les escaliers

Vous montez un escalier. Il faut n étapes pour atteindre le sommet.

À chaque fois, vous pouvez monter 1 ou 2 marches. De combien de manières distinctes pouvez-vous grimper jusqu'au sommet ?

Exemple 1 :

Entrée : n = 2
Sortie : 2
Explication : Il existe deux façons de grimper jusqu'au sommet.

1. 1 étape + 1 étape
2. 2 étapes Exemple 2 :

Entrée : n = 3
Sortie : 3
Explication : Il existe trois façons de grimper jusqu'au sommet.

1. 1 étape + 1 étape + 1 étape
2. 1 étape + 2 étapes
3. 2 étapes + 1 étape

70. Monter les escaliers

Vous montez un escalier. Il faut n étapes pour atteindre le sommet.

À chaque fois, vous pouvez monter 1 ou 2 marches. De combien de manières distinctes pouvez-vous grimper jusqu'au sommet ?

Exemple 1 :

Entrée : n = 2
Sortie : 2
Explication : Il existe deux façons de grimper jusqu'au sommet.

1. 1 étape + 1 étape
2. 2 étapes Exemple 2 :

Entrée : n = 3
Sortie : 3
Explication : Il existe trois façons de grimper jusqu'au sommet.

1. 1 étape + 1 étape + 1 étape
2. 1 étape + 2 étapes
3. 2 étapes + 1 étape

Contraintes :

1 <= n <= 45
Page originale

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;
        for(int i=3; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        } 
        return dp[n];       
    }

    public int climbStairs(int n) {
        if(n<3){
            return n;
        }

        int prepre = 1;
        int pre = 2;
        int res = 0;
        for(int i=3; i<=n; i++){
            res = prepre + pre;
            prepre = pre;
            pre = res;
        } 
        return res;       
    }

746. Monter les escaliers à coût minimum

Vous recevez un coût de tableau entier où cost[i] est le coût de la ième marche d'un escalier. Une fois le prix payé, vous pouvez monter une ou deux marches.

Vous pouvez soit partir de l'étape d'index 0, soit de l'étape d'index 1.

Renvoyer le coût minimum pour atteindre le sommet de l'étage.

Exemple 1 :

Entrée : coût = [10,15,20]
Sortie : 15
Explication : Vous commencerez à l'index 1.

• Payez 15 et montez deux marches pour atteindre le sommet. Le coût total est de 15. Exemple 2 :

Entrée : coût = [1 100,1,1,1 100,1,1 100,1]
Sortie : 6
Explication : Vous commencerez à l'index 0.

• Payez 1 et montez deux marches pour atteindre l'indice 2.
• Payez 1 et montez deux marches pour atteindre l'indice 4.
• Payez 1 et montez deux marches pour atteindre l'indice 6.
• Payez 1 et montez une marche pour atteindre l'indice 7.
• Payez 1 et montez deux marches pour atteindre l'indice 9.
• Payez 1 et montez une marche pour atteindre le sommet. Le coût total est de 6.

Contraintes :

2 <= coût.longueur <= 1000
0 <= coût[i] <= 999
Page originale

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length < 2){
            return 0;
        }

        int[] dp = new int[cost.length+1];
        dp[0] = 0;
        dp[1] = 0;

        for(int i=2; i<dp.length; i++){
            dp[i] = Math.min(dp[i-1]+cost[i-1], dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];

    }
the key thing of this problem is the `init array` and `the meaning of the array` and the `Recurrence relation`

Attention, la question nous a dit que nous pouvons partir de l'indice 0 et de l'indice 1, ce qui implique que si le nombre d'escaliers est inférieur à 2, nous coûterons 0 car nous pouvons commencer à ce point et le comportement de démarrage sera coût 0, uniquement le comportement du coût de déplacement.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!