Number Of Ways To Reach A Position After Exactly K Steps - Leetcode Solution

Problem:

There is a robot starting at position (0, 0), the origin, on a 2D plane. Given a sequence of its moves, judge if this robot ends up at (0, 0) after it completes its moves.

The move sequence is represented by a string, and the moves are represented by characters 'U', 'D', 'L' and 'R', which represent up, down, left and right respectively. Each move of the robot is a unit vector increment or decrement along one of the axes of the 2D plane.

Given the starting position {(0,0)}, a sequence of moves {{U,D,L,R}}, and an integer k, return the number of ways to move the robot to the destination {(0,0)} after exactly k moves.

Solution:

Approach:

We can solve this problem using dynamic programming.

We will create a table DP where DP[i][j][step] will represent the number of ways in which we can reach the position (i, j) after exactly step moves.

The index i ranges from -m to m and j ranges from -n to n where (m, n) is the maximum possible position after k moves. It is given by m = maxMoves2 + 1 and n = maxMoves2 + 1. Also, the maximum value of step is k.

Now, we can update the values of DP[i][j][step] as follows:

• Base case: For step=0, DP[0][0][0] = 1 (since we are already at the starting position).

• For each step > 0, we will loop through all 4 directions and update the value of DP[i][j][step] as the sum of number of ways to reach (i+x, j+y) in step-1 moves, where (x, y) is the direction we are moving in.

• Handle boundary cases: We need to check if the new position (i+x, j+y) is within the bounds of the 2D plane or not. If it is outside the bounds, then we can ignore that move.

• Return the value of DP[0][0][k] in the end.

Time Complexity: O(kmn) where k is the number of steps, and m and n are the maximum values of i and j.

Space Complexity: O(kmn) for the DP table.

Code:

int MOD = 1e9 + 7;

int dfs(int i, int j, int step, int k, vector<vector<vector<int>>>& DP) { if(i < -k || j < -k || i > k || j > k) return 0;

if(step == k)
{
    if(i == 0 && j == 0)
        return 1;
    else
        return 0;
}

if(DP[i+k][j+k][step] != -1)
    return DP[i+k][j+k][step];

int ans = 0;
ans = (ans + dfs(i-1, j, step+1, k, DP)) % MOD;
ans = (ans + dfs(i+1, j, step+1, k, DP)) % MOD;
ans = (ans + dfs(i, j-1, step+1, k, DP)) % MOD;
ans = (ans + dfs(i, j+1, step+1, k, DP)) % MOD;

return DP[i+k][j+k][step] = ans;

}

int findPaths(int m, int n, int maxMove, int startRow, int startColumn) { vector<vector<vector<int>>> DP(2maxMove+1, vector<vector<int>>(2maxMove+1, vector<int>(maxMove+1, -1)));

return dfs(startRow, startColumn, 0, maxMove, DP);

}

1