假设有一个大小为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