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