Δυναμικός προγραμματισμός: Παραδείγματα, κοινά προβλήματα και λύσεις

Δεν υπάρχει αμφιβολία ότι τα προβλήματα δυναμικού προγραμματισμού μπορεί να είναι πολύ εκφοβιστικά σε μια συνέντευξη κωδικοποίησης. Ακόμα και όταν γνωρίζετε ότι ένα πρόβλημα πρέπει να λυθεί χρησιμοποιώντας μια δυναμική μέθοδο προγραμματισμού, είναι μια πρόκληση να μπορείτε να βρείτε μια λύση εργασίας σε περιορισμένο χρονικό διάστημα.

Ο καλύτερος τρόπος για να είστε καλοί σε δυναμικά προβλήματα προγραμματισμού είναι να περάσετε όσο το δυνατόν περισσότερα από αυτά. Παρόλο που δεν χρειάζεται απαραίτητα να απομνημονεύσετε τη λύση σε κάθε πρόβλημα, είναι καλό να έχετε μια ιδέα για το πώς μπορείτε να εφαρμόσετε ένα πρόβλημα.

Τι είναι ο δυναμικός προγραμματισμός;

Με απλά λόγια, ο δυναμικός προγραμματισμός είναι μια μέθοδος βελτιστοποίησης για αναδρομικούς αλγόριθμους, οι περισσότεροι από τους οποίους χρησιμοποιούνται για την επίλυση υπολογιστικών ή μαθηματικών προβλημάτων.

Μπορείτε επίσης να το ονομάσετε αλγοριθμική τεχνική για την επίλυση ενός προβλήματος βελτιστοποίησης, χωρίζοντάς το σε απλούστερα δευτερεύοντα προβλήματα. Μια βασική αρχή στην οποία βασίζεται ο δυναμικός προγραμματισμός είναι ότι η βέλτιστη λύση σε ένα πρόβλημα εξαρτάται από τις λύσεις στα υποπροβλήματά του.

Όπου βλέπουμε μια αναδρομική λύση που έχει επαναλαμβανόμενες κλήσεις για τις ίδιες εισόδους, μπορούμε να την βελτιστοποιήσουμε χρησιμοποιώντας δυναμικό προγραμματισμό. Η ιδέα είναι απλώς να αποθηκεύσουμε τα αποτελέσματα των υποπροβλημάτων, ώστε να μην χρειάζεται να τα υπολογίσουμε ξανά όταν χρειαστεί αργότερα.

Οι δυναμικά προγραμματισμένες λύσεις έχουν πολυωνυμική πολυπλοκότητα που εξασφαλίζει πολύ πιο γρήγορο χρόνο εκτέλεσης από άλλες τεχνικές όπως η αναδρομή ή το backtracking. Στις περισσότερες περιπτώσεις, ο δυναμικός προγραμματισμός μειώνει την πολυπλοκότητα του χρόνου, γνωστή και ως μεγάλο-Ο, από εκθετικό σε πολυώνυμο.

Τι είναι η σημειογραφία Big-O;

Ο κώδικάς σας πρέπει να είναι αποτελεσματικός, αλλά πώς δείχνετε πόσο αποτελεσματικό είναι κάτι; Με το Big-O!

Τώρα που έχετε μια καλή ιδέα για το δυναμικό προγραμματισμό, ήρθε η ώρα να δείτε μερικά κοινά προβλήματα και τις λύσεις τους.

Προβλήματα δυναμικού προγραμματισμού

1. Πρόβλημα σακιδίων

Δήλωση προβλήματος

Δεδομένου ενός συνόλου αντικειμένων, το καθένα με βάρος και τιμή, καθορίστε τον αριθμό κάθε στοιχείου που θα συμπεριληφθεί στο α συλλογή έτσι ώστε το συνολικό βάρος να μην υπερβαίνει ένα δεδομένο όριο και η συνολική τιμή είναι τόσο μεγάλη όσο δυνατόν.

Σας δίνονται δύο ακέραιοι πίνακες τιμές [0..n-1] και βάρη [0..n-1] που αντιπροσωπεύουν τιμές και βάρη που σχετίζονται με n στοιχεία αντίστοιχα. Επίσης δίνεται είναι ακέραιος Δ που αντιπροσωπεύει την ικανότητα σακιδίων.

Εδώ επιλύουμε το πρόβλημα σακιδίου 0/1, που σημαίνει ότι μπορούμε να επιλέξουμε είτε να προσθέσουμε ένα αντικείμενο είτε να το αποκλείσουμε.

Αλγόριθμος

• Δημιουργήστε έναν δισδιάστατο πίνακα με n + 1 σειρές και w + 1 στήλες. Ένας αριθμός σειράς ν δηλώνει το σύνολο αντικειμένων από 1 έως Εγώκαι έναν αριθμό στήλης β δηλώνει τη μέγιστη ικανότητα μεταφοράς της τσάντας.
• Η αριθμητική τιμή στο [i] [j] δηλώνει τη συνολική αξία των αντικειμένων έως Εγώ σε μια τσάντα που μπορεί να φέρει μέγιστο βάρος j.
• Σε κάθε συντεταγμένη [i] [j] στον πίνακα, επιλέξτε τη μέγιστη τιμή που μπορούμε να αποκτήσουμε χωρίς αντικείμενο iή τη μέγιστη τιμή που μπορούμε να αποκτήσουμε αντικείμενο iόποιο είναι μεγαλύτερο.
• Η μέγιστη τιμή που μπορεί να ληφθεί συμπεριλαμβάνοντας το στοιχείο i είναι το άθροισμα του είδους Εγώ το ίδιο και τη μέγιστη τιμή που μπορεί να επιτευχθεί με την εναπομένουσα χωρητικότητα του σακιδίου.
• Εκτελέστε αυτό το βήμα μέχρι να βρείτε τη μέγιστη τιμή για το Δ^ου σειρά.

Κώδικας

def FindMax (W, n, τιμές, βάρη):
MaxVals = [[0 για x στην περιοχή (W + 1)] για x στην περιοχή (n + 1)]
για i στην περιοχή (n + 1):
για w στην περιοχή (W + 1):
αν i == 0 ή w == 0:
MaxVals [i] [w] = 0
βάρη elif [i-1] <= w:
MaxVals [i] [w] = max (τιμές [i-1]
+ MaxVals [i-1] [w-weight [i-1]], 
MaxVals [i-1] [w])
αλλού:
MaxVals [i] [w] = MaxVals [i-1] [w]
επιστροφή MaxVals [n] [W]

2. Πρόβλημα αλλαγής νομισμάτων

Δήλωση προβλήματος

Ας υποθέσουμε ότι σας δίνεται μια σειρά αριθμών που αντιπροσωπεύουν τις τιμές κάθε νομίσματος. Δεδομένου ενός συγκεκριμένου ποσού, βρείτε τον ελάχιστο αριθμό νομισμάτων που χρειάζεστε για να δημιουργήσετε αυτό το ποσό.

Αλγόριθμος

• Αρχικοποιήστε μια σειρά μεγεθών n + 1, όπου n είναι το ποσό. Αρχικοποιήστε την τιμή κάθε ευρετηρίου Εγώ στον πίνακα να είναι ίσο με το ποσό. Αυτό υποδηλώνει τον μέγιστο αριθμό νομισμάτων (χρησιμοποιώντας νομίσματα ονομαστικής αξίας 1) που απαιτούνται για τον υπολογισμό αυτού του ποσού.
• Επειδή δεν υπάρχει ονομαστική τιμή για το 0, αρχικοποιήστε τη βασική περίπτωση όπου πίνακας [0] = 0.
• Για κάθε άλλο ευρετήριο Εγώ, συγκρίνουμε την τιμή σε αυτήν (η οποία αρχικά έχει οριστεί σε n + 1) με την τιμή πίνακας [i-k] +1, που κ είναι λιγότερο από Εγώ. Αυτό ελέγχει ουσιαστικά ολόκληρη τη σειρά μέχρι το i-1 για να βρει τον ελάχιστο δυνατό αριθμό κερμάτων που μπορούμε να χρησιμοποιήσουμε.
• Εάν η τιμή σε οποιοδήποτε πίνακας [i-k] + 1 είναι μικρότερη από την υπάρχουσα τιμή στο πίνακας [i], αντικαταστήστε την τιμή στο πίνακας [i] με αυτό στο πίνακας [i-k] +1.

Κώδικας

def coin_change (d, ποσό, k):
αριθμοί = [0] * (ποσό + 1)
για j στην περιοχή (1, ποσό + 1):
ελάχιστο = ποσό
για i στην περιοχή (1, k + 1):
εάν (j> = d [i]):
ελάχιστο = min (ελάχιστο, 1 + αριθμοί [j-d [i]])
αριθμοί [j] = ελάχιστος
αριθμοί επιστροφής [ποσό]

3. Fibonacci

Δήλωση προβλήματος

Η σειρά Fibonacci είναι μια ακολουθία ακεραίων όπου ο επόμενος ακέραιος στη σειρά είναι το άθροισμα των δύο προηγούμενων.

Ορίζεται από την ακόλουθη αναδρομική σχέση: F (0) = 0, F (n) = F (n-1) + F (n-2), που F (ν) είναι τότε^ου όρος. Σε αυτό το πρόβλημα, πρέπει να δημιουργήσουμε όλους τους αριθμούς σε μια ακολουθία Fibonacci μέχρι ένα δεδομένο n^ου όρος.

Αλγόριθμος

• Αρχικά, χρησιμοποιήστε μια αναδρομική προσέγγιση για να εφαρμόσετε τη δεδομένη σχέση επανάληψης.
• Η επαναληπτική επίλυση αυτού του προβλήματος συνεπάγεται την κατάρρευση F (ν) σε F (n-1) + F (n-2)και, στη συνέχεια, καλεί τη συνάρτηση με F (n-1) και F (n + 2) ως παράμετροι. Το κάνουμε αυτό έως ότου η βασική περίπτωση n = 0, ή n = 1 επιτυγχάνονται.
• Τώρα, χρησιμοποιούμε μια τεχνική που ονομάζεται απομνημόνευση. Αποθηκεύστε τα αποτελέσματα όλων των κλήσεων λειτουργίας σε έναν πίνακα. Αυτό θα διασφαλίσει ότι για κάθε n, F (ν) πρέπει να υπολογιστεί μόνο μία φορά.
• Για τυχόν επόμενους υπολογισμούς, η τιμή του μπορεί απλώς να ανακτηθεί από τον πίνακα σε σταθερό χρόνο.

Κώδικας

def fibonacci (η): 
fibNums = [0, 1] 
για i στην περιοχή (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
επιστροφή fibNums [n] 

4. Μεγαλύτερη αυξανόμενη ακολουθία

Δήλωση προβλήματος

Βρείτε το μήκος της μεγαλύτερης αυξανόμενης ακολουθίας εντός ενός δεδομένου πίνακα. Η μακρύτερη αυξανόμενη ακολουθία είναι μια ακολουθία μέσα σε μια σειρά αριθμών με αυξανόμενη σειρά. Οι αριθμοί στη συνέχεια πρέπει να είναι μοναδικοί και σε αύξουσα σειρά.

Επίσης, τα στοιχεία της ακολουθίας δεν χρειάζεται να είναι διαδοχικά.

Αλγόριθμος

• Ξεκινήστε με μια αναδρομική προσέγγιση όπου υπολογίζετε την τιμή της μεγαλύτερης αυξανόμενης ακολουθίας του κάθε πιθανή υποπεριοχή από το ευρετήριο μηδέν έως το ευρετήριο i, όπου το i είναι μικρότερο από ή ίσο με το μέγεθος του πίνακας.
• Για να μετατρέψετε αυτήν τη μέθοδο σε δυναμική, δημιουργήστε έναν πίνακα για να αποθηκεύσετε την τιμή για κάθε ακολουθία. Αρχικοποιήστε όλες τις τιμές αυτού του πίνακα σε 0.
• Κάθε δείκτης Εγώ αυτής της συστοιχίας αντιστοιχεί στο μήκος της μεγαλύτερης αυξανόμενης ακολουθίας για μια υποπεριοχή μεγέθους Εγώ.
• Τώρα, για κάθε αναδρομική κλήση του εύρεσηLIS (arr, n), έλεγξε το ν^ου ευρετήριο του πίνακα. Εάν αυτή η τιμή είναι 0, τότε υπολογίστε την τιμή χρησιμοποιώντας τη μέθοδο στο πρώτο βήμα και αποθηκεύστε την στο ν^ου δείκτης.
• Τέλος, επιστρέψτε τη μέγιστη τιμή από τον πίνακα. Αυτό είναι το μήκος της μεγαλύτερης αυξανόμενης ακολουθίας ενός δεδομένου μεγέθους ν.

Κώδικας

def findLIS (myArray):
n = len (myArray)
lis = [0] * ν
για i στην περιοχή (1, n):
για j στην περιοχή (0, i):
αν myArray [i]> myArray [j] και lis [i] lis [i] = lis [j] +1
maxVal = 0
για i στην περιοχή (n):
maxVal = max (maxVal, lis [i])
επιστροφή maxVal

Λύσεις για προβλήματα δυναμικού προγραμματισμού

Τώρα που έχετε αντιμετωπίσει μερικά από τα πιο δημοφιλή προβλήματα δυναμικού προγραμματισμού, ήρθε η ώρα να δοκιμάσετε να εφαρμόσετε μόνοι σας τις λύσεις. Εάν έχετε κολλήσει, μπορείτε πάντα να επιστρέψετε και να ανατρέξετε στην ενότητα αλγορίθμου για κάθε παραπάνω πρόβλημα.

Δεδομένου του πόσο δημοφιλείς τεχνικές όπως η αναδρομή και ο δυναμικός προγραμματισμός είναι σήμερα, δεν θα βλάψει να δείτε μερικές δημοφιλείς πλατφόρμες όπου μπορείτε να μάθετε τέτοιες έννοιες και ακονίστε τις δεξιότητές σας κωδικοποίησης. Αν και ενδέχεται να μην αντιμετωπίζετε αυτά τα προβλήματα σε καθημερινή βάση, σίγουρα θα τα αντιμετωπίσετε σε μια τεχνική συνέντευξη.

Φυσικά, η γνώση κοινών προβλημάτων είναι υποχρεωμένη να πληρώνει μερίσματα όταν πηγαίνετε για την επόμενη συνέντευξή σας. Άνοιξε λοιπόν το δικό σου αγαπημένο IDEκαι ξεκινήστε!

Τα 9 καλύτερα κανάλια YouTube για να μάθετε τον προγραμματισμό

Είστε έτοιμοι να ξεκινήσετε την κωδικοποίηση; Αυτά τα κανάλια YouTube είναι ένας πολύ καλός τρόπος για να ξεκινήσετε σε παιχνίδια, εφαρμογές, ιστούς και άλλες εξελίξεις.

Σχετικά με τον Συγγραφέα