C++でいくつかの手順を実行した後も同じ場所にとどまる方法の数

サイズarrLenの配列があり、その配列のインデックス0にもポインタがあるとします。各ステップで、アレイ内で1つの位置を左に移動するか、1つの位置を右に移動するか、同じ場所にとどまることができます。

ここで、2つの整数ステップとarrLenがあるとすると、正確なステップの後もポインターがインデックス0に留まるような方法の数を見つける必要があります。答えが非常に大きい場合は、10 ^ 9+7を法として返します。

したがって、入力がsteps =3、arrLen =2のような場合、出力は4になります。これは、3つのステップの後でインデックス0に留まる4つの異なる方法があるためです。これらは、[右、左、滞在]、[滞在、右、左]、[右、滞在、左]、[滞在、滞在、滞在]です。

これを解決するには、次の手順に従います-

• m：=1e9 + 7

• 関数add（）を定義します。これには、a、b、

  が必要です。

• return（a mod m + b mod m）mod m

• 1つの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

  • ans：=add（ans、solve（n、x --1、pos + 1））

• ans：=add（ans、solve（n、x --1、pos））

• dp [pos、n]：=ans

• ansを返す

• メインの方法から、次のようにします-

• x：=arrLenとステップの最小値/2 + 1

• dp：=サイズ2 x（x + 1）の2D配列を1つ定義し、これに0を入力します

• dp [0、0]：=1

• n：=arrLen

• 初期化i：=1の場合、i <=ステップの場合、更新（iを1増やします）、実行-

  • 初期化j：=0の場合、j

    • x：=（i-1）mod 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]）

• dp [steps mod 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