dp
con dp[0] = 1
, ya que hay exactamente 1 forma de sumar 0: no hacer ninguna tirada.dp
se utiliza como "memo" para almacenar los resultados de subproblemas ya resueltos.dp[i]
para cada valor de i
desde 1
hasta n
, siguiendo la relación de recurrencia. Esto asegura que cada subproblema (suma menor que n
) sea resuelto antes de resolver el subproblema final dp[n]
.10^9 + 7
después de cada operación de suma para evitar desbordamientos y cumplir con las restricciones del problema.dp[n]
contiene la cantidad de formas de obtener la suma n
y se imprime como la solución final. vector<unsigned long long> dp(1e6+1); // también suelen llamar a este vector "memo"
int n;
cin >> n;
dp[0] = 1; // Base del DP: hay una manera de sumar 0 (no hacer nada)
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 6; ++j) {
if (i - j >= 0) dp[i] += dp[i - j];
}
dp[i] %= 1e9+7; // El problema pide imprimir con módulo 10^9+7
}
cout << dp[n];// O(n) tiempo & espacio
Que corran el codigo para n = 20
Dibujar el arbol fibonacci de arriba hacia abajo
La solucion del de meta es que dado A + B = C, en el que A, B, C son números primos.Entonces B sólo pueden ser números pares, ya que la resta de dos números primos siempre será un número par. B = 2