arrLen 크기의 배열이 있고 해당 배열의 인덱스 0에 포인터도 있다고 가정합니다. 각 단계에서 배열에서 왼쪽으로 1칸, 오른쪽으로 1칸 이동하거나 같은 위치에 머물 수 있습니다.
이제 두 개의 정수 단계와 rrLen이 있다고 가정하고 포인터가 정확한 단계 후에 여전히 인덱스 0에 있도록 하는 방법의 수를 찾아야 합니다. 답이 매우 크면 모듈로 10^9 + 7을 반환합니다.
따라서 입력이 단계 =3, arrLen =2와 같으면 3단계 후에 인덱스 0을 유지하는 4가지 다른 방법이 있으므로 출력은 4가 됩니다. [Right, Left, Stay], [Stay, Right, Left], [Right, Stay, Left], [Stay, Stay, Stay]입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
m :=1e9 + 7
-
add() 함수를 정의하면, b,
-
return (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
-
ans :=add(ans, solve(n, x - 1, pos + 1))
-
-
ans :=add(ans, solve(n, x - 1, pos))
-
dp[pos, n] :=ans
-
반환
-
주요 방법에서 다음을 수행하십시오 -
-
x :=arrLen 및 단계의 최소값 / 2 + 1
-
dp :=크기가 2 x (x + 1)인 2D 배열 하나를 정의하고 0으로 채웁니다.
-
dp[0, 0] :=1
-
n :=arrLen
-
initialize i :=1의 경우, i <=단계일 때 업데이트(i 1만큼 증가), 수행 -
-
j 초기화의 경우:=0, j
-
x :=(i - 1) 모드 2
-
y :=i 모드 2
-
dp[y, j] :=dp[x, j]
-
j - 1>=0이면 -
-
dp[y, j] :=add(dp[y, j], dp[x, j - 1])
-
-
j + 1
-
dp[y, j] :=add(dp[y, j], dp[x, j + 1])
-
-
-
-
반환 dp[단계 모드 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