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

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

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

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

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

m：=1e9+7

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

返回（amodm+bmodm）modm

定义一个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：=定义一个大小为2x（x+1）的2D数组，并用0填充

dp[0，0]：=1

n：=arrLen

对于初始化i：=1，当i<=步骤时，更新（将i增加1），-

x：=(i-1)mod2

y：=我mod2

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），请执行-

returndp[stepsmod2，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