# 1269. Number of Ways to Stay in the Same Place After Some Steps

You have a pointer at index `0` in an array of size `arrLen`. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers `steps` and `arrLen`, return the number of ways such that your pointer still at index `0` after exactly `steps` steps. Since the answer may be too large, return it modulo `109 + 7`.

Example 1:

``````Input: steps = 3, arrLen = 2
Output: 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay
``````

Example 2:

``````Input: steps = 2, arrLen = 4
Output: 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay
``````

Example 3:

``````Input: steps = 4, arrLen = 2
Output: 8
``````

Constraints:

• `1 <= steps <= 500`
• `1 <= arrLen <= 10^6`

``````class Solution {
public:
int numWays(int steps, int arrLen) {
int M = 1e9 + 7, n = min(steps, arrLen);
vector<long> last(n + 1);
last[0] = 1;
for (int i = 1; i <= steps; ++i) {
vector<long> cur(n + 1);
for (int j = 0; j < n; ++j) {
if (last[j] > 0) {
cur[j] = (cur[j] + last[j]) % M;
}
if (j + 1 < arrLen && last[j + 1] > 0) {
cur[j] = (cur[j] + last[j + 1]) % M;
}
if (j > 0 && last[j - 1] > 0) {
cur[j] = (cur[j] + last[j - 1]) % M;
}
}
last = cur;
}
return last[0];
}
};
``````

``````class Solution {
public:
int numWays(int steps, int arrLen) {
vector<vector<int>> memo(steps + 1, vector<int>(steps / 2 + 1));
return dfs(steps, arrLen, 0, memo);
}
int dfs(int steps, int arrLen, int i, vector<vector<int>>& memo) {
if (steps == 0 && i == 0) return 1;
if (i < 0 || i >= arrLen || steps == 0 || i > steps) return 0;
if (memo[steps][i] > 0) return memo[steps][i];
int M = 1e9 + 7;
return memo[steps][i] = ((dfs(steps - 1, arrLen, i + 1, memo) % M + dfs(steps - 1, arrLen, i - 1, memo)) % M + dfs(steps - 1, arrLen, i, memo)) % M;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1269

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/436117/C%2B%2B-Recursive-DP-(Memoization)

https://leetcode.com/problems/number-of-ways-to-stay-in-the-same-place-after-some-steps/discuss/436287/Step-by-Step-Solution-(diagrams)-(with-how-I-overcome-MemoryTime-limit-exception)

LeetCode All in One 题目讲解汇总(持续更新中…)

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation