62. Unique Paths

leetcode medium

#array#csharp#leetcode#matrix#medium#string

Task

На сетке размером m на n находится робот. Изначально робот расположен в верхнем левом углу (то есть, в клетке grid[0][0]). Робот пытается добраться до нижнего правого угла (то есть, в клетку grid[m - 1][n - 1]). Робот может двигаться только вниз или вправо в любой момент времени.

Даны два целых числа m и n, верните количество возможных уникальных путей, которые робот может пройти, чтобы достичь нижнего правого угла.

Тестовые случаи сгенерированы таким образом, что ответ будет меньше или равен 2 * 10^9.

Пример:

Input: m = 3, n = 7

Output: 28

C# solution

matched/original

public class Solution {
    public int UniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return UniquePaths(m - 1, n) + UniquePaths(m, n - 1);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int UniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return UniquePaths(m - 1, n) + UniquePaths(m, n - 1);
    }
}

Java solution

matched/original

class Solution {
    public int uniquePaths(int m, int n) {
        if (m == 1 || n == 1) {
            return 1;
        }
        return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
    }
}

JavaScript solution

matched/original

var uniquePaths = function (m, n) {
    if (m == 1 || n == 1) {
        return 1;
    }
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1);
};

Python solution

matched/original

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        if m == 1 or n == 1:
            return 1

        return self.uniquePaths(m - 1, n) + self.uniquePaths(m, n - 1)

Go solution

matched/original

func uniquePaths(m int, n int) int {
    if m == 1 || n == 1 {
        return 1
    }
    return uniquePaths(m-1, n) + uniquePaths(m, n-1)
}

Explanation

Algorithm

1️⃣

Инициализировать двумерный массив d[m][n] = количество путей. Сначала установить количество путей равным 1 для первой строки и первого столбца. Для упрощения можно инициализировать весь двумерный массив единицами.

2️⃣

Проитерировать по всем "внутренним" ячейкам: d[col][row] = d[col - 1][row] + d[col][row - 1].

3️⃣

Вернуть d[m - 1][n - 1].

😎