Le nombre de façons pour construire un mur de dimension 4*N - Programmation compétitive

Considérons un mur de taille 4 * N et des briques de taille  4 * 1 . Il faut compter le nombre de façons dont nous pouvons construire ce mur. Vous pouvez placer la brique verticalement ou horizontalement, selon votre choix.

Supposons que nous ayons un mur de dimension 4x5 (N=5), alors il y en a 3 façons pour construire le mur comme suit :

Entrée

Une ligne contient la dimension N

Sortie

Le nombre de façons pour construire le mur de dimension 4*N

  Exemples

Nous allons résoudre ce problème en utilisant la récursivité. Nous allons commencer à construire le mur à partir de la dernière colonne, c'est-à-dire; nous allons d'abord construire la Nième colonne, puis la (N-1)ième colonne, et ainsi de suite.

Il y a 2 cas possibles :

•  Si nous plaçons la brique verticalement, le problème sera converti en un sous-problème de construction d'un mur de taille 4 * (N - 1).
•  Si nous plaçons la brique horizontalement, 4 briques seront nécessaires pour couvrir les 4 dernières colonnes, et maintenant le problème sera converti en un sous-problème de construction d'un mur de taille 4 * (N - 4).

Ainsi, si nbFacons(N) dénote le nombre de façons de construire un mur de taille 4 * N, alors, $$ \begin{array}{CC} nbFacons(N)=1 & N\lt4 \\ nbFacons(N)=nbFacons(N-1)+nbFacons(N-4) & N\ge4 \end{array} $$

#include <iostream>
using namespace std;

int nbFacons(int N){
    if (N < 4)
        return 1;
 
    return nbFacons(N - 1) + nbFacons(N - 4);
}

int main()
{
    int n;
    cin >> n;
    cout << nbFacons(n) << endl;
    return 0;
}
                    

def nbFacons(N):
    if (N < 4):
        return 1
 
    return nbFacons(N - 1) + nbFacons(N - 4)

n=int(input(""))
print(nbFacons(n))
                    

Mais l'approche ci-dessus est une implémentation naïve. Nous pouvons optimiser la solution en utilisant une approche de programmation dynamique. Il est clairement visible que nous faisons des appels répétitifs au même sous-problème pour différentes valeurs de N. Cela finit par calculer encore et encore la solution au même sous-problème. En fin de compte, cela conduit à une très faible complexité temporelle et à un énorme arbre de récursivité.

Dans l'approche de programmation dynamique, nous stockons simplement la solution à ces sous-problèmes répétitifs à l'aide d'un vecteur. Et chaque fois que nous avons besoin de ces valeurs, nous y accédons dans une complexité temporelle constante.

#include <iostream>
#include <cstring>

using namespace std;

int DP[1000];

int nbFacons(int N){
    if(DP[N]>=0)
        return DP[N];

    if (N < 4)
        return 1;
    
    return DP[N]=nbFacons(N - 1) + nbFacons(N - 4);
}

int main()
{
    int n;
    cin >> n;
    memset(DP, -1, sizeof(DP));
    cout << nbFacons(n) << endl;
    
    return 0;
}
                    

def nbFacons(N):
    global DP

    if(DP[N]>=0):
        return DP[N]

    if (N < 4):
        return 1
    
    DP[N]=nbFacons(N - 1) + nbFacons(N - 4)
    return DP[N]

n=int(input(""))
DP=[-1 for _ in range(n+1)]

print(nbFacons(n))
                    

Cela implique le calcul de sous-problèmes plus petits pour calculer le résultat de sous-problèmes plus grands. Nous stockons les résultats des plus petits sous-problèmes dans un tableau DP et les utilisons pour calculer le résultat du plus grand sous-problème.

#include <iostream>
#include <cstring>

using namespace std;


int nbFacons(int N){
    int DP[N+1];
    memset(DP, -1, sizeof(DP));

    for(int i=0;i<=N;i++){
        if (i<4)
            DP[i]=1;
        else
            DP[i]=DP[i-1]+DP[i-4];
    }
    
    return DP[N];
}

int main()
{
    int n;
    cin >> n;
    
    cout << nbFacons(n) << endl;
    
    return 0;
}
                    

def nbFacons(N):
    DP=[-1 for _ in range(N+1)]
    for i in range(n+1):
        if (i<4):
            DP[i]=1
        else:
            DP[i]=DP[i-1]+DP[i-4]
    
    return DP[N]

n=int(input(""))

print(nbFacons(n))
                    

Complexité :

•  Complexité temporelle : Puisque nous utilisons DP pour stocker les résultats, chaque combinaison n'est calculée qu'une seule fois. Par conséquent, la complexité temporelle de cette approche est donnée par O(N).
•  Complexité spatiale : Puisque nous utilisons de l'espace supplémentaire pour stocker les résultats et éviter les recalculs, la complexité spatiale est donnée par O(N).