ספרו דרכים להגיע למדרגות התשיעיות באמצעות שלב 1, 2 או 3


רמת קושי קַל
נשאל לעתים קרובות אמזון בעברית CodeNation GE Healthcare מיקרוסופט מעבדות מונפרוג פייפאל סופר
קומבינטורי תכנות דינמי

הבעיה "ספרו דרכים להגיע למדרגות התשיעיות באמצעות שלב 1, 2 או 3" קובעת שאתם עומדים על הקרקע. עכשיו אתה צריך להגיע לקצה גרם המדרגות. אז כמה דרכים יש להגיע לסוף אם אתה יכול לקפוץ רק צעד אחד, 1 או 2?

דוגמה

ספרו דרכים להגיע למדרגות התשיעיות באמצעות שלב 1, 2 או 3

2
2

הסבר

ישנן שתי דרכים כיוון שאנו נגיע ישירות למדרגה השנייה ישירות מהאדמה או תחילה נגיע למדרגות 2 ואז מתקדם.

גישה

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

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

בפתרון התכנות הדינמי אנו רואים כי אנו עומדים בשלב ה- I. ואז מספר הדרכים להגיע לשלב זה הוא משלב i-1, שלב i-2 או שלב i-3. אז באופן פורמלי, דרכים [i] = דרכים [i-1] + דרכים [i-2] + דרכים [i-3], באמצעות הנוסחה הרקורסיבית הזו. נפתור את הבעיה שלנו.

קופונים

קוד C ++ לספירת דרכים להגיע למדרגות התשיעיות באמצעות שלב 1, 2 או 3

#include<bits/stdc++.h>
using namespace std;

int main(){
    int n;cin>>n;
    int dp[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }
    cout<<dp[n];
}
5
13

קוד Java לספירת דרכים להגיע למדרגות התשיעיות באמצעות שלב 1, 2 או 3

import java.util.*;
class Main{
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
  int n = sc.nextInt();
    int dp[] = new int[n+1];
    // base case
    dp[0] = 1;
    for(int i=1;i<=n;i++){
        dp[i] = ((i-1)>=0 ? dp[i-1] : 0) +
                ((i-2)>=0 ? dp[i-2] : 0) +
                ((i-3)>=0 ? dp[i-3] : 0);
    }

    System.out.print(dp[n]);
  }
}
5
13

ניתוח מורכבות

מורכבות זמן

O (N) כי אנחנו צריכים להפעיל לולאה עד לשלב התשיעי. אז מבחינת תכנות דינמי, היה לנו מצב יחיד שנע בין 0 ל n ועלות המעבר היא O (1). לפיכך מורכבות הזמן היא לינארית.

מורכבות בחלל

O (N) מכיוון שעלינו ליצור מערך DP 1-D. מורכבות החלל של הפתרון היא לינארית.