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))
1public class NumWays {
2 private static final int MOD = 1000000007;
3 public int numWays(int steps, int arrLen) {
4The Java solution follows the dynamic programming method to calculate the number of ways to stay at the initial position after the given steps. The transition between states considers all potential moves: staying, moving left, or right.
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))
#include <vector>
#define MOD 1000000007
using namespace std;
vector<vector<int>> cache;
int numWaysHelper(int steps, int pos, int maxPos) {
if (pos < 0 || pos > maxPos) return 0;
if (steps == 0) return pos == 0 ? 1 : 0;
if (cache[steps][pos] != -1) return cache[steps][pos];
int stay = numWaysHelper(steps - 1, pos, maxPos);
int left = numWaysHelper(steps - 1, pos - 1, maxPos);
int right = numWaysHelper(steps - 1, pos + 1, maxPos);
return cache[steps][pos] = ((stay + left) % MOD + right) % MOD;
}
int numWays(int steps, int arrLen) {
int maxPos = min(steps, arrLen - 1);
cache.assign(steps + 1, vector<int>(maxPos + 1, -1));
return numWaysHelper(steps, 0, maxPos);
}
int main() {
cout << numWays(3, 2) << endl; // Output: 4
return 0;
}A C++ implementation of recursion with memoization, using vectors to dynamically manage memory and cache recursive results, considerably speeding up the process.