C++ এ কিছু ধাপের পর একই জায়গায় থাকার উপায়ের সংখ্যা

ধরুন একটি অ্যারে আকারের arrLen আছে, এবং সেই অ্যারেতে আমাদের ইনডেক্স 0-এ একটি পয়েন্টারও আছে। প্রতিটি ধাপে, আমরা অ্যারেতে 1টি অবস্থান বাম দিকে, 1টি অবস্থান ডানদিকে সরাতে পারি বা একই জায়গায় থাকতে পারি।

এখন ধরুন আমাদের দুটি পূর্ণসংখ্যার ধাপ এবং arrLen আছে, আমাদেরকে এমন উপায়ের সংখ্যা খুঁজে বের করতে হবে যাতে পয়েন্টারটি ঠিক ধাপের পরেও সূচক 0-এ থাকে। যদি উত্তরটি খুব বড় হয় তবে এটি মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি ধাপ =3, arrLen =2 এর মত হয়, তাহলে আউটপুট 4 হবে, কারণ 3টি ধাপের পরে সূচক 0 এ থাকার জন্য 4টি ভিন্ন উপায় রয়েছে। এগুলি হল [ডান, বাম, থাকুন], [থান, ডান, বাম], [ডান, থাকুন, বাম], [থাক, থাকুন, থাকুন]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• m :=1e9 + 7

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• রিটার্ন (a mod m + b mod m) mod m

• একটি 2D অ্যারে ডিপি

  সংজ্ঞায়িত করুন

• একটি ফাংশন solve() সংজ্ঞায়িত করুন, এটি n, x, pos 0 দিয়ে আরম্ভ করবে,

• যদি x 0 এর সমান হয়, তাহলে −

  • 0

    এর মত পোস হলে true রিটার্ন করুন

• যদি dp[pos, n] -1 এর সমান না হয়, তাহলে −

  • dp[pos, n]

    ফেরত দিন

• উত্তর :=0

• যদি pos> 0 হয়, তাহলে

  • ans :=add(ans, solve(n, x - 1, pos - 1))

• যদি pos

  • ans :=add(ans, solve(n, x - 1, pos + 1))

• ans :=add(ans, solve(n, x - 1, pos))

• dp[pos, n] :=ans

• উত্তর ফেরত দিন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• x :=ন্যূনতম arrLen এবং ধাপ / 2 + 1

• dp :=2 x (x + 1) আকারের একটি 2D অ্যারে সংজ্ঞায়িত করুন, এটি 0 দিয়ে পূরণ করুন

• dp[0, 0] :=1

• n :=আরলেন

• আরম্ভ করার জন্য i :=1, যখন i <=ধাপ, আপডেট (i 1 দ্বারা বৃদ্ধি), −

  • আরম্ভ করার জন্য j :=0, যখন j <ন্যূনতম arrLen এবং step/2 + 1, আপডেট করুন (j 1 দ্বারা বাড়ান), করবেন −

    • x :=(i - 1) মোড 2

    • y :=i mod 2

    • dp[y, j] :=dp[x, j]

    • যদি j - 1>=0 হয়, তাহলে −

      • dp[y, j] :=add(dp[y, j], dp[x, j - 1])

    • যদি j + 1

      • dp[y, j] :=add(dp[y, j], dp[x, j + 1])

• ডিপি [স্টেপ মোড 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