LeetCode 2912: Number of Ways to Reach Destination in the Grid

Explanation:

This problem can be solved using dynamic programming. We can create a 2D DP array to keep track of the number of ways to reach each cell in the grid.

The idea is to start from the destination cell and fill in the DP array by summing the number of ways from its right and bottom cells. We iterate from the destination cell to the starting cell, as we need the number of ways to reach the destination cell.

At the end, the value in the top left cell will represent the number of ways to reach the destination in the grid.

Algorithm:

1. Initialize a 2D DP array with dimensions equal to the grid dimensions.
2. Start from the bottom right cell and set its value to 1 (since there is only one way to reach the destination cell).
3. Iterate from the bottom right cell towards the top left cell.
4. For each cell, update its value by summing the values of its right and bottom cells.
5. Return the value in the top left cell as the result.

Time Complexity:

The time complexity of this solution is O(m*n), where m and n are the dimensions of the grid.

Space Complexity:

The space complexity is also O(m*n) for the DP array.

: :

class Solution {
    public int uniquePaths(int m, int n) {
        int[][] dp = new int[m][n];
        
        for (int i = m-1; i >= 0; i--) {
            for (int j = n-1; j >= 0; j--) {
                if (i == m-1 && j == n-1) {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = (i+1 < m ? dp[i+1][j] : 0) + (j+1 < n ? dp[i][j+1] : 0);
                }
            }
        }
        
        return dp[0][0];
    }
}