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))
1const MOD = 1000000007;
2
3function numWays(steps, arrLen) {
4 const maxPos = Math.min(steps, arrLen - 1);
5 const dp = Array.from({length: steps + 1}, () => Array(maxPos + 1).fill(0));
6 dp[0][0] = 1;
7 for (let i = 1; i <= steps; i++) {
8 for (let j = 0; j <= maxPos; j++) {
9 dp[i][j] = dp[i - 1][j];
10 if (j > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % MOD;
11 if (j < maxPos) dp[i][j] = (dp[i][j] + dp[i - 1][j + 1]) % MOD;
12 }
13 }
14 return dp[steps][0];
15}
16
17console.log(numWays(3, 2)); // Output: 4This JavaScript implementation follows the dynamic programming strategy to compute the required count of ways. It controls the array size using generic JavaScript functionality such that the number of computations remains efficient and manageable.
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))
using System.Collections.Generic;
class NumWaysMemo
{
const int MOD = 1000000007;
private Dictionary<string, int> cache = new Dictionary<string, int>();
public int NumWaysHelper(int steps, int pos, int maxPos)
{
if (pos < 0 || pos > maxPos) return 0;
if (steps == 0) return pos == 0 ? 1 : 0;
string key = steps + "," + pos;
if (cache.ContainsKey(key)) return cache[key];
int stay = NumWaysHelper(steps - 1, pos, maxPos);
int left = NumWaysHelper(steps - 1, pos - 1, maxPos);
int right = NumWaysHelper(steps - 1, pos + 1, maxPos);
int result = ((stay + left) % MOD + right) % MOD;
cache[key] = result;
return result;
}
public int NumWays(int steps, int arrLen)
{
int maxPos = Math.Min(steps, arrLen - 1);
return NumWaysHelper(steps, 0, maxPos);
}
static void Main(string[] args)
{
NumWaysMemo nwm = new NumWaysMemo();
Console.WriteLine(nwm.NumWays(3, 2)); // Output: 4
}
}A C# recursive solution with memoization. It pursues all move directions while caching results to eliminate redundant operations and effectively manage state transitions in an optimal manner.