La idea básica de la programación dinámica es descomponer el problema que se resolverá en varios subproblemas, primero resolver los subproblemas y guardar las soluciones de estos subproblemas. Si necesita usar las soluciones de estos subproblemas en el futuro al resolver subproblemas más grandes, puede extraer directamente estas soluciones calculadas para evitar operaciones repetidas. La solución para guardar subproblemas se puede llenar utilizando el método de formulario, como guardar en una matriz.
Use un ejemplo práctico para reflejar la idea algorítmica de la programación dinámica: el problema del cambio de monedas.
Descripción de la pregunta:
Supongamos que hay varias monedas y hay cantidades ilimitadas. Averigüe el número mínimo de monedas que pueden compensar un cierto número de cambios. Por ejemplo, varios tipos de monedas son [1, 3, 5], el número mínimo de monedas con un valor nominal de 2 es 2 (1, 1), el número mínimo de monedas con un valor nominal de 4 es 2 (1, 3) y el número mínimo de monedas con un valor nominal de 11 es 3 (5, 5, 1 o 5, 3, 3).
Análisis de problemas:
Suponga que los diferentes conjuntos de monedas son la moneda de matriz [0, ..., N-1]. Luego encuentre el número mínimo de monedas con el valor nominal K, luego la función de conteo y la moneda de matriz de monedas cumplen con esta condición:
Count (k) = min (count (k - moneda [0]), ..., count (k - moned [n - 1])) + 1;
Y la fórmula anterior solo se mantiene si se cumple la condición k - monedas [i]> = 0 && k - coin [i] <k.
Porque K- Coin [i] <k, al calcular el recuento (k), el recuento (i) (i <- [0, k-1]) debe cumplirse, por lo que aquí implica el problema del retroceso.
Por lo tanto, podemos crear una matriz de matriz [K + 1] [Coin.Length + 1], de modo que la matriz [0] [j] se inicialice a 0 valores, y guarde el número mínimo de monedas con un valor nominal de I en la matriz [i] [Coin.length].
Y el proceso específico es el siguiente:
* k | coin 1 3 5 min * 0 0 0 0 0 0 * 1 1 0 0 1 * 2 2 0 2 * 3 3 1 0 3, 1 * 4 2 2 0 2, 2 * 5 3 3 1 3, 3, 1 * 6 2 2 2 2, 2, 2 * ... ...
Finalmente, la implementación específica del código Java es la siguiente:
public static int BacktrackingCoin (int [] monedas, int k) {// método de retroceso + programación dinámica if (Coins == null || Coins.length == 0 || k <1) {return 0; } int [] [] matrix = new int [k + 1] [Coins.length + 1]; for (int i = 1; i <= k; i ++) {for (int j = 0; j <Coins.length; j ++) {int prek = i - monedas [j]; if (prek> -1) {// Solo cuando no es inferior a 0, se puede realizar prek en la matriz de matriz y se puede realizar el retroceso. matriz [i] [j] = matriz [prek] [Coins.length] + 1; // El valor nominal i está retroceso if (matriz [i] [Coins.length] == 0 || matriz [i] [j] <matrix [i] [coins.length]) {// si el número de monedas corriente es el número más pequeño, actualiza el número mínimo de las bases en la columna de la columna minimum en la columna de la columna minimum en la columna de la columna minimum en el minús matriz [i] [monedas.length] = matrix [i] [j]; }}} return matrix [k] [Coins.Length]; }¡El código ha sido probado y todos los casos de prueba dados por la pregunta han pasado!
Resumir
Lo anterior es todo el contenido de este artículo sobre el código de implementación del problema de cambio de monedas de la programación dinámica Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!