ধরি arrLen আকারের একটি অ্যারে এবং ইন্ডেক্স 0-এ একটি পয়েন্টার আছে। প্রতিটি স্টেপে বামে, ডানে বা একই জায়গায় থাকা যায়। steps এবং arrLen দেওয়া থাকলে steps স্টেপ পর পয়েন্টার ইন্ডেক্স 0-এ থাকার পথ সংখ্যা বের করতে হবে (মডুলো 10^9+7)।
steps=3, arrLen=2 হলে আউটপুট 4।
সমাধানের ধাপসমূহ
MOD := 1e9+7, add() ফাংশন মডুলো যোগ করার জন্য
DP টেবিল: dp[2][x+1] যেখানে x = min(arrLen, steps/2+1)
dp[0][0] = 1
i := 1 থেকে steps পর্যন্ত – j := 0 থেকে min(arrLen, steps/2+1) পর্যন্ত DP ট্রানজিশন করুন
dp[steps%2][0] ফেরত দিন
বेहतर বোঝার জন্য নিচের কোডটি দেখুন –
উদাহরণ
#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]; } }; main(){ Solution ob; cout << (ob.numWays(3,2)); }ইনপুট
3, 2
আউটপুট
4
