সিঁড়ি চড়া পদ্ধতি গণনা (১, ২, ৩ ধাপ) C++-এ

n ধাপের একটি সিঁড়ি দেওয়া থাকলে, প্রতিবার ১, ২ বা ৩ ধাপ চড়া যেতে পারে। শীর্ষে পৌঁছানোর মোট কতটি পদ্ধতি আছে তা বের করতে হবে।

উদাহরণ

n = 3

পদ্ধতিগুলো: 1+1+1, 1+2, 2+1, 3 → মোট 4টি

n = 5 → মোট 13টি

অ্যালগরিদম

1. রিকারসিভ (O(3^n)): f(n) = f(n-1) + f(n-2) + f(n-3) with base cases f(0)=1, f(1)=1, f(2)=2
2. ডাইনামিক প্রোগ্রামিং (O(n)): বটম-আপ বা মেমোইজেশন ব্যবহার করুন।

C++ কোড উদাহরণ (দুই পদ্ধতি)

#include <iostream>
#include <vector>
using namespace std;

// Recursive with memoization
int countWaysMemo(int n, vector& dp) {
    if (n < 0) return 0;
    if (n == 0) return 1;
    if (dp[n] != -1) return dp[n];
    return dp[n] = countWaysMemo(n-1, dp) + countWaysMemo(n-2, dp) + countWaysMemo(n-3, dp);
}

// Bottom-up DP
int countWaysDP(int n) {
    if (n <= 1) return 1;
    if (n == 2) return 2;
    
    vector 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];
}

int main() {
    int n = 5;
    vector dp(n+1, -1);
    cout << "Memo: " << countWaysMemo(n, dp) << endl;
    cout << "DP: " << countWaysDP(n);
    return 0;
}

ইনপুট

5

আউটপুট

13