Creo que descubrí de dónde viene tu confusión. “Desglosar un problema en subproblemas”, y específicamente la palabra “problema”, puede tener diferentes significados según el contexto: por ejemplo, en el diseño orientado a objetos, el problema podría ser algo así como “construir un clon de eBay”, y el subproblemas: “módulo de cuenta de compilación”, “módulo de subasta de compilación”, etc., mientras que aquí el problema es, digamos, una lista de números, y los subproblemas son listas más cortas que puede hacer al dividir la lista más grande.
“Programación dinámica” se refiere a una técnica específica, y de otra manera no tiene nada que ver con “dinámica” o “programación” – es una técnica de optimización matemática. Sobre cómo se inventó ese nombre, esto es lo que dice la autobiografía de Richard Bellman al respecto:
“Una pregunta interesante es: ‘¿De dónde viene el nombre, la programación dinámica?’ La década de 1950 no fueron buenos años para la investigación matemática. Tuvimos un caballero muy interesante en Washington llamado Wilson. Era Secretario de Defensa, y en realidad tenía un miedo patológico y odio a la palabra, investigación. […] Puedes imaginar cómo se sintió, entonces, sobre el término matemático. Por lo tanto, sentí que tenía que hacer algo para proteger a Wilson y a la Fuerza Aérea del hecho de que realmente estaba haciendo matemáticas dentro de la Corporación RAND. ¿Qué título, qué nombre podría elegir? En primer lugar, me interesaba planificar, tomar decisiones y pensar. Pero planificar no es una buena palabra por varias razones. Por lo tanto, decidí usar la palabra ‘programación’. Quería transmitir la idea de que esto era dinámico, que era de varias etapas, que variaba en el tiempo. Pensé, matemos dos pájaros de un tiro. Tomemos una palabra que tenga un significado absolutamente preciso, a saber, dinámico, en el sentido físico clásico. También tiene una propiedad muy interesante como adjetivo, y es que es imposible usar la palabra, dinámico, en un sentido peyorativo. Intenta pensar en alguna combinación que posiblemente le dé un significado peyorativo. Es imposible. Por lo tanto, pensé que la programación dinámica era un buen nombre. Era algo a lo que ni siquiera un congresista podría oponerse. Así que lo usé como un paraguas para mis actividades ”
- ¿Cuál es el peor caso, el caso promedio y la mejor complejidad de tiempo de un algoritmo?
- ¿Por qué soy tan dinámico?
- ¿Qué tan complejos son los algoritmos que usan los sitios web de citas como eHarmony para unir a las personas?
- ¿Cuál es el enfoque algorítmico para resolver el problema de hackerrank Substring Diff?
- ¿Cuál es la mejor manera de ordenar un terabyte de matriz de datos, cuando tiene RAM limitada (500k), y cada elemento de la matriz tiene un par de elementos de datos, de aproximadamente 1-10k cada uno?
Entonces sí, definitivamente es su propia categoría de algoritmos, y aunque el nombre es un poco extraño, este es casi siempre el caso cuando se trata de terminología: al final, solo elige alguna palabra o combinación de palabras, y siempre Como todos los involucrados saben a qué se refieren, puedes comunicarte más rápido. No importa si las palabras no tienen sentido o no, son solo un símbolo.