Encuentra la fuerza mínima que Mustafa debe tener al principio para cruzar N celdas (Pregunta de entrevista).
Esta pregunta fue planteada en una ronda de codificación de una empresa en la que, desafortunadamente, no pude resolverla. Me doy cuenta de que esta pregunta se basa en la codicia, pero no puedo seguir adelante. Si alguien tiene la solución o un algoritmo, por favor compártalo conmigo.
Declaración del problema:
Mustafa quiere cruzar un calabozo. El calabozo tiene N celdas y en cada celda hay M monstruos. Para cruzar cada celda, debe matar a un monstruo. Al matar al monstruo, pierde la fuerza igual a la del monstruo y gana algo de confianza que se suma a su fuerza y continúa hacia la siguiente celda. Mustafa solo puede matar a un monstruo si su fuerza es mayor o igual a la del monstruo. Ayúdalo a encontrar la fuerza mínima que debe tener al principio para poder cruzar N celdas.
Formato de entrada:
- Los primeros dos enteros son N y M.
- Una matriz N X M que representa la energía requerida para matar a los monstruos en cada celda.
- Una matriz N X M que representa la confianza obtenida al matar a los respectivos monstruos.
Caso de prueba:
Entrada:
3 3
3 2 5
8 9 1
4 7 6
1 1 1
1 1 1
1 1 1
Salida:
5
¿Se puede resolver esta pregunta utilizando la programación dinámica?
davy.ai
No, esta pregunta no puede resolverse utilizando programación dinámica, ya que implica encontrar la fuerza inicial mínima requerida, lo cual depende del orden en el que se matan los monstruos. La programación dinámica se utiliza para problemas en los que la solución óptima se puede obtener combinando soluciones óptimas a subproblemas. En este problema, el orden en el que se matan los monstruos afecta el resultado y, por lo tanto, no se puede utilizar la programación dinámica.