Unique Paths

Q: Qual é a fórmula para Unique Paths?

A resposta é o coeficiente binomial C(m+n-2, m-1) . Cada caminho faz m-1 movimentos para baixo e n-1 movimentos para a direita, em alguma ordem, e escolher quais dos m+n-2 movimentos são para baixo determina o caminho. Para uma grade de 3 × 4, temos C(5, 2) = 10.

MédioProgramação dinâmica Matemática e simulação

+10

Um robô começa na célula superior esquerda de uma grade com m linhas e n colunas e precisa chegar à célula inferior direita. Cada movimento o leva uma célula para a direita ou uma célula para baixo. Retorne o número de caminhos diferentes que ele pode percorrer.

Função

uniquePaths(m: integer, n: integer) → integer

minteger: o número de linhas na grade
ninteger: o número de colunas na grade
Retornainteger: o número de caminhos diferentes da célula superior esquerda até a célula inferior direita

Restrições

1 ≤ m, n ≤ 100
A resposta é no máximo 2 × 10⁹, então cabe em um inteiro de 32 bits com sinal.

Exemplos

Entrada: m = 3n = 4
Saída: 10
Explicação: Cada caminho faz 2 movimentos para baixo e 3 movimentos para a direita, 5 movimentos ao todo. Um caminho é determinado por quais 2 dos 5 movimentos vão para baixo, e há 10 maneiras de escolhê-los.

+14 testes ocultos ao enviar

Para ir além

Para uma grade de 100 × 100, a resposta tem 59 dígitos. Como você a retornaria módulo 10^9+7 usando a fórmula, quando dividir por i não funciona mais?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Listar os caminhos um por um é inviável: uma grade de 17 × 17 já tem 601,080,390 deles. Você precisa contar sem listar. Os caminhos até uma célula são os caminhos até a célula acima mais os caminhos até a célula à esquerda, o que transforma a grade em uma tabela que você preenche em uma única passada. Um caminho também não é mais do que uma sequência ordenada de movimentos para baixo e para a direita, e isso fornece uma fórmula fechada.

Conte todos os caminhos usando recursão

Correta, mas não termina nos maiores testes

Intuição

Pense no último movimento do robô até a célula inferior direita. Ele veio de baixo da célula acima ou da direita da célula à esquerda, nunca dos dois lados. Portanto, os caminhos em uma grade m × n são os caminhos pela grade com uma linha a menos, uniquePaths(m-1, n), mais os caminhos pela grade com uma coluna a menos, uniquePaths(m, n-1).

A recursão para em uma grade com uma linha ou uma coluna, na qual o robô só pode seguir em linha reta, então há exatamente 1 caminho. Todo caminho termina com um dos dois movimentos, portanto cada caminho é contado uma vez e o total está correto.

É lento porque todo caminho termina em um caso-base que retorna 1, então o número de chamadas é pelo menos igual à própria resposta. Uma grade de 17 × 17 exige mais de 600 milhões de chamadas, e os testes chegam a respostas próximas de 1.6 × 10^9. As mesmas grades menores são calculadas muitas vezes: (m-1, n-1) é alcançada uma vez a partir de cada um de seus dois nós-pai, e as repetições se multiplicam à medida que você desce.

Algoritmo

Se m ou n for 1, retorne 1: o único caminho é uma linha reta.
Caso contrário, conte os caminhos cuja última movimentação é para baixo, uniquePaths(m-1, n).
Conte os caminhos cuja última movimentação é para a direita, uniquePaths(m, n-1).
Retorne a soma deles.

def uniquePaths(m, n):
    # One row or one column: the only path is a straight line
    if m == 1 or n == 1:
        return 1
    # The last move came down from the row above or right from the column before
    return uniquePaths(m - 1, n) + uniquePaths(m, n - 1)

Preencha a grade uma linha de cada vez

Intuição

A recursão pergunta pelas mesmas células várias vezes, e há apenas m × n células. Conte os caminhos até cada célula uma única vez, em uma ordem na qual as células de que você precisa estejam sempre prontas.

Estado: paths[r][c] é o número de caminhos da célula superior esquerda até a linha r, coluna c. Recorrência: paths[r][c] = paths[r-1][c] + paths[r][c-1], os caminhos que chegam de cima mais os caminhos que chegam da esquerda. Casos-base: cada célula da linha superior e da coluna esquerda tem 1 caminho, em linha reta. Ordem: linha por linha, da esquerda para a direita, para que a célula acima e a célula à esquerda sejam preenchidas antes de você precisar delas.

Para m = 3 e n = 4, as linhas são 1 1 1 1, depois 1 2 3 4, depois 1 3 6 10, e a resposta é a última célula, 10.

Agora veja o que o preenchimento lê: apenas a linha de cima e a linha que você está preenchendo. Então, mantenha uma única linha. Antes de atualizar row[c], ela ainda contém a contagem da linha de cima, e row[c-1] já contém a nova contagem à esquerda, então row[c] += row[c-1] é toda a recorrência. O tempo continua sendo O(m × n), e a memória cai de O(m × n) para O(n).

Algoritmo

Crie row com n entradas, todas iguais a 1: a linha do topo.
Repita m-1 vezes, uma vez para cada linha abaixo do topo.
Em cada linha, para c de 1 a n-1, adicione row[c-1] a row[c]. row[0] permanece igual a 1: essa é a coluna da esquerda.
Retorne row[n-1].

def uniquePaths(m, n):
    # row[c] counts the paths into column c of the current row.
    # The top row is all 1s: the only way along it is straight right.
    row = [1] * n
    for _ in range(m - 1):
        for c in range(1, n):
            # Paths from above (the old row[c]) plus paths from the left (the new row[c-1])
            row[c] += row[c - 1]
    return row[n - 1]

Conte os movimentos usando um coeficiente binomial

Intuição

Cada caminho faz exatamente m-1 movimentos para baixo e n-1 movimentos para a direita, totalizando m+n-2 movimentos, em alguma ordem. Toda ordem é um caminho válido: o robô nunca faz mais de m-1 movimentos para baixo nem mais de n-1 movimentos para a direita, portanto nunca sai da grade. Assim, um caminho equivale a escolher quais m-1 dos m+n-2 movimentos são para baixo, e a resposta é o coeficiente binomial C(m+n-2, m-1).

A tabela da abordagem anterior é o triângulo de Pascal virado de lado, por isso os dois resultados coincidem. Para calcular o coeficiente sem fatoriais enormes, monte-o um fator de cada vez. Com N = m+n-2 e k = min(m, n)-1, multiplique por N-k+i e depois divida por i, para i de 1 a k. Após a etapa i, o valor acumulado é C(N-k+i, i), um número inteiro, então cada divisão é exata.

Para m = 3 e n = 4: N = 5, k = 2, e o valor passa por 1 × 4 / 1 = 4 e, depois, 4 × 5 / 2 = 10. Escolher pelo lado menor mantém o laço em no máximo 99 etapas. O produto antes da última divisão é k vezes a resposta. Para uma grade de 17 × 17, isso é 16 × 601,080,390, aproximadamente 9.6 × 10^9, acima do limite de 32 bits, então mantenha o valor em um inteiro de 64 bits.

Algoritmo

Defina N = m+n-2, o número de movimentos, e k = min(m, n)-1.
Inicie uma contagem de 64 bits em 1.
Para i de 1 até k, multiplique a contagem por N-k+i e, em seguida, divida-a por i.
Retorne a contagem.

def uniquePaths(m, n):
    # A path is m+n-2 moves; count the ways to choose which of them go down.
    # Choose along the shorter side so the loop stays short.
    moves = m + n - 2
    k = min(m, n) - 1
    count = 1
    for i in range(1, k + 1):
        # count goes from C(moves-k+i-1, i-1) to C(moves-k+i, i); the division is exact
        count = count * (moves - k + i) // i
    return count

Armadilhas e casos extremos

A contagem é curta, então os bugs ficam escondidos nas bordas da grade e no tamanho dos números.

Calcular (m+n-2)! e dividir pelos outros dois fatoriais causa overflow muito antes de o resultado causar: 21! já ultrapassa o limite de 64 bits, e m+n-2 chega a 105 em uma grade de 100 × 7.
Dividir antes de multiplicar, como em count / i * (N-k+i), trunca o resultado, porque count nem sempre é múltiplo de i. Multiplique primeiro: o produto sempre é divisível exatamente.
O produto count × (N-k+i) pode ultrapassar 2^31 mesmo quando o resultado não ultrapassa. Mantenha-o em um inteiro de 64 bits.
Deixar a linha superior ou a coluna da esquerda em 0, em vez de 1, faz com que todas as células sejam 0. Uma grade com uma linha ou uma coluna tem exatamente 1 caminho.
Trocar as linhas e as colunas não altera o resultado, pois C(m+n-2, m-1) = C(m+n-2, n-1).

Perguntas frequentes4

Qual é a fórmula para Unique Paths?

A resposta é o coeficiente binomial C(m+n-2, m-1). Cada caminho faz m-1 movimentos para baixo e n-1 movimentos para a direita, em alguma ordem, e escolher quais dos m+n-2 movimentos são para baixo determina o caminho. Para uma grade de 3 × 4, temos C(5, 2) = 10.

Qual é a complexidade de tempo de Unique Paths?

A tabela de programação dinâmica leva O(m × n) de tempo e O(n) de espaço quando você mantém uma linha. A fórmula binomial leva O(min(m, n)) de tempo e O(1) de espaço. A recursão simples faz pelo menos tantas chamadas quanto o número de caminhos, que é exponencial em m + n.

Como resolver Caminhos Únicos quando algumas células estão bloqueadas?

Use a mesma tabela e defina a contagem de uma célula bloqueada como 0 para que nenhum caminho passe por ela. A linha superior e a coluna da esquerda deixam de ser todas 1: cada célula após uma bloqueada na linha superior tem 0 caminhos. A fórmula não funciona mais, porque pressupõe que todas as ordens de movimentos são permitidas.

Por que a tabela de caminhos únicos corresponde ao triângulo de Pascal?

Cada célula soma a célula acima e a célula à sua esquerda, que é a regra que constrói o triângulo de Pascal, lido ao longo de suas diagonais. A célula na linha r e na coluna c contém C(r+c, r), então a célula inferior direita contém C(m+n-2, m-1).

Python

def uniquePaths(m, n):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

m = 3
n = 4

Esperado

Unique Paths

Função

Restrições

Exemplos

Dicas

Solução

Conte todos os caminhos usando recursão

Preencha a grade uma linha de cada vez

Conte os movimentos usando um coeficiente binomial

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos