मान लीजिए arrLen आकार की एक सरणी है, और हमारे पास उस सरणी में इंडेक्स 0 पर एक पॉइंटर है। प्रत्येक चरण में, हम सरणी में 1 स्थिति बाएं, 1 स्थिति दाएं जा सकते हैं या उसी स्थान पर रह सकते हैं।
अब मान लीजिए हमारे पास दो पूर्णांक steps और arrLen हैं, हमें उन तरीकों की संख्या ज्ञात करनी है जैसे कि पॉइंटर ठीक steps के बाद इंडेक्स 0 पर ही रहे। यदि उत्तर बहुत बड़ा है तो इसे मॉड्यूलो 10^9 + 7 पर लौटाएं।
यदि इनपुट steps = 3, arrLen = 2 है, तो आउटपुट 4 होगा, क्योंकि 3 चरणों के बाद इंडेक्स 0 पर रहने के 4 अलग-अलग तरीके हैं। ये हैं [दाएं, बाएं, रहें], [रहें, दाएं, बाएं], [दाएं, रहें, बाएं], [रहें, रहें, रहें]।
हल करने के चरण
m := 10^9 + 7
add() फ़ंक्शन परिभाषित करें: (a % m + b % m) % m लौटाएं
एक 2D सरणी dp परिभाषित करें
solve() फ़ंक्शन परिभाषित करें जो n, x, pos (0 से आरंभ) लेता है
यदि x == 0 तो pos == 0 होने पर true लौटाएं
यदि dp[pos][n] != -1 तो dp[pos][n] लौटाएं
ans := 0, यदि pos > 0 तो ans = add(ans, solve(n, x-1, pos-1))
यदि pos < n-1 तो ans = add(ans, solve(n, x-1, pos+1))
ans = add(ans, solve(n, x-1, pos)), dp[pos][n] = ans, ans लौटाएं
मुख्य विधि से: x = min(arrLen, steps/2 + 1), dp आरंभ करें, पुनरावर्ती DP से उत्तर की गणना करें
उदाहरण
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
const int MOD = 1e9 + 7;
lli add(lli a, lli b) {
return (a % MOD + b % MOD) % MOD;
}
class Solution {
public:
vector<vector<int> > dp;
int solve(int n, int x, int pos = 0) {
if (x == 0) return pos == 0;
if (dp[pos][n] != -1) return dp[pos][n];
int ans = 0;
if (pos > 0) ans = add(ans, solve(n, x - 1, pos - 1));
if (pos < n - 1) ans = add(ans, solve(n, x - 1, pos + 1));
ans = add(ans, solve(n, x - 1, pos));
dp[pos][n] = ans;
return ans;
}
int numWays(int steps, int arrLen) {
int x = min(arrLen, steps / 2 + 1);
this->dp = vector<vector<int> >(2, vector<int>(x + 1, 0));
dp[0][0] = 1;
int n = arrLen;
for (int i = 1; i <= steps; i++) {
for (int j = 0; j < min(arrLen, steps / 2 + 1); j++) {
int x = (i - 1) % 2;
int y = i % 2;
dp[y][j] = dp[x][j];
if (j - 1 >= 0) dp[y][j] = add(dp[y][j], dp[x][j - 1]);
if (j + 1 < n) dp[y][j] = add(dp[y][j], dp[x][j + 1]);
}
}
return dp[steps % 2][0];
}
};
int main() {
Solution ob;
cout << (ob.numWays(3, 2));
return 0;
}
इनपुट
3, 2
आउटपुट
4