62. Unique Paths

LeetCode medium original: C# #array #csharp #leetcode #matrix #medium #string

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

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

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

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

Exemplo:

Input: m = 3, n = 7

Output: 28

C# solução

correspondente/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++ solução

rascunho automático, revisar antes de enviar

#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 solução

correspondente/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 solução

correspondente/original

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

Python solução

correspondente/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 solução

correspondente/original

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

Algorithm

1️⃣

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

2️⃣

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

3️⃣

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

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.