Skip to content

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

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
 public:
  int numWays(int steps, int arrLen) {
    constexpr int kMod = 1'000'000'007;
    const int n = min(arrLen, steps / 2 + 1);
    // dp[i] := the number of ways to stay at index i
    vector<long> dp(n);
    dp[0] = 1;

    while (steps-- > 0) {
      vector<long> newDp(n);
      for (int i = 0; i < n; ++i) {
        newDp[i] = dp[i];
        if (i - 1 >= 0)
          newDp[i] += dp[i - 1];
        if (i + 1 < n)
          newDp[i] += dp[i + 1];
        newDp[i] %= kMod;
      }
      dp = std::move(newDp);
    }

    return dp[0];
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
  public int numWays(int steps, int arrLen) {
    final int kMod = 1_000_000_007;
    final int n = Math.min(arrLen, steps / 2 + 1);
    // dp[i] := the number of ways to stay at index i
    long[] dp = new long[n];
    dp[0] = 1;

    while (steps-- > 0) {
      long[] newDp = new long[n];
      for (int i = 0; i < n; ++i) {
        newDp[i] = dp[i];
        if (i - 1 >= 0)
          newDp[i] += dp[i - 1];
        if (i + 1 < n)
          newDp[i] += dp[i + 1];
        newDp[i] %= kMod;
      }
      dp = newDp;
    }

    return (int) dp[0];
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
  def numWays(self, steps: int, arrLen: int) -> int:
    kMod = 1_000_000_007
    # dp[i] := the number of ways to stay at index i
    dp = [0] * min(steps // 2 + 1, arrLen)
    dp[0] = 1

    for _ in range(steps):
      newDp = [0] * min(steps // 2 + 1, arrLen)
      for i, ways in enumerate(dp):
        if ways > 0:
          for dx in (-1, 0, 1):
            nextIndex = i + dx
            if 0 <= nextIndex < len(dp):
              newDp[nextIndex] += ways
              newDp[nextIndex] %= kMod
      dp = newDp

    return dp[0]