RUST GYM v0.2.4

62. Unique Paths

A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

How many possible unique paths are there?

 

Example 1:

Input: m = 3, n = 7
Output: 28

Example 2:

Input: m = 3, n = 2
Output: 3
Explanation:
From the top-left corner, there are a total of 3 ways to reach the bottom-right corner:
1. Right -> Down -> Down
2. Down -> Down -> Right
3. Down -> Right -> Down

Example 3:

Input: m = 7, n = 3
Output: 28

Example 4:

Input: m = 3, n = 3
Output: 6

 

Constraints:

  • 1 <= m, n <= 100
  • It's guaranteed that the answer will be less than or equal to 2 * 109.

Rust Solution

struct Solution;

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

#[test]
fn test() {
    let m = 3;
    let n = 2;
    let res = 3;
    assert_eq!(Solution::unique_paths(m, n), res);
    let m = 7;
    let n = 3;
    let res = 28;
    assert_eq!(Solution::unique_paths(m, n), res);
}

Having problems with this solution? Click here to submit an issue on github.