এই টিউটোরিয়ালে আমরা প্রোডাক্ট K-এর চেয়ে কম হয় এমন সাবসিকোয়েন্সের সংখ্যা বের করার প্রোগ্রাম নিয়ে আলোচনা করব।
এই জন্য আমাদের একটি নন-নেগেটিভ অ্যারে এবং একটি k ভ্যালু দেওয়া থাকবে। আমাদের কাজ হলো অ্যারেতে যেসব সাবসিকোয়েন্সের প্রোডাক্ট k-এর চেয়ে কম, সেগুলো বের করা।
উদাহরণ
#include <bits/stdc++.h> using namespace std; //counting subsequences with product //less than k int count_sub(vector<int> &arr, int k){ int n = arr.size(); int dp[k + 1][n + 1]; memset(dp, 0, sizeof(dp)); for (int i = 1; i <= k; i++) { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i][j - 1]; if (arr[j - 1] <= i && arr[j - 1] > 0) dp[i][j] += dp[i/arr[j-1]][j-1] + 1; } } return dp[k][n]; } int main(){ vector<int> A; A.push_back(1); A.push_back(2); A.push_back(3); A.push_back(4); int k = 10; cout << count_sub(A, k) << endl; }আউটপুট
11
