在C ++中经过一些步骤后留在同一地方的方法数量

假设有一个大小为arrLen的数组,并且我们在该数组的索引0处也有一个指针。在每一步中,我们可以在数组中向左移动1个位置,向右移动1个位置,或保持在同一位置。

现在假设我们有两个整数步长和arrLen,我们必须找到方法的数量,以使指针在精确步长后仍位于索引0处。如果答案很大,则以10 ^ 9 + 7为模返回。

因此,如果输入的步长= 3,arrLen = 2,则输出将是4,因为经过3步后,有4种不同的方法保持索引0。这些是[右,左,停留],[停留,右,左],[右,停留,左],[停留,停留,停留]。

为了解决这个问题,我们将遵循以下步骤-

  • m:= 1e9 + 7

  • 定义一个函数add(),这将花费a,b,

  • 返回(a mod m + b mod m)mod m

  • 定义一个2D数组dp

  • 定义一个函数solve(),它将使用n,x,pos将其初始化为0,

  • 如果x等于0,则-

    • 当pos等于0时返回true

  • 如果dp [pos,n]不等于-1,则-

    • 返回dp [pos,n]

  • 回答:= 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:= arrLen和步长的最小值/ 2 +1

  • dp:=定义一个大小为2 x(x + 1)的2D数组,并用0填充

  • dp [0,0]:= 1

  • n:= arrLen

  • 对于初始化i:= 1,当i <=步骤时,更新(将i增加1),-

    • x:=(i-1)mod 2

    • y:=我mod 2

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

    • 如果j-1> = 0,则-

    • 如果j + 1 <n,则-

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

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

    • 对于初始化j:= 0,当j <arrLen的最小值并且step / 2 + 1时,更新(将j增加1),请执行-

    • return 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