ডেলানয় নাম্বার (Delannoy Numbers) কী? C++-এ প্রোগ্রাম

ডেলানয় নাম্বার D(a,b) = (০,০) থেকে (a,b) পর্যন্ত রেক্ট্যাঙ্গুলার গ্রিডে ইস্ট (→), নর্থ-ইস্ট (↗), নর্থ (↑) স্টেপ নিয়ে পাওয়ার পথের সংখ্যা।

রিকারেন্স রিলেশন

D(a,b) = D(a-1,b) + D(a,b-1) + D(a-1,b-1)
Base: D(0,0) = 1, D(a,0) = 1, D(0,b) = 1

উদাহরণ

D(3,3) = 63

উদাহরণ কোড (রিকার্সিভ + মেমোইজেশন)

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

int delannoy(int a, int b, vector<vector<int>>& memo) {
    if (a == 0 || b == 0) return 1;
    if (memo[a][b] != -1) return memo[a][b];
    return memo[a][b] = delannoy(a-1, b, memo) + 
                        delannoy(a, b-1, memo) + 
                        delannoy(a-1, b-1, memo);
}

int main() {
    int a = 3, b = 3;
    vector<vector<int>> memo(a+1, vector<int>(b+1, -1));
    cout << delannoy(a, b, memo) << endl; // 63
    return 0;
}

আউটপুট

মেমোইজেশন ছাড়া রিকার্সিভ করতে এক্সপোনেনশিয়াল টাইম লাগবে। DP বা মেমোইজেশন ব্যবহার করুন।