Programació dinàmica és un mètode utilitzat en matemàtiques i informàtica per resoldre problemes complexos desglossant-los en subproblemes més simples. En resoldre cada subproblema només una vegada i emmagatzemar els resultats, evita càlculs redundants, donant lloc a solucions més eficients per a una àmplia gamma de problemes. Aquest article ofereix una exploració detallada dels conceptes de programació dinàmica, il·lustrada amb exemples.
javac no es reconeix
Programació dinàmica
Taula de contingut
- Què és la Programació Dinàmica?
- Com funciona la programació dinàmica?
- Exemples de programació dinàmica
- Quan utilitzar la programació dinàmica?
- Enfocaments de la Programació Dinàmica
- Algoritme de programació dinàmica
- Avantatges de la Programació Dinàmica
- Aplicacions de la Programació Dinàmica
- Aprendre les bases de la programació dinàmica
- Conceptes avançats en programació dinàmica
- Problemes de programació dinàmica
Què és la Programació Dinàmica (DP)?
Programació dinàmica (DP) és un mètode utilitzat en matemàtiques i informàtica per resoldre problemes complexos desglossant-los en subproblemes més simples. En resoldre cada subproblema només una vegada i emmagatzemar els resultats, evita càlculs redundants, donant lloc a solucions més eficients per a una àmplia gamma de problemes.
Com funciona la programació dinàmica (DP)?
- Identificar subproblemes: Dividiu el problema principal en subproblemes més petits i independents.
- Solucions de botiga: Resoldre cada subproblema i emmagatzemar la solució en una taula o matriu.
- Creació de solucions: Utilitzeu les solucions emmagatzemades per crear la solució al problema principal.
- Evitar la redundància: En emmagatzemar solucions, DP assegura que cada subproblema es resol només una vegada, reduint el temps de càlcul.
Exemples de programació dinàmica (DP)
Exemple 1: Considereu el problema de trobar la seqüència de Fibonacci:
Seqüència de Fibonacci: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …
Enfocament de força bruta:
Per trobar l'enèsim nombre de Fibonacci utilitzant un enfocament de força bruta, simplement afegiríeu el (n-1)è i (n-2)è Nombres de Fibonacci. Això funcionaria, però seria ineficient per a grans valors de n , ja que caldria calcular tots els nombres de Fibonacci anteriors.
Enfocament de programació dinàmica:
Sèrie de Fibonacci utilitzant programació dinàmica
- Subproblems: F(0), F(1), F(2), F(3), …
- Solucions de botiga: Creeu una taula per emmagatzemar els valors de F(n) a mesura que es calculen.
- Creació de solucions: Per a F(n), busqueu F(n-1) i F(n-2) a la taula i afegiu-los.
- Evitar la redundància: La taula assegura que cada subproblema (per exemple, F(2)) es resol només una vegada.
Utilitzant DP, podem calcular de manera eficient la seqüència de Fibonacci sense haver de tornar a calcular subproblemes.
introduïu el maneig d'excepcions de Java
Exemple 2: Subseqüència comuna més llarga (trobar la subseqüència més llarga que és comuna a dues cadenes)
Exemple 3: Camí més curt d'un gràfic (trobar el camí més curt entre dos nodes d'un gràfic)
Exemple 4: Problema de la motxilla (trobar el valor màxim dels articles que es poden col·locar en una motxilla amb una capacitat determinada)
Quan utilitzar la programació dinàmica (DP)?
La programació dinàmica és una tècnica d'optimització utilitzada per resoldre problemes que consta de les següents característiques:
1. Subestructura òptima:
La subestructura òptima significa que combinem els resultats òptims dels subproblemes per aconseguir el resultat òptim del problema més gran.
variable bash
Exemple:
Considereu el problema de trobar el cost mínim camí en un gràfic ponderat a partir de a font node a a destinació node. Podem dividir aquest problema en subproblemes més petits:
- Troba el mínim cost camí des del font node a cadascun intermedi node.
- Troba el mínim cost camí de cadascun intermedi node al destinació node.
La solució al problema més gran (trobar el camí de cost mínim des del node font fins al node de destinació) es pot construir a partir de les solucions d'aquests subproblemes més petits.
2. Subproblemes superposats:
Els mateixos subproblemes es resolen repetidament en diferents parts del problema.
Exemple:
Considereu el problema de calcular el Sèrie de Fibonacci . Per calcular el nombre de Fibonacci a l'índex n , hem de calcular els nombres de Fibonacci als índexs n-1 i n-2 . Això vol dir que el subproblema de calcular el nombre de Fibonacci a l'índex n-1 s'utilitza dues vegades en la solució del problema més gran de calcular el nombre de Fibonacci a l'índex n .
Enfocaments de programació dinàmica (DP)
La programació dinàmica es pot aconseguir mitjançant dos enfocaments:
1. Enfocament de dalt a baix (memoització):
En l'enfocament de dalt a baix, també conegut com memorització , comencem amb la solució final i la desglossem recursivament en subproblemes més petits. Per evitar càlculs redundants, emmagatzemem els resultats dels subproblemes resolts en una taula de memorització.
Desglossem l'enfocament de dalt a baix:
- Comença amb la solució final i la divideix recursivament en subproblemes més petits.
- Emmagatzema les solucions dels subproblemes en una taula per evitar càlculs redundants.
- Adequat quan el nombre de subproblemes és gran i molts d'ells es reutilitzen.
2. Enfocament de baix a dalt (tabulació):
En l'enfocament de baix a dalt, també conegut com tabulació , comencem amb els subproblemes més petits i a poc a poc arribem a la solució final. Emmagatzemem els resultats dels subproblemes resolts en una taula per evitar càlculs redundants.
Desglossem l'enfocament de baix a dalt:
- Comença amb els subproblemes més petits i s'acumula gradualment fins a la solució final.
- Omple una taula amb solucions a subproblemes de manera ascendente.
- Adequat quan el nombre de subproblemes és petit i la solució òptima es pot calcular directament des de les solucions a subproblemes més petits.
Programació dinàmica (DP) Algorisme
La programació dinàmica és una tècnica algorítmica que resol problemes complexos dividint-los en subproblemes més petits i emmagatzemant les seves solucions per a un ús futur. És especialment eficaç per als problemes que conté subproblemes superposats i subestructura òptima.
Algorismes comuns que utilitzen la programació dinàmica:
- Subseqüència comuna més llarga (LCS): Troba la subseqüència comuna més llarga entre dues cadenes.
- El camí més curt d'un gràfic: Troba el camí més curt entre dos nodes en un gràfic.
- Problema de la motxilla: Determina el valor màxim dels articles que es poden col·locar en una motxilla amb una capacitat determinada.
- Multiplicació de cadena matricial: Optimitza l'ordre de multiplicació de matrius per minimitzar el nombre d'operacions.
- Seqüència de Fibonacci: Calcula l'enèsim nombre de Fibonacci.
Avantatges de la Programació Dinàmica (DP)
La programació dinàmica té una àmplia gamma d'avantatges, com ara:
- Evita tornar a calcular els mateixos subproblemes diverses vegades, la qual cosa comporta un estalvi de temps important.
- Assegura que es trobi la solució òptima considerant totes les combinacions possibles.
- Desglossa els problemes complexos en subproblemes més petits i més manejables.
Aplicacions de la Programació Dinàmica (DP)
La programació dinàmica té una àmplia gamma d'aplicacions, que inclouen:
- Optimització: Problema de motxilla, problema de camí més curt, problema de màxim subarray
- Ciències de la Computació: Subseqüència comuna més llarga, distància d'edició, concordança de cadenes
- Recerca operativa: Gestió d'inventari, programació, assignació de recursos
Ara, explorem un full de ruta complet per dominar la programació dinàmica.
Aprèn Bàsiques de Programació Dinàmica (DP)
- Què és la memoització? Un tutorial complet
- Tabulació vs memorització
- Propietat òptima de la subestructura
- Propietat de subproblemes superposats
- Com resoldre un problema de programació dinàmica?
Conceptes avançats en programació dinàmica (DP)
- Enmascarament de bits i programació dinàmica | Set 1
- Enmascarament de bits i programació dinàmica | Set-2 (TSP)
- Dígit DP | Introducció
- Suma sobre subconjunts | Programació dinàmica
Programació dinàmica (DP) Problemes
Hem classificat els problemes estàndard de programació dinàmica (DP) en tres categories: fàcils, mitjans i difícils.
rebaixa amb imatges
1. Problemes fàcils de programació dinàmica (DP)
- Nombres de Fibonacci
- nè Número català
- Números de campana (nombre de maneres de dividir un conjunt)
- Coeficient binomial
- Problema de canvi de moneda
- Problema de la suma del subconjunt
- Calculeu nCr % p
- Tallar una vareta
- Algoritme de tanca de pintura
- Subseqüència comuna més llarga
- Subseqüència creixent més llarga
- La subseqüència més llarga de manera que la diferència entre adjacents és d'un
- Submatriu quadrada de mida màxima amb tots els 1
- Ruta del cost mínim
- Nombre mínim de salts per arribar al final
- Subcadena comuna més llarga (solució DP optimitzada per a l'espai)
- Compteu les maneres d'arribar a l'enèsima escala mitjançant el pas 1, 2 o 3
- Compteu tots els camins possibles des de la part superior esquerra fins a la part inferior dreta d'una matriu mXn
- Camins únics en una quadrícula amb obstacles
2. Problemes mitjans de programació dinàmica (DP)
- Algoritme de Floyd Warshall
- Algoritme Bellman-Ford
- Problema de la motxilla 0-1
- Impressió d'articles en motxilla 0/1
- Motxilla sense límits (permet la repetició d'elements)
- Trencaclosques de caiguda d'ous
- Problema de trencament de paraules
- Problema de coberta de vèrtex
- Problema d'apilament de rajoles
- Problema d'apilament de caixes
- Problema de partició
- Problema del venedor ambulant | Set 1 (programació ingenua i dinàmica)
- Subseqüència palindròmica més llarga
- Subseqüència creixent comuna més llarga (LCS + LIS)
- Trobeu totes les sumes diferents de subconjunts (o subseqüències) d'una matriu
- Programació de treball ponderada
- Recompte de trastorns (permutació de manera que cap element apareix a la seva posició original)
- Insercions mínimes per formar un palíndrom
- Coincidència de patró de comodí
- Maneres d'ordenar les boles de manera que les boles adjacents siguin de diferents tipus
3. Problemes difícils de programació dinàmica (DP)
- Partició de palíndrom
- Problema d'embolcall de paraules
- El problema de la partició del pintor
- Programa per al problema del pont i la torxa
- Multiplicació de cadena matricial
- Impressió de claudàtors al problema de multiplicació de la cadena de matrius
- Rectangle de suma màxima en una matriu 2D
- Màxim benefici en comprar i vendre una acció com a màxim k vegades
- Cost mínim per ordenar cadenes mitjançant operacions de reversió de diferents costos
- Recompte de subseqüències AP (Progressió aritmètica) en una matriu
- Introducció a la Programació Dinàmica en Arbres
- Alçada màxima de l'arbre quan qualsevol node es pot considerar com a arrel
- Subcadena més llarga repetida i no solapada
Links ràpids:
- Apreneu l'estructura de dades i els algorismes | Tutorial DSA
- Les 20 principals preguntes d'entrevista de programació dinàmica
- 'Problemes de pràctica' sobre programació dinàmica
- ‘Quiz’ sobre programació dinàmica