תכנות דינמי: דוגמאות, בעיות נפוצות ופתרונות

אין ספק שבעיות תכנות דינמיות יכולות להיות מאוד מאיימות בראיון קידוד. גם כשאתה אולי יודע שצריך לפתור בעיה בשיטת תכנות דינמית, זה אתגר להיות מסוגל להמציא פתרון עבודה במסגרת זמן מוגבלת.

הדרך הטובה ביותר להיות טובים בבעיות תכנות דינמיות היא לעבור על כמה שיותר מהם. אמנם אתה לא בהכרח צריך לשנן את הפיתרון לכל בעיה, אבל טוב שיש לך מושג כיצד ניתן ליישם בעיה כזו.

מהי תכנות דינמי?

במילים פשוטות, תכנות דינמי הוא שיטת אופטימיזציה לאלגוריתמים רקורסיביים, שרובם משמשים לפתרון בעיות מחשוב או מתמטיקה.

אתה יכול גם לקרוא לזה טכניקה אלגוריתמית לפתרון בעיית אופטימיזציה על ידי פריצתה לבעיות משנה פשוטות יותר. עיקרון מרכזי שמבוסס על תכנות דינמי הוא שהפתרון האופטימלי לבעיה תלוי בפתרונות לבעיות המשנה שלו.

בכל מקום בו אנו רואים פתרון רקורסיבי שיש בו קריאות חוזרות ונשנות לאותן תשומות, אנו יכולים לייעל אותו באמצעות תכנות דינמי. הרעיון הוא פשוט לאחסן את התוצאות של בעיות משנה כדי שלא נצטרך לחשב אותן מחדש בעת הצורך בהמשך.

לפתרונות מתוכנתים באופן דינמי מורכבות פולינומית שמבטיחה זמן ריצה מהיר בהרבה מאשר טכניקות אחרות כמו רקורסיה או מעקב אחורי. ברוב המקרים, תכנות דינמי מפחית את מורכבות הזמן, המכונה גם

גדול-או, מאקספוננציאלי לפולינומי.

מהי Big-O Notation?

הקוד שלך צריך להיות יעיל, אבל איך אתה מראה כמה יעיל משהו? עם ביג-או!

עכשיו כשיש לך מושג טוב מה זה תכנות דינמי, זה הזמן לבדוק כמה בעיות נפוצות והפתרונות שלהן.

בעיות תכנות דינמיות

1. בעיית תרמיל

הצהרת בעיה

בהינתן קבוצה של פריטים, כל אחד עם משקל וערך, קבע את מספר כל פריט שייכלל ב- אוסף כך שהמשקל הכולל לא יעלה על מגבלה נתונה והערך הכולל יהיה גדול כמו אפשרי.

נותנים לך שני מערכים שלמים ערכים [0..n-1] ו משקולות [0..n-1] המייצגים ערכים ומשקלים הקשורים ל- n פריטים בהתאמה. ניתן גם מספר שלם W המייצג את יכולת הכנאפה.

כאן אנו פותרים את בעיית הכנאפה 0/1, כלומר נוכל לבחור להוסיף פריט או לא לכלול אותו.

אַלגוֹרִיתְם

• צור מערך דו מימדי עם n + 1 שורות ו w + 1 עמודות. מספר שורה נ מציין את קבוצת הפריטים מ -1 עד אניומספר עמודה w מציין את יכולת הנשיאה המרבית של התיק.
• הערך המספרי ב- [i] [j] מציין את הערך הכולל של פריטים עד אני בתיק שיכול לשאת משקל מקסימלי של j.
• בכל קואורדינטות [i] [j] במערך בחר את הערך המקסימלי שנוכל להשיג בלעדיו פריט i, או הערך המקסימלי שאנו יכולים להשיג איתו פריט iהגדול מביניהם.
• הערך המקסימלי להשגה על ידי הכללת פריט i הוא סכום הפריט אני את עצמו ואת הערך המקסימלי שניתן להשיג עם היכולת הנותרת של הכנאפה.
• בצע שלב זה עד שתמצא את הערך המקסימלי עבור ה- W^ה שׁוּרָה.

קוד

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-weights [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, איפה k זה פחות מ אני. זה בעצם בודק את כל המערך עד i-1 כדי למצוא את המספר המינימלי של מטבעות שאנחנו יכולים להשתמש בהם.
• אם הערך בכלל מערך [i-k] + 1 הוא פחות מהערך הקיים ב- מערך [i], החלף את הערך ב- מערך [i] עם זה ב מערך [i-k] +1.

קוד

def מטבע_חלף (d, סכום, k):
מספרים = [0] * (סכום + 1)
עבור j בטווח (1, כמות + 1):
מינימום = סכום
עבור i בטווח (1, k + 1):
אם (j> = d [i]):
מינימום = מינימום (מינימום, מספרים 1 + [j-d [i]])
מספרים [j] = מינימום
החזר מספרים [סכום]

3. פיבונאצ'י

הצהרת בעיה

סדרת פיבונאצ'י היא רצף של מספרים שלמים כאשר המספר השלם הבא בסדרה הוא סכום השניים הקודמים.

זה מוגדר על ידי הקשר הרקורסיבי הבא: F (0) = 0, F (n) = F (n-1) + F (n-2), איפה F (n) האם ה- n^ה טווח. בבעיה זו עלינו ליצור את כל המספרים ברצף פיבונאצ'י עד n נתון^ה טווח.

אַלגוֹרִיתְם

• ראשית, השתמש בגישה רקורסיבית כדי ליישם את יחס ההישנות הנתון.
• פתרון רקורטיבי של בעיה זו כרוך בפירוק F (n) לְתוֹך F (n-1) + F (n-2)ואז להתקשר לפונקציה עם F (n-1) ו F (n + 2) כפרמטרים. אנו עושים זאת עד למקרי הבסיס שבהם n = 0, או n = 1 מושגים.
• כעת אנו משתמשים בטכניקה הנקראת memoization. אחסן את התוצאות של כל שיחות הפונקציה במערך. זה יבטיח כי לכל n, F (n) צריך לחשב רק פעם אחת.
• עבור כל החישובים הבאים, ניתן פשוט לאחזר את הערך שלו מהמערך בזמן קבוע.

קוד

def (n): 
fibNums = [0, 1] 
עבור i בטווח (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
החזר fibNums [n] 

4. המשך הגדל הארוך ביותר

הצהרת בעיה

מצא את אורך ההמשך המתגבר הארוך ביותר בתוך מערך נתון. המשך הגדל הארוך ביותר הוא המשך בתוך מערך מספרים עם סדר הולך וגדל. המספרים בהמשך צריכים להיות ייחודיים ובסדר עולה.

כמו כן, פריטי הרצף אינם צריכים להיות רצופים.

אַלגוֹרִיתְם

• התחל בגישה רקורסיבית שבה אתה מחשב את ערך ההמשך הארוך ביותר של כל מערך משנה אפשרי ממדד אפס לאינדקס i, כאשר אני קטן או שווה לגודל ה- מַעֲרָך.
• כדי להפוך שיטה זו לשיטה דינמית, צור מערך לאחסון הערך לכל המשך. ראשית את כל הערכים של מערך זה ל- 0.
• כל אינדקס אני של מערך זה תואם את אורכו של המשך הגדל הארוך ביותר למערך משנה בגודל אני.
• עכשיו, לכל שיחה רקורסיבית של findLIS (arr, n), בדוק את ה נ^ה אינדקס המערך. אם ערך זה הוא 0, אז חישב את הערך בשיטה בשלב הראשון ושמור אותו ב- נ^ה אינדקס.
• לבסוף, החזר את הערך המרבי מהמערך. זהו אורכו של המשך הגדל הארוך ביותר בגודל נתון נ.

קוד

def findLIS (myArray):
n = len (myArray)
ליס = [0] * n
עבור i בטווח (1, n):
עבור j בטווח (0, i):
אם myArray [i]> myArray [j] ו- lis [i] ליס [i] = ליס [j] +1
maxVal = 0
עבור אני בטווח (n):
maxVal = max (maxVal, lis [i])
החזר maxVal

פתרונות לבעיות תכנות דינמיות

כעת לאחר שעברתם כמה מבעיות התכנות הדינמיות הפופולריות ביותר, הגיע הזמן לנסות ליישם את הפתרונות בעצמכם. אם אתה תקוע, אתה תמיד יכול לחזור ולהתייחס לסעיף האלגוריתם לכל בעיה לעיל.

לאור כמה טכניקות פופולריות כמו רקורסיות ותכנות דינמי כיום, לא יזיק לבדוק כמה פלטפורמות פופולריות בהן תוכלו ללמוד מושגים כאלה לחדד את כישורי הקידוד שלך. אמנם ייתכן שלא תתקל בבעיות אלה על בסיס יומי, אך בוודאי תיתקל בהן בראיון טכני.

מטבע הדברים, הידע של בעיות נפוצות חייב לשלם דיבידנד כשאתה הולך לראיון הבא שלך. אז תפתח את שלך IDE מועדף, והתחל!

9 ערוצי ה- YouTube הטובים ביותר ללימוד תכנות

מוכן להתחיל קידוד? ערוצי YouTube אלה הם דרך נהדרת להתחיל במשחק, אפליקציה, אינטרנט ופיתוח אחר.

על הסופר