चरण 1, 2 किंवा 3 चा वापर करुन नवव्या पायर्‍यावर जाण्याचे मार्ग मोजा


अडचण पातळी सोपे
वारंवार विचारले ऍमेझॉन कोडनेशन जीई हेल्थकेअर मायक्रोसॉफ्ट मूनफ्रोग लॅब पोपल उबेर
एकत्रित डायनॅमिक प्रोग्रामिंग

"चरण 1, 2, किंवा 3 चा वापर करून नवव्या पायर्‍यापर्यंत जाण्याचे मार्ग मोजा" या समस्येमध्ये असे म्हटले आहे की आपण जमिनीवर उभे आहात. आता आपल्याला पायर्याच्या शेवटी पोहोचण्याची आवश्यकता आहे. तर मग आपण फक्त 1, 2 किंवा 3 चरणावर उडी मारू शकता तर शेवटपर्यंत पोहोचण्याचे किती मार्ग आहेत?

उदाहरण

चरण 1, 2 किंवा 3 चा वापर करुन नवव्या पायर्‍यावर जाण्याचे मार्ग मोजा

2
2

स्पष्टीकरण

तेथे 2 मार्ग आहेत कारण एकतर आपण थेट जमिनीपासून थेट दुस step्या पायरीवर पोहोचतो किंवा प्रथम आपण पहिल्या पायर्‍यावर पोहोचतो नंतर पुढे जा.

दृष्टीकोन

पायर्‍याच्या शेवटच्या टोकापर्यंत पोहोचण्याचे एकूण वेगवेगळे मार्ग जसे आपण जमिनीपासून सुरू करतो तेव्हा समस्या आम्हाला विचारते. तर पायर्‍या 2 पाय 2्या आहेत याचा विचार करा. मग तेथे 2 संभाव्य मार्ग आहेत, एकतर आपण थेट 1 रा पायरीवर किंवा पहिल्या चरणात 2 चरण आणि नंतर 1 रा. त्याचप्रमाणे, चरण 2, 3 किंवा XNUMX वापरून आपण नवव्या पाय st्यापर्यंत पोहोचण्याचे मार्ग मोजणे आवश्यक आहे.

एक भोळे दृष्टिकोन म्हणजे सर्व शक्य मार्ग निर्माण करणे आणि नंतर त्या मोजणे. परंतु हा दृष्टीकोन वेळ घेणारा असेल. अशा प्रकारे वेळेची जटिलता कमी करण्यासाठी आपण काही भिन्न मार्गांनी विचार केला पाहिजे. आपण भोळसट दृष्टिकोनातून चर्चा केलेली पद्धत अ रिकर्सिव निराकरण जेथे आपण 0 व्या चरणातून प्रारंभ करू शकता. नंतर प्रत्येक रिकर्सिव्ह कॉलमध्ये, i + 1, i + 2 आणि i + 3 वर जा. जेव्हा आपण नवव्या पायर्‍यावर वाढता तेव्हा काउंटर वाढवा. या मार्गाने शेवटी काउंटरने नवव्या पायरीपर्यंत पोहोचण्याचे अनेक मार्ग साठवले. परंतु ही पद्धत पुन्हा पुन्हा पुन्हा त्याच समस्यांची पुनरावृत्ती करते. म्हणून आम्ही वापरत असलेल्या या सोल्यूशनला ऑप्टिमाइझ करण्यासाठी डायनॅमिक प्रोग्रामिंग.

डायनॅमिक प्रोग्रामिंग सोल्यूशनमध्ये आम्ही विचार करतो की आम्ही ith स्टेपवर उभे आहोत. तर आयथ पायर्‍यावर जाण्याचे मार्ग i-1 चरण, i-2 चरण किंवा i-3 चरणाचे आहेत. औपचारिकरित्या, हे रिकर्सिव सूत्र वापरुन, मार्ग [i] = मार्ग [i-1] + मार्ग [i-2] + मार्ग [i-3]. आम्ही आमची समस्या सोडवू.

कोड

चरण 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

पायरी 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

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आपल्याला नवव्या पायरीपर्यंत पळवाट चालवावी लागेल. तर डायनॅमिक प्रोग्रामिंगच्या बाबतीत आमच्याकडे 0 ते n पर्यंतचे एकच राज्य होते आणि संक्रमण खर्च ओ (1) आहे. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), आम्हाला 1-DP अ‍ॅरे तयार करण्याची आवश्यकता आहे. द्रावणाची जागा अवघड असते.