Aprile 2025: con matrice 3×3 e regole di produzione (escludi quelle illegali).
Febbraio 2026: due vettori, uno per le stringhe che terminano con 0 e uno con non.
Gennaio 2026: tre vettori per le stringhe che terminano in 0, 1, 2.
Giugno 2025: matrice tre per tre.
Luglio 2025: È Il più difficile e usa questa relazione per le celle della matrice di dimensioni (stringa+1)×(sottostringa+1): numero modi in cui sottostringa appare in stringa = numero modi in cui sottostringa appare in “stringa senza ultimo carattere” + numero modi in cui sottostringa appare in “stringa con ultimo carattere”. L’ultimo addendo è uguale a numero di modi in cui sottostringa senza ultimo carattere appare in stringa senza ultimo carattere se gli ultimi caratteri delle due sono uguali, altrimenti è 0.
Ottobre 2025: la soluzione si può trovare in O(n), mantenendo due array, una per il numero di sotto-sequenze pari con i elementi e l’altra per le dispari. A ogni avanzamento di i si calcolano gli scenari con l’aggiunta (o meno) dell’elemento A[i−1] sia alle sotto-sequenze pari che a quelle dispari, ma esse si aggiornano in modo diverso in base alla parità di A[i−1]. Attenzione al primo caso base che è l’insieme vuoto: per questo l’array pari e quello dispari sono lunghi len(A)+1.
>>> def es2(A):... P = [0] * (len(A)+1)... D = [0] * (len(A)+1)... P[0] = 1... P[1] = 2 if A[0]%2==0 else 1... D[1] = 1 if A[0]%2==1 else 0... for i in range(2, len(A)+1):... if A[i-1]%2:... P[i] = P[i-1]+P[i-2]... D[i] = D[i-1]+D[i-2]... else:... P[i] = P[i-1]+D[i-2]... D[i] = D[i-1]+P[i-2]... return P[len(A)]...>>> es2([1, 2, 5, 4, 6])7
Settembre 2025: classica programmazione dinamica con array.
Aprile 2025: numero di variazioni passato come argomento da confrontare.
Febbraio 2026: backtracking standard.
Gennaio 2026: backtracking standard.
Giugno 2025: il numero di uni consecutivi (passato in argomento) si resetta quando si aggiunge uno zero nella stringa e aumenta di 1 (fino a k) quando si aggiunge un 1.
Luglio 2025: ogni chiamata fa progredire gli indici i e j della matrice riga per riga, è utile definire una funzione next(i, j, lato). Si stampa la matrice quando i == n, cioè quando i è nel primo stato illegale (prima cella della riga inesistente dopo l’ultima della matrice).
Ottobre 2025: backtracking standard (stai attento all’ultimo carattere)
