मान लीजिए हमारे पास तीन पूर्णांक n, m, और k हैं। यदि हमारे पास एक धनात्मक पूर्णांकों के ऐरे के अधिकतम तत्व को खोजने के लिए निम्नलिखित एल्गोरिदम है −
max_val := -1 max_ind := -1 search_cost := 0 n := size of arr for initialize i := 0, when i < n, update (increase i by 1), do: if max_val < arr[i], then: max_val := arr[i] max_ind := i (increase search_cost by 1) return max_ind
हमें ऐरे arr बनाना है जिसमें निम्नलिखित मानदंड हों: arr में ठीक n पूर्णांक हों। सभी तत्व arr[i] 1 से m की सीमा में हों (सम्मिलित) (0 <= i < n)। उपरोक्त एल्गोरिदम को arr पर लागू करने के बाद, search_cost का मान k के बराबर हो। हमें उल्लिखित शर्तों के तहत ऐरे arr बनाने के तरीकों की संख्या ढूंढनी है। उत्तर बहुत बड़ा हो सकता है इसलिए इसे मॉड्यूलो 10^9 + 7 पर गणना की जाएगी।
तो, यदि इनपुट n = 2, m = 3, k = 1 है, तो आउटपुट 6 होगा क्योंकि संभावित ऐरे हैं [1, 1], [2, 1], [2, 2], [3, 1], [3, 2] [3, 3]
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
m := 10^9 + 7
एक फ़ंक्शन add() परिभाषित करें, जो a, b लेगा,
((a mod m) + (b mod m)) mod m लौटाएं
आकार 54 x 54 x 105 का एक ऐरे dp परिभाषित करें।
एक फ़ंक्शन help() परिभाषित करें, जो idx, m, k, currVal, n लेगा,
यदि k < 0, तो −
0 लौटाएं
यदि idx, n + 1 के समान है, तो −
तब true लौटाएं जब k 0 हो
यदि dp[idx, k, currVal + 1], -1 के बराबर नहीं है, तो −
dp[idx, k, currVal + 1] लौटाएं
ret := 0
i := 1 से आरंभ करें, जब i <= m, अद्यतन करें (i को 1 से बढ़ाएं), करें −
यदि i > currVal, तो −
ret := add(help(idx + 1, m, k - 1, max(currVal,i), n), ret)
अन्यथा
ret := add(help(idx + 1, m, k, max(currVal,i), n), ret)
dp[idx, k, currVal + 1] = ret लौटाएं
मुख्य विधि से निम्नलिखित करें −
i := 0 से आरंभ करें, जब i < 54, अद्यतन करें (i को 1 से बढ़ाएं), करें −
j := 0 से आरंभ करें, जब j < 54, अद्यतन करें (j को 1 से बढ़ाएं), करें −
k := 0 से आरंभ करें, जब k < 105, अद्यतन करें (k को 1 से बढ़ाएं), करें −
dp[i, j, k] := -1
ret := help(1, m, k, -1, n)
ret लौटाएं
उदाहरण
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
#include <bits/stdc++.h> using namespace std; typedef long long int lli; const lli m = 1e9 + 7; class Solution { public: lli add(lli a, lli b) { return ((a % m) + (b % m)) % m; } int dp[54][54][105]; int help(int idx, int m, int k, int currVal, int n) { if (k < 0) return 0; if (idx == n + 1) { return k == 0; } if (dp[idx][k][currVal + 1] != -1) return dp[idx][k][currVal + 1]; int ret = 0; for (int i = 1; i <= m; i++) { if (i > currVal) { ret = add(help(idx + 1, m, k - 1, max(currVal, i), n), ret); } else { ret = add(help(idx + 1, m, k, max(currVal, i), n), ret); } } return dp[idx][k][currVal + 1] = ret; } int numOfArrays(int n, int m, int k) { for (int i = 0; i < 54; i++) for (int j = 0; j < 54; j++) for (int k = 0; k < 105; k++) dp[i][j][k] = -1; int ret = help(1, m, k, -1, n); return ret; } }; main() { Solution ob; cout << (ob.numOfArrays(2, 3, 1)); }इनपुट
2, 3, 1
आउटपुट
6