Unique Paths

                                            
class Solution {
public:
    int uniquePaths(int m, int n) {
        vector<vector<int>> dp(m, vector<int>(n, 1));
        
        for (int i = 1; i < m; ++i) {
            for (int j = 1; j < n; ++j) {
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        
        return dp[m-1][n-1];
    }
};

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

                                            
class Solution(object):
    def uniquePaths(self, m, n):
        dp = [[1] * n for _ in range(m)]
        
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i-1][j] + dp[i][j-1]
        
        return dp[-1][-1]

                                            
int uniquePaths(int m, int n) {
    int dp[m][n];
    
    for(int i = 0; i < m; i++) {
        dp[i][0] = 1;
    }
    
    for(int j = 0; j < n; j++) {
        dp[0][j] = 1;
    }
    
    for(int i = 1; i < m; i++) {
        for(int j = 1; j < n; j++) {
            dp[i][j] = dp[i-1][j] + dp[i][j-1];
        }
    }
    
    return dp[m-1][n-1];
}

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

                                            
/**
 * @param {number} m
 * @param {number} n
 * @return {number}
 */
var uniquePaths = function(m, n) {
    const dp = new Array(m).fill(1).map(() => new Array(n).fill(1));
    
    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }
    
    return dp[m - 1][n - 1];
};

                                            
function uniquePaths(m: number, n: number): number {
    const dp: number[][] = new Array(m).fill(0).map(() => new Array(n).fill(1));

    for (let i = 1; i < m; i++) {
        for (let j = 1; j < n; j++) {
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    }

    return dp[m - 1][n - 1];
};

                                            
class Solution {
    /**
     * @param Integer $m
     * @param Integer $n
     * @return Integer
     */
    function uniquePaths($m, $n) {
        $dp = array_fill(0, $m, array_fill(0, $n, 1));

        for ($i = 1; $i < $m; $i++) {
            for ($j = 1; $j < $n; $j++) {
                $dp[$i][$j] = $dp[$i - 1][$j] + $dp[$i][$j - 1];
            }
        }

        return $dp[$m - 1][$n - 1];
    }
}

                                            
class Solution {
    func uniquePaths(_ m: Int, _ n: Int) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: n), count: m)
        
        for i in 0..<m {
            for j in 0..<n {
                if i == 0 || j == 0 {
                    dp[i][j] = 1
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1]
                }
            }
        }
        
        return dp[m-1][n-1]
    }
}

                                            
class Solution {
    fun uniquePaths(m: Int, n: Int): Int {
        val dp = Array(m) { IntArray(n) { 1 } }
        
        for (i in 1 until m) {
            for (j in 1 until n) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
            }
        }
        
        return dp[m - 1][n - 1]
    }
}

                                            
class Solution {
  int uniquePaths(int m, int n) {
    List<List<int>> dp = List.generate(m, (_) => List.filled(n, 1));
    
    for (int i = 1; i < m; i++) {
      for (int j = 1; j < n; j++) {
        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
      }
    }
    
    return dp[m - 1][n - 1];
  }
}

                                            
func uniquePaths(m int, n int) int {
    dp := make([][]int, m)
    for i := range dp {
        dp[i] = make([]int, n)
        dp[i][0] = 1
    }
    for j := 0; j < n; j++ {
        dp[0][j] = 1
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
        }
    }
    return dp[m-1][n-1]
}

                                            
# @param {Integer} m
# @param {Integer} n
# @return {Integer}
def unique_paths(m, n)
    dp = Array.new(m) { Array.new(n, 1) }
    
    (1...m).each do |i|
        (1...n).each do |j|
            dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
        end
    end
    
    dp[m - 1][n - 1]
end

                                            
object Solution {
    def uniquePaths(m: Int, n: Int): Int = {
        val dp = Array.ofDim[Int](m, n)
        
        for (i <- 0 until m) {
            dp(i)(0) = 1
        }
        
        for (j <- 0 until n) {
            dp(0)(j) = 1
        }
        
        for (i <- 1 until m) {
            for (j <- 1 until n) {
                dp(i)(j) = dp(i - 1)(j) + dp(i)(j - 1)
            }
        }
        
        dp(m - 1)(n - 1)
    }
}

                                            
impl Solution {
    pub fn unique_paths(m: i32, n: i32) -> i32 {
        let mut dp = vec![vec![0; n as usize]; m as usize];
        
        for i in 0..m as usize {
            for j in 0..n as usize {
                if i == 0 || j == 0 {
                    dp[i][j] = 1;
                } else {
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        
        dp[m as usize - 1][n as usize - 1]
    }
}

                                            
(define/contract (unique-paths m n)
  (-> exact-integer? exact-integer? exact-integer?)
  (if (or (= m 1) (= n 1))
      1
      (+ (unique-paths (- m 1) n) (unique-paths m (- n 1)))
      )
  )

To solve this coding challenge, we need to determine the number of unique paths a robot can take to move from the top-left corner to the bottom-right corner of a grid. The robot can only move down or right at any point in time, and we are given the dimensions of the grid (m, n). Let's explore the approach and create pseudocode to solve this problem.

# Explanation

The challenge involves computing the number of unique paths from the top-left to the bottom-right of an m x n grid. The robot can only move down or right. A dynamic programming approach is suitable for this problem because it allows us to break the problem down into smaller subproblems and reuse their solutions.

## Key Points:

Grid Representation : Use a 2D array (e.g., dp) where dp[i][j] represents the number of unique paths to reach cell (i, j).
Initialization :

The first row (dp[0][j]) should all be 1 because the only way to move right in the first row is from the left.
The first column (dp[i][0]) should all be 1 because the only way to move down in the first column is from the top.

State Transition : For each cell (i, j), the number of unique paths to that cell is the sum of the number of unique paths to the cell directly above it (dp[i-1][j]) and the cell directly to its left (dp[i][j-1]).

Detailed Steps in Pseudocode:

Initialize a matrix (dp) with dimensions m x n. Start by filling the entire matrix with default values (e.g., 1).
Iterate over the cells of the matrix starting from (1, 1) . Update each cell by summing the values from the top and left cells.
Return the value in the bottom-right corner of the matrix (dp[m-1][n-1]) which holds the total number of unique paths.

# Pseudocode with Comments:

                                            
function uniquePaths(m, n):
# Create a 2D list (dp) with m rows and n columns initialized to 1
dp = initialize 2D list of size m x n filled with 1

# Loop over each row starting from the second row
for row in range(1, m):
# Loop over each column starting from the second column
for col in range(1, n):
# Update the cell dp[row][col]
# It is the sum of the value from the cell above (dp[row-1][col])
# and the value from the cell on the left (dp[row][col-1])
dp[row][col] = dp[row - 1][col] + dp[row][col - 1]

# Return the value in the bottom-right cell which contains the number of unique paths
return dp[m - 1][n - 1]

Step-by-Step Explanation

Initialize the dp matrix : We first create a 2D list with dimensions m x n, where every element is initialized to 1. This is because the first row and first column should all be 1, representing the only ways to move to these cells (either only right or only down).
Iterating through the matrix : We start with the second row and the second column. For each cell at position (i, j), we calculate the number of ways to reach it by summing the number of ways to reach the cell above it and the cell to the left.
Compute the number of paths dynamically : Each cell in the matrix dp is filled based on previously computed values, ensuring that by the time we reach the bottom-right corner, dp[m-1][n-1] will have the total number of unique paths from the top-left to bottom-right.

By following this approach, the robot's movement paths are computed efficiently using dynamic programming, ensuring that the solution scales well with the given constraints (1 <= m, n <= 100).