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

Une brique verticale occupe une seule colonne de hauteur 4, tandis qu’une brique horizontale occupe une seule ligne sur 4 colonnes. Comme la hauteur du mur est 4, poser des briques horizontalement impose d’en placer quatre en même temps pour couvrir complètement les 4 lignes.

Problème

Écrire un programme qui lit un entier N et affiche le nombre de façons de construire un mur de dimensions 4 × N à l’aide de briques 4 × 1.

Entrée

Une ligne contient un entier N.

Sortie

Afficher le nombre de façons de construire un mur de dimensions 4 × N.

Exemples

5

3

8

7

50

5453761

35

43371

Relation de récurrence

Notons nbFacons(N) le nombre de façons de construire un mur de dimensions 4 × N. En observant la dernière partie du mur, on obtient deux cas :

• si la dernière brique est verticale, il reste à construire un mur de taille 4 × (N - 1) ;
• si les dernières briques sont horizontales, il faut placer 4 briques horizontales, et il reste à construire un mur de taille 4 × (N - 4).

nbFacons(N) = 1                  si N < 4
nbFacons(N) = nbFacons(N-1) + nbFacons(N-4)    si N ≥ 4

Solution 1 : approche récursive

La solution la plus directe consiste à appliquer la relation de récurrence telle quelle. On calcule récursivement le nombre de façons de construire un mur plus petit jusqu’à atteindre un cas de base.

#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))

Pourquoi optimiser ?

Dans la solution récursive naïve, plusieurs appels récursifs demandent à nouveau le calcul des mêmes sous-problèmes. Par exemple, nbFacons(N-1) et nbFacons(N-4) peuvent eux-mêmes avoir besoin de nbFacons(N-5), etc.

Solution optimisée : programmation dynamique top-down

L’approche top-down consiste à conserver la structure récursive, mais à mémoriser les résultats déjà calculés dans un tableau DP. Ainsi, dès qu’un sous-problème a déjà été résolu, on renvoie immédiatement sa valeur sans recalcul.

#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;

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

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))

Solution optimisée : programmation dynamique bottom-up

L’approche bottom-up construit les résultats dans l’ordre croissant, depuis les plus petites valeurs jusqu’à N. Elle évite complètement la récursivité.

On commence par remplir les cas de base, puis on applique la relation :

$$ DP[i] = DP[i-1] + DP[i-4] \quad \text{pour } i \ge 4 $$

#include <iostream>
using namespace std;

int nbFacons(int N) {
    int DP[N + 1];

    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é