Definamos dp bidimensional,
int [matemáticas] dp [n + 1] [n + 1] [/ matemáticas]
Donde [math] dp [i] [j] [/ math] representa no. de manzana cuando estás en [math] i ^ {th} [/ math] farm y tu energía es [math] j [/ math] unit.
- ¿Qué sucede cuando hay un ciclo negativo en el gráfico?
- Cómo mostrar que la distancia más corta entre 2 curvas que no se cruzan siempre se encuentra a lo largo de su normal común
- ¿Qué algoritmo se debe usar para una tesis que tiene al menos tres desventajas que se pueden resolver?
- ¿Cuál es el algoritmo más preciso (sin usar un software) para predecir el número 21 basado en 20 números anteriores?
- ¿La programación se trata de definiciones de variables, para bucles, ifs y estructuras de datos?
Entonces, si tomamos manzana de la granja [math] i ^ {th} [/ math],
dp [i] [j-1] = max (dp [i] [j-1] ,, dp [i-1] [j] + manzana [i]) donde [matemáticas] 1 [/ matemáticas] [matemáticas] \ leq j \ leq n. [/ math]
si tomamos leche de la granja [math] i ^ {th} [/ math],
dp [i] [min (j + mil [i] -1, n)] = max (dp [i] [min (j + mil [i] -1, n)], dp [i-1] [j ]). [matemáticas] 1 \ leq j \ leq n. [/ matemáticas]
Nota: Si la energía es mayor que n, entonces simplemente podemos tomarla n porque en n unidades de energía podemos visitar toda la granja.
cuando la energía es cero, no podemos ir más allá, simplemente agregamos esto
dp [i] [0] = max (dp [i] [0], dp [i-1] [0])
Caso base:
Reemplace todos los elementos en la tabla con -1.
Inicialmente tenemos energía p y 0 manzana, entonces dp [0] [min (p, n)] = 0. si [matemática] p \ ge n [/ matemática] entonces tómela n como se explicó anteriormente.
Nuestra respuesta es max de dp [n] [j] [matemáticas] 0 \ leq j \ leq n. [/ Matemáticas]
Aquí está mi código java,
