C++ में 1, 2 या 3 चरण से nवीं सीढ़ी तक पहुंचने के तरीके

हमें सीढ़ियों की कुल संख्या n दी गई है। एक व्यक्ति अगली मंजिल तक 1, 2 या 3 चरण छोड़कर पहुंच सकता है। लक्ष्य है उन तरीकों की संख्या ज्ञात करना जिनसे अगली मंजिल तक पहुंचा जा सकता है।

हम रिकर्सिव विधि का उपयोग करेंगे: किसी भी i-वें चरण तक पहुंचने के लिए, व्यक्ति को i-1वें (1 चरण छोड़कर), i-2वें (2 चरण छोड़कर), या i-3वें (3 चरण छोड़कर) चरण से कूदना होगा।

इनपुट - N = 3 चरण

आउटपुट - nवीं सीढ़ी तक पहुंचने के तरीके: 4

व्याख्या - 3 चरण: 3 (सीधे), 1+2, 2+1, 1+1+1

उपयोग किया गया दृष्टिकोण (रिकर्सिव)

• यदि steps = 0: 1 तरीका वापस करें।
• यदि steps = 1: 1 तरीका।
• यदि steps = 2: 2 तरीके (1+1, 2)।
• अन्यथा: stairs_step(steps-3) + stairs_step(steps-2) + stairs_step(steps-1)

नोट: यह रिकर्सिव दृष्टिकोण घातीय समय लेता है। डायनामिक प्रोग्रामिंग (मेमोइजेशन या टेबुलेशन) से O(n) समय में हल किया जा सकता है।

उदाहरण (रिकर्सिव)

#include <iostream> 
using namespace std; 

int stairs_step(int steps) { 
    if (steps == 0) return 1; 
    else if (steps == 1) return 1; 
    else if (steps == 2) return 2; 
    else return stairs_step(steps-3) + stairs_step(steps-2) + stairs_step(steps-1); 
} 

int main() { 
    int steps = 5; 
    cout << "Count of ways to reach the nth stair using step 1, 2 or 3 are: " << stairs_step(steps); 
    return 0; 
}

आउटपुट

Count of ways to reach the nth stair using step 1, 2 or 3 are: 13

कुशल दृष्टिकोण (DP)

int countWays(int n) { 
    if (n <= 1) return 1; 
    if (n == 2) return 2; 
    vector<int> dp(n+1); 
    dp[0] = 1; dp[1] = 1; dp[2] = 2; 
    for (int i = 3; i <= n; i++) 
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]; 
    return dp[n]; 
}