Stern's Diatomic Series-এর nth টার্ম (C++)

Stern's Diatomic Series (fusc function): 0,1,1,2,1,3,2,3,1,4,3,5,2,5,3,4,...

রিকারেন্স: p(n) = p(n/2) যদি n জোড়, p(n) = p((n-1)/2) + p((n+1)/2) যদি n বিজোড়। p(0)=0, p(1)=1।

ডাইনামিক প্রোগ্রামিং দিয়ে টেবিল বানিয়ে O(n) এ বের করুন।

উদাহরণ

#include <iostream>
using namespace std;

int findTerm(int n) {
    vector<int> table(n+1);
    table[0] = 0; table[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (i % 2 == 0) table[i] = table[i/2];
        else table[i] = table[(i-1)/2] + table[(i+1)/2];
    }
    return table[n];
}

int main() {
    cout << "3rd term: " << findTerm(3) << endl;
    cout << "15th term: " << findTerm(15) << endl;
    cout << "20th term: " << findTerm(20) << endl;
    return 0;
}

আউটপুট

3rd term: 2
15th term: 4
20th term: 3