Red de conocimiento informático - Aprendizaje de código fuente - ¿Qué está pasando con el problema de la torre de números?

¿Qué está pasando con el problema de la torre de números?

Comenzando desde arriba, puede elegir ir hacia la izquierda o hacia la derecha en cada nodo y caminar juntos hasta el final. Debe encontrar una ruta que maximice el valor de la ruta.

Si se utiliza el método de enumeración para esta pregunta, la cantidad de rutas que deben enumerarse será muy grande si la cantidad de capas en la torre es un poco mayor.

Si utiliza el método codicioso, a menudo no podrá obtener la solución óptima.

Al considerar el problema de la torre numérica utilizando programación dinámica, se pueden realizar análisis de arriba hacia abajo y cálculos de abajo hacia arriba. Al comenzar desde el vértice, depende de si vas hacia la izquierda o hacia la derecha.

Entonces, si puedes obtener el valor máximo yendo hacia la izquierda o hacia la derecha, siempre que el valor máximo en los caminos izquierdo y derecho sea calculado para tomar decisiones. De la misma manera, la dirección del siguiente nivel depende de si se ha encontrado el valor máximo en el siguiente nivel antes de que se pueda tomar una decisión. Empújalo capa a capa de esta forma hasta que quede bien claro cuando llegues a la penúltima capa

. Por ejemplo, el número 2, simplemente seleccione el nodo 19 con el valor mayor debajo para avanzar. Por lo tanto, cuando realmente resuelva el problema, puede comenzar desde la capa inferior y proceder capa por capa, y finalmente obtener el valor máximo.

Es muy importante dominar las reglas generales de programación a la hora de resolver el problema. Es muy importante saber qué matrices de claves suelen ser necesarias para almacenar el proceso de cambio.

El programa de muestra para el problema de la torre de números es el siguiente: