Ακολουθήστε αυτά τα βήματα για να λύσετε οποιοδήποτε πρόβλημα συνέντευξης δυναμικού προγραμματισμού

Παρά τη σημαντική εμπειρία δημιουργίας προϊόντων λογισμικού, πολλοί μηχανικοί νιώθουν νευρικότητα στη σκέψη να περάσουν από μια συνέντευξη κωδικοποίησης που επικεντρώνεται σε αλγόριθμους. Έχω πάρει συνέντευξη από εκατοντάδες μηχανικούς στο Refdash, στο Google και στις νεοσύστατες εταιρείες έχω συμμετάσχει, και μερικές από τις πιο συχνές ερωτήσεις που κάνουν τους μηχανικούς άβολα είναι αυτές που περιλαμβάνουν το Δυναμικό Προγραμματισμό (DP).

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

Δυναμικός προγραμματισμός - Προβλέψιμος και προετοιμασμένος

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

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

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

7 βήματα για την επίλυση ενός προβλήματος δυναμικού προγραμματισμού

Στο υπόλοιπο αυτής της ανάρτησης, θα εξετάσω μια συνταγή που μπορείτε να ακολουθήσετε για να μάθω αν ένα πρόβλημα είναι "πρόβλημα DP", καθώς και για να βρω μια λύση σε ένα τέτοιο πρόβλημα. Συγκεκριμένα, θα ακολουθήσω τα ακόλουθα βήματα:

  1. Πώς να αναγνωρίσετε ένα πρόβλημα DP
  2. Προσδιορίστε τις μεταβλητές προβλήματος
  3. Εκφράστε σαφώς τη σχέση επανάληψης
  4. Προσδιορίστε τις βασικές περιπτώσεις
  5. Αποφασίστε εάν θέλετε να το εφαρμόσετε επαναληπτικά ή αναδρομικά
  6. Προσθήκη απομνημονεύσεων
  7. Προσδιορίστε την πολυπλοκότητα του χρόνου

Πρόβλημα DP δείγματος

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

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

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

Εδώ είναι οι κανόνες:

1) Σας δίνεται ένα επίπεδο διάδρομο με ένα σωρό καρφιά σε αυτό. Ο διάδρομος αντιπροσωπεύεται από μια δυαδική συστοιχία που δείχνει εάν ένα συγκεκριμένο (διακριτό) σημείο είναι καθαρό από αιχμές. Είναι αλήθεια για σαφές και λάθος για μη σαφές.

Παράδειγμα παράστασης πίνακα:

2) Σας δίνεται ταχύτητα εκκίνησης. Το S. είναι ένας μη αρνητικός ακέραιος αριθμός σε οποιοδήποτε δεδομένο σημείο και δείχνει πόσο θα προχωρήσετε με το επόμενο άλμα.

3) Κάθε φορά που προσγειώνεστε σε ένα σημείο, μπορείτε να προσαρμόσετε την ταχύτητά σας έως και 1 μονάδα πριν από το επόμενο άλμα.

4) Θέλετε να σταματήσετε με ασφάλεια οπουδήποτε κατά μήκος του διαδρόμου (δεν χρειάζεται να είστε στο τέλος του πίνακα). Σταματάτε όταν η ταχύτητά σας γίνει 0. Ωστόσο, εάν φτάσετε σε μια ακίδα σε οποιοδήποτε σημείο, η τρελή μπάλα που αναπηδά σας ξεσπά και τελειώνει το παιχνίδι.

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

Βήμα 1: Πώς να αναγνωρίσετε ένα πρόβλημα Δυναμικού Προγραμματισμού

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

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

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

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

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

Βήμα 2: Προσδιορίστε τις μεταβλητές προβλήματος

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

Συνήθως σε συνεντεύξεις, θα έχετε μία ή δύο παραμέτρους που αλλάζουν, αλλά τεχνικά αυτό θα μπορούσε να είναι οποιοσδήποτε αριθμός. Ένα κλασικό παράδειγμα ενός προβλήματος μίας αλλαγής παραμέτρου είναι "προσδιορισμός ενός αριθμού F-Fibonacci". Ένα τέτοιο παράδειγμα για ένα πρόβλημα δύο παραμέτρων που αλλάζει είναι «Υπολογισμός απόστασης επεξεργασίας μεταξύ συμβολοσειρών». Εάν δεν είστε εξοικειωμένοι με αυτά τα προβλήματα, μην ανησυχείτε για αυτό.

Ένας τρόπος προσδιορισμού του αριθμού των παραμέτρων που αλλάζουν είναι να παραθέσετε παραδείγματα διαφόρων υποπροβλημάτων και να συγκρίνετε τις παραμέτρους. Η μέτρηση του αριθμού των μεταβαλλόμενων παραμέτρων είναι πολύτιμη για τον προσδιορισμό του αριθμού των υποπροβλημάτων που πρέπει να λύσουμε. Είναι επίσης σημαντικό από μόνο του να μας βοηθήσει να ενισχύσουμε την κατανόηση της σχέσης υποτροπής από το βήμα 1.

Στο παράδειγμά μας, οι δύο παράμετροι που θα μπορούσαν να αλλάξουν για κάθε υποπρόβλημα είναι:

  1. Θέση σειράς (P)
  2. Ταχύτητα (S)

Θα μπορούσε κανείς να πει ότι ο μπροστά διάδρομος αλλάζει επίσης, αλλά αυτό θα ήταν περιττό λαμβάνοντας υπόψη ότι ολόκληρος ο μη μεταβαλλόμενος διάδρομος και η θέση (P) έχουν ήδη αυτές τις πληροφορίες.

Τώρα, με αυτές τις 2 μεταβαλλόμενες παραμέτρους και άλλες στατικές παραμέτρους, έχουμε την πλήρη περιγραφή των υπο-προβλημάτων μας.

Προσδιορίστε τις μεταβαλλόμενες παραμέτρους και προσδιορίστε τον αριθμό των υποπροβλημάτων.

Βήμα 3: Εκφράστε σαφώς τη σχέση επανάληψης

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

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

Εδώ είναι πώς το σκεφτόμαστε στο δείγμα μας πρόβλημα:

Επειδή μπορείτε να προσαρμόσετε την ταχύτητά σας έως και 1 πριν μεταβείτε στην επόμενη θέση, υπάρχουν μόνο 3 πιθανές ταχύτητες και επομένως 3 σημεία στα οποία θα μπορούσαμε να είμαστε επόμενοι.

Πιο επίσημα, εάν η ταχύτητά μας είναι S, θέση P, θα μπορούσαμε να πάμε από (S, P) στο:

  1. (S, P + S) ; # αν δεν αλλάξουμε την ταχύτητα
  2. (S - 1, P + S - 1) ; # αν αλλάξουμε την ταχύτητα κατά -1
  3. (S + 1, P + S + 1) ; # αν αλλάξουμε την ταχύτητα κατά +1

Εάν μπορούμε να βρούμε έναν τρόπο να σταματήσουμε σε οποιοδήποτε από τα παραπάνω υποπροβλήματα, τότε μπορούμε επίσης να σταματήσουμε από (S, P). Αυτό συμβαίνει επειδή μπορούμε να μεταβούμε από (S, P) σε οποιαδήποτε από τις παραπάνω τρεις επιλογές.

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

canStop (S, P) = canStop (S, P + S) || canStop (S - 1, P + S - 1) || canStop (S + 1, P + S + 1)

Ωχ, φαίνεται ότι έχουμε τη σχέση επανάληψης!

Σχέση επανάληψης: Υποθέτοντας ότι έχετε υπολογίσει τα υποπροβλήματα, πώς θα υπολογίζατε το κύριο πρόβλημα;

Βήμα 4: Προσδιορίστε τις βασικές περιπτώσεις

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

Ο λόγος για τον οποίο ένα πρόβλημα δεν μπορεί να απλουστευθεί περαιτέρω είναι ότι μία από τις παραμέτρους θα γίνει μια τιμή που δεν είναι δυνατή λόγω των περιορισμών του προβλήματος.

Στο παράδειγμά μας πρόβλημα, έχουμε δύο μεταβαλλόμενες παραμέτρους, S και P. Ας σκεφτούμε ποιες πιθανές τιμές S και P μπορεί να μην είναι νόμιμες:

  1. Το P πρέπει να βρίσκεται εντός των ορίων του δεδομένου διαδρόμου
  2. Το P δεν μπορεί να είναι τέτοιο που ο διάδρομος [P] είναι ψευδής γιατί αυτό θα σήμαινε ότι είμαστε σε μια ακίδα
  3. Το S δεν μπορεί να είναι αρνητικό και το S == 0 δείχνει ότι έχουμε τελειώσει

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

Στο παράδειγμά μας:

  1. Ρ <0 || P> = το μήκος του διαδρόμου μοιάζει με το σωστό. Μια εναλλακτική λύση θα μπορούσε να είναι να θεωρηθεί το m Ping = = τέλος του διαδρόμου μια υπόθεση βάσης. Ωστόσο, είναι πιθανό ένα πρόβλημα να χωριστεί σε ένα υποπρόβλημα που ξεπερνά το τέλος του διαδρόμου, οπότε πρέπει πραγματικά να ελέγξουμε ανισότητες.
  2. Αυτό φαίνεται αρκετά προφανές. Μπορούμε απλά να ελέγξουμε εάν ο διάδρομος [P] είναι λανθασμένος .
  3. Παρόμοια με το # 1, θα μπορούσαμε απλώς να ελέγξουμε για S <0 και S == 0. Ωστόσο, εδώ μπορούμε να ισχυριστούμε ότι είναι αδύνατο το S να είναι <0 επειδή το S μειώνεται το πολύ 1, οπότε θα πρέπει να περάσει S == 0 περίπτωση εκ των προτέρων. Το efore S == 0 είναι μια επαρκής βάση για την παράμετρο S.

Βήμα 5: Αποφασίστε εάν θέλετε να το εφαρμόσετε επαναληπτικά ή αναδρομικά

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

Για να αποφασίσετε αν θα πάτε επανειλημμένα ή αναδρομικά, θέλετε να σκεφτείτε προσεκτικά τις αντισταθμίσεις .

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

Στο συγκεκριμένο πρόβλημά μας, εφάρμοσα και τις δύο εκδόσεις. Εδώ είναι ο κώδικας python για αυτό:

Μια αναδρομική λύση: (μπορείτε να βρείτε αρχικά αποσπάσματα κώδικα εδώ)

Μια επαναληπτική λύση: (μπορείτε να βρείτε αποσπάσματα πρωτότυπου κώδικα εδώ)

Βήμα 6: Προσθήκη απομνημονεύσεων

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

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

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

Αυτό σημαίνει ότι πρέπει:

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

Εδώ είναι ο κωδικός από ψηλά με προστιθέμενη απομνημόνευση (επισημαίνονται οι προστιθέμενες γραμμές): (μπορείτε να βρείτε αρχικά αποσπάσματα κώδικα εδώ)

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

  1. Δημιούργησα έναν διάδρομο μήκους 1000 με αιχμές σε τυχαία μέρη (επέλεξα να υπάρχει πιθανότητα μια ακίδα σε οποιοδήποτε σημείο να είναι 20%)
  2. initSpeed ​​= 30
  3. Έτρεξα όλες τις συναρτήσεις 10 φορές και μέτρησα τον μέσο χρόνο εκτέλεσης

Εδώ είναι τα αποτελέσματα (σε δευτερόλεπτα):

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

Βήμα 7: Προσδιορίστε την πολυπλοκότητα του χρόνου

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

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

Στο παράδειγμά μας πρόβλημα, ο αριθμός των καταστάσεων είναι | P | * | S |, πού

  • P είναι το σύνολο όλων των θέσεων (| P | δείχνει τον αριθμό των στοιχείων στο P)
  • Το S είναι το σύνολο όλων των ταχυτήτων

Η δουλειά που πραγματοποιείται ανά κάθε κατάσταση είναι O (1) σε αυτό το πρόβλημα, επειδή, λαμβάνοντας υπόψη όλες τις άλλες καταστάσεις, απλά πρέπει να κοιτάξουμε 3 υποπροβλήματα για να προσδιορίσουμε την κατάσταση που προκύπτει.

Όπως σημειώσαμε στον κώδικα πριν, | S | περιορίζεται από το μήκος του διαδρόμου (| P |), οπότε θα μπορούσαμε να πούμε ότι ο αριθμός των καταστάσεων είναι | P | ² και επειδή η εργασία που πραγματοποιείται ανά κάθε κατάσταση είναι O (1), τότε η συνολική πολυπλοκότητα του χρόνου είναι O (| P | ²).

Ωστόσο, φαίνεται ότι | S | μπορεί να περιοριστεί περαιτέρω, επειδή εάν ήταν πραγματικά | P |, είναι πολύ σαφές ότι η διακοπή δεν θα ήταν δυνατή επειδή θα πρέπει να πηδήσετε το μήκος ολόκληρου του διαδρόμου στην πρώτη κίνηση.

Ας δούμε λοιπόν πώς μπορούμε να βάλουμε ένα αυστηρότερο δέσιμο στο | S |. Ας καλέσουμε τη μέγιστη ταχύτητα S. Ας υποθέσουμε ότι ξεκινάμε από τη θέση 0. Πόσο γρήγορα θα μπορούσαμε να σταματήσουμε εάν προσπαθούσαμε να σταματήσουμε το συντομότερο δυνατό και αν αγνοήσουμε τις πιθανές αιχμές;

Στην πρώτη επανάληψη, θα έπρεπε να φτάσουμε τουλάχιστον στο σημείο (S-1), ρυθμίζοντας την ταχύτητά μας στο μηδέν κατά -1. Από εκεί θα πάμε τουλάχιστον (S-2) βήματα μπροστά και ούτω καθεξής.

Για διάδρομο μήκους L , πρέπει να κρατήσετε τα ακόλουθα:

=> (S-1) + (S-2) + (S-3) +…. + 1 <L

=> S * (S-1) / 2 <L

=> S² - S - 2L <0

Εάν βρείτε ρίζες της παραπάνω συνάρτησης, θα είναι:

r1 = 1/2 + sqrt (1/4 + 2L) και r2 = 1/2 - sqrt (1/4 + 2L)

Μπορούμε να γράψουμε την ανισότητά μας ως:

(S - r1) * (S - r2) < ; 0

Λαμβάνοντας υπόψη ότι S - r2> 0 για οποιαδήποτε S> 0 και L> 0, χρειαζόμαστε τα εξής:

S - 1/2 - sqrt (1/4 + 2L) < ; 0

=> S <1/2 + sqrt (1/4 + 2L)

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

Αυτό σημαίνει ότι η συνολική πολυπλοκότητα χρόνου εξαρτάται μόνο από το μήκος του διαδρόμου L στην ακόλουθη μορφή:

O (L * sqrt (L)) που είναι καλύτερο από το O (L²)

O (L * sqrt (L)) είναι το ανώτερο όριο της χρονικής πολυπλοκότητας

Καταπληκτικά, τα καταφέρατε! :)

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

Ακολουθούν μερικά επόμενα βήματα που μπορείτε να κάνετε

  1. Επεκτείνετε το πρόβλημα δείγματος προσπαθώντας να βρείτε μια διαδρομή προς ένα σημείο διακοπής. Λύσαμε ένα πρόβλημα που σας λέει εάν μπορείτε να σταματήσετε, αλλά τι γίνεται αν θέλετε να γνωρίζετε επίσης τα βήματα που πρέπει να ακολουθήσετε για να σταματήσετε τελικά κατά μήκος του διαδρόμου; Πώς θα τροποποιούσατε την υπάρχουσα εφαρμογή για να το κάνετε αυτό;
  2. Αν θέλετε να ενισχύσετε την κατανόηση της απομνημόνευσης και να καταλάβετε ότι είναι απλώς μια προσωρινή μνήμη αποτελέσματος λειτουργίας, θα πρέπει να διαβάσετε για διακοσμητές στο Python ή παρόμοιες έννοιες σε άλλες γλώσσες. Σκεφτείτε πώς θα σας επέτρεπαν να εφαρμόσετε απομνημόνευση γενικά για οποιαδήποτε λειτουργία που θέλετε να απομνημονεύσετε.
  3. Εργαστείτε για περισσότερα προβλήματα DP ακολουθώντας τα βήματα που περάσαμε. Μπορείτε πάντα να βρείτε πολλά από αυτά στο διαδίκτυο (π.χ. LeetCode ή GeeksForGeeks). Καθώς ασκείστε, λάβετε υπόψη ένα πράγμα: μάθετε ιδέες, μην μάθετε προβλήματα. Ο αριθμός των ιδεών είναι σημαντικά μικρότερος και είναι ένας ευκολότερος χώρος για να κατακτήσετε, ο οποίος θα σας εξυπηρετήσει επίσης πολύ καλύτερα.

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

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