Sponsored
Sponsored
This approach leverages dynamic programming to find the number of ways to stay at index 0 after a given number of steps. We define a 2D table dp[i][j] where i represents the number of steps remaining, and j represents the current position of the pointer.
To optimize computation, we can limit the table size to the minimum of steps and arrLen since going beyond these positions is unnecessary.
Time Complexity: O(steps * min(steps, arrLen))
Space Complexity: O(steps * min(steps, arrLen))
1MOD = 1000000007
2
3def numWays(steps: int, arrLen: int) -> int:
4 maxPos = min(steps, arrLen - 1)
5 dp = [[0] * (maxPos + 1) for _ in range(steps + 1)]
6 dp[0][0] = 1
7 for i in range(1, steps + 1):
8 for j in range(maxPos + 1):
9 dp[i][j] = dp[i - 1][j] % MOD
10 if j > 0:
11 dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD
12 if j < maxPos:
13 dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD
14 return dp[steps][0]
15
16print(numWays(3, 2)) # Output: 4The Python solution utilizes dynamic programming. It uses a list to store the number of ways to reach each position after each step, and follows the same logic as the C/C++/Java counterparts.
This approach utilizes recursion combined with memoization to optimize the recursive calls. Here, recursion is used to explore all possible paths dynamically adjusting by staying at, moving left, or moving right from each position in every step.
The results of the recursive calls are stored in a memoization table to avoid redundant calculations.
Time Complexity: O(steps * min(steps, arrLen))
Space Complexity: O(steps * min(steps, arrLen))
The Java implementation leverages a HashMap to cache results of recursive calls, effectively managing state transitions by evaluating all possibilities and memoizing results.