عد الطرق للوصول إلى الدرجة التاسعة باستخدام الخطوة 1 أو 2 أو 3  


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون CodeNation جنرال إلكتريك للرعاية الصحية Microsoft مختبرات Moonfrog Paypal اوبر
اندماجي البرمجة الديناميكية

توضح مشكلة "عد الطرق للوصول إلى الدرجة التاسعة باستخدام الخطوة 1 أو 2 أو 3" أنك تقف على الأرض. أنت الآن بحاجة للوصول إلى نهاية الدرج. إذن ما عدد الطرق المتاحة للوصول إلى النهاية إذا كان بإمكانك القفز خطوة واحدة أو خطوتين أو ثلاث خطوات فقط؟

مثال  

عد الطرق للوصول إلى الدرجة التاسعة باستخدام الخطوة 1 أو 2 أو 3

2
2

تفسير

هناك طريقتان لأننا إما نصل مباشرة إلى الخطوة الثانية مباشرة من الأرض أو نصل أولاً إلى الدرجة الأولى ثم نتقدم للأمام.

الرسالة  

تطلب منا المشكلة العدد الإجمالي للطرق المختلفة للوصول إلى نهاية الدرج بحيث نبدأ من الأرض. لذلك ضع في اعتبارك أن الدرج يتكون من خطوتين. ثم هناك طريقتان محتملتان ، إما أن تنتقل مباشرة إلى الخطوة الثانية أو الخطوة الأولى إلى الخطوة الأولى ثم إلى الثانية. وبالمثل ، نحتاج إلى حساب طرق الوصول إلى الدرجة التاسعة باستخدام الخطوات 2 أو 2 أو 2.

النهج الساذج هو إنشاء كل الطرق الممكنة ثم عدها. لكن هذا النهج سيستغرق وقتًا طويلاً. وبالتالي لتقليل تعقيد الوقت ، يجب أن نفكر في بعض الطرق المختلفة. الطريقة التي ناقشناها في النهج الساذج هي أ العودية الحل حيث يمكنك البدء من الخطوة 0. ثم في كل مكالمة متكررة ، انتقل إلى الخطوة i + 1 و i + 2 و i + 3. عندما تصل إلى الخطوة n ، قم بزيادة العداد. بهذه الطريقة في النهاية ، يخزن العداد عدد الطرق للوصول إلى الخطوة التاسعة. لكن هذه الخطوة تعيد حساب نفس المشكلات مرارًا وتكرارًا. لتحسين هذا الحل نستخدمه البرمجة الديناميكية.

انظر أيضا
الحد الأقصى لمنتج لاحق متزايد

في حل البرمجة الديناميكية ، نعتبر أننا نقف في الخطوة الأولى. ثم يكون عدد طرق الوصول إلى ith step من i-1 step أو i-2 step أو i-3 step. من الناحية الرسمية ، الطرق [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) لأننا نحتاج إلى إنشاء مجموعة 1-D DP. التعقيد المكاني للحل خطي.