在C ++中经过一些步骤后留在同一地方的方法数量
现在假设我们有两个整数步长和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