Al escribir un programa recursivo o basado en bucles para resolver un problema, en cada llamada recursiva o iteración de bucle nos preocupa cómo llegar a la solución a nuestro problema actual desde la (s) solución (es) hasta uno o más subproblemas.
Ahora, en DP, de una forma u otra, está reduciendo la entrada de su problema a algo que puede usar como índice de matriz. La pregunta es si puede representar adecuadamente la entrada del problema como un índice de matriz única o si necesita más de un índice. (Sí, podría jugar y encontrar formas de codificar múltiples índices en un número, pero no queremos pasar por contorsiones extrañas como esas si pudiéramos usar dos índices en su lugar).
Siempre me resulta más fácil olvidarme brevemente de DP y simplemente formular la solución primero como una función recursiva (probablemente en pseudocódigo) cuyo significado puedo describir en una oración. (Por cierto, esta también es una buena manera de saber si DP es necesario en primer lugar; la característica fundamental de un problema de DP es que puede terminar haciendo llamadas recursivas en las mismas entradas más de una vez). Si puedo escribir un función de un argumento, entonces tengo buenas razones para creer que puedo usar un índice, por lo tanto, una matriz 1-D. Si no puedo hacerlo con uno, es posible que necesite dos argumentos, lo que significa que necesito una matriz 2-D. Si necesito tres, entonces necesito una matriz 3-D. Y así.
- ¿Cuál es la mejor manera de explicar este método recursivo en Java?
- Cómo explicar el algoritmo de clasificación de inserción a un niño de 10 años
- Cómo comenzar a aprender y explorar el campo de los Algoritmos de Big Data
- ¿Cuál es la optimización de un conjunto de antenas?
- Cuando trato de entender una técnica como la memorización o lo que sea, me enfrento a muchos dolores y no lo entiendo de inmediato. Necesito intentarlo varias veces. ¿Es normal o debo obtener algoritmos y técnicas con al menos uno o 2 aciertos?
Para un ejemplo de requerir dos índices: en el problema de la distancia de edición, estamos viendo dos cadenas s1 y s2, y en cualquier llamada dada (si funciona de forma recursiva) o iteración de bucle, debemos ser conscientes de alguna posición en s1 y alguna posición en s2. Por lo tanto, tiene sentido usar dos índices.
Un apéndice, provocado por la discusión en los comentarios: no hay sustituto para resolver el problema a mano , en papel o en un tablero, para entradas de ejemplo simples . Esto le dirá con bastante rapidez si puede salirse con una entrada o si necesita dos (o tres).
