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))
class NumWays
{
const int MOD = 1000000007;
public int NumWays(int steps, int arrLen)
{
int maxPos = Math.Min(steps, arrLen - 1);
int[,] dp = new int[steps + 1, maxPos + 1];
dp[0, 0] = 1;
for (int i = 1; i <= steps; i++)
{
for (int j = 0; j <= maxPos; j++)
{
dp[i, j] = dp[i - 1, j];
if (j > 0) dp[i, j] = (dp[i, j] + dp[i - 1, j - 1]) % MOD;
if (j < maxPos) dp[i, j] = (dp[i, j] + dp[i - 1, j + 1]) % MOD;
}
}
return dp[steps, 0];
}
static void Main(string[] args)
{
NumWays nw = new NumWays();
Console.WriteLine(nw.NumWays(3, 2)); // Output: 4
}
}Solve with full IDE support and test cases
This C# solution builds on the same dynamic programming approach. The transition states manage the potential moves while maintaining accuracy and efficiency using the Math.Min function to limit the table size.
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))
1from functools import lru_cache
2
3MOD = 1000000007
4
5class NumWaysMemo:
6 def __init__(self):
7 self.cache = {}
8
9 def numWaysHelper(self, steps: int, pos: int, maxPos: int) -> int:
10 if pos < 0 or pos > maxPos:
11 return 0
12 if steps == 0:
13 return 1 if pos == 0 else 0
14
15 key = (steps, pos)
16 if key in self.cache:
17 return self.cache[key]
18
19 stay = self.numWaysHelper(steps - 1, pos, maxPos)
20 left = self.numWaysHelper(steps - 1, pos - 1, maxPos)
21 right = self.numWaysHelper(steps - 1, pos + 1, maxPos)
22
23 result = (stay + left + right) % MOD
24 self.cache[key] = result
25 return result
26
27 def numWays(self, steps: int, arrLen: int) -> int:
28 maxPos = min(steps, arrLen - 1)
29 return self.numWaysHelper(steps, 0, maxPos)
30
31nwm = NumWaysMemo()
32print(nwm.numWays(3, 2)) # Output: 4This Python solution applies memoization by caching computed results for recursive calls using a dictionary, strengthening the efficiency by avoiding repetitive calculations.