Pascal's Triangle

Q: Qual é a complexidade de tempo para gerar o triângulo de Pascal?

Construir cada linha a partir da linha acima leva tempo O(n²) para n linhas, porque o triângulo tem cerca de n²/2 entradas e cada uma envolve uma única adição. Isso é ideal, pois é preciso escrever cada entrada da saída. Além da saída, usa O(1) de espaço extra.

Q: Como o triângulo de Pascal está relacionado aos coeficientes binomiais?

A entrada k da linha r , contando ambas a partir de 0, é o coeficiente binomial C(r, k) , o número de maneiras de escolher k itens dentre r . A regra de que cada entrada é a soma das duas acima dela é a identidade C(r, k) = C(r-1, k-1) + C(r-1, k) . Essa também é a razão pela qual a linha r soma 2^r .

Q: Você consegue calcular uma linha sem construir as linhas acima dela?

Sim. Comece com 1 e obtenha cada próximo elemento a partir do anterior: C(r, k) = C(r, k-1) × (r-k+1) / k . Multiplique antes de dividir para que a divisão seja exata e use um inteiro de 64 bits para o produto. Assim, a linha r leva O(r) tempo, sem calcular outras linhas.

Q: Por que o triângulo de Pascal é um problema de programação dinâmica?

Cada entrada depende de dois subproblemas menores, as entradas acima dela, e esses subproblemas se sobrepõem bastante: a recursão simples os recalcula repetidamente. Construir as linhas em ordem armazena cada subproblema uma única vez e o reutiliza, transformando um trabalho exponencial em O(n²) .

FácilProgramação dinâmica

+10

No triângulo de Pascal, a primeira linha é [1]. Cada linha seguinte tem uma entrada a mais, começa e termina com 1, e cada entrada entre elas é a soma das duas entradas diretamente acima dela. Você recebe um inteiro numRows. Retorne as primeiras numRows linhas do triângulo, começando pela linha do topo, cada linha como um array de inteiros.

Função

generate(numRows: integer) → integer-2d-array

numRowsinteger: quantas linhas do triângulo construir
Retornainteger-2d-array: as primeiras numRows linhas, começando pela linha superior

Restrições

1 ≤ numRows ≤ 30
Todas as entradas das primeiras 30 linhas cabem em um inteiro com sinal de 32 bits. A maior é 77558760, no meio da linha 30.

Exemplos

Entrada: numRows = 5
Saída: [[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
Explicação: Cada elemento interno soma os dois que estão acima dele. Na quarta linha, 3 = 1 + 2 e 3 = 2 + 1. Na quinta linha, 4 = 1 + 3, 6 = 3 + 3 e 4 = 3 + 1.

Entrada: numRows = 1
Saída: [[1]]
Explicação: Com uma linha, o triângulo é apenas seu topo, [1].

+13 testes ocultos ao enviar

Para ir além

Você consegue construir apenas a última linha em um único array, atualizando-a no próprio lugar, linha após linha, em vez de manter as linhas anteriores? Em que direção o loop interno deve ser executado e por quê?

Dicas

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

0 de 3 abertas

Solução

A regra que define o triângulo é recursiva: uma entrada é a soma de duas entradas da linha acima. Avaliar essa regra do zero para cada entrada recalcula os mesmos valores repetidamente, e o trabalho dobra a cada linha. As linhas que você precisa retornar são exatamente as respostas armazenadas para esses problemas menores; portanto, construa o triângulo de cima para baixo e obtenha cada linha a partir da que você construiu antes dela.

Calcule cada entrada recursivamente

Correta, mas não termina nos maiores testes

Intuição

Numere as linhas e as posições dentro de uma linha começando em 0. A definição do triângulo se transforma em uma função: entry(row, col) é 1 quando col é 0 ou igual a row, as duas bordas, e, caso contrário, é entry(row-1, col-1) + entry(row-1, col). Chame-a para cada posição de cada linha e você terá o triângulo. Está correto porque é a definição, palavra por palavra.

O problema é a quantidade de chamadas que ela faz. A recursão só para nas bordas, onde retorna 1, então calcular uma entrada com valor v leva cerca de 2v chamadas. A linha r soma até 2^r, então as 30 linhas juntas precisam de cerca de 2^31 chamadas, mais de dois bilhões. As mesmas entradas pequenas são recalculadas milhões de vezes: entry(2, 1) fica abaixo de quase todos os valores acima dele.

Algoritmo

Escreva entry(row, col): retorne 1 se col for 0 ou se col for igual a row.
Caso contrário, retorne entry(row-1, col-1) + entry(row-1, col).
Para cada row de 0 a numRows-1, colete entry(row, col) para cada col de 0 a row.
Retorne a lista de linhas.

def pascalEntry(row, col):
    if col == 0 or col == row:
        return 1  # the edges of the triangle
    return pascalEntry(row - 1, col - 1) + pascalEntry(row - 1, col)


def generate(numRows):
    triangle = []
    for row in range(numRows):
        triangle.append([pascalEntry(row, col) for col in range(row + 1)])
    return triangle

Construa cada linha a partir da linha acima

Intuição

A versão recursiva continua pedindo elementos de linhas anteriores, e você já está construindo essas linhas de qualquer forma. Então, calcule as linhas em ordem, de cima para baixo, e, ao preencher a linha r, leia os valores necessários diretamente da linha r-1, que já está pronta. Cada elemento exige, então, uma adição. Isso é programação dinâmica em sua forma mais simples: a tabela de respostas menores é a própria saída.

Comece a linha r com r + 1 uns, o que define as duas extremidades. Depois, para cada posição interna c de 1 a r-1, defina-a como above[c-1] + above[c]. As linhas 0 e 1 não têm posições internas, então permanecem [1] e [1, 1], sem um caso especial.

O triângulo tem 1 + 2 + ... + n, cerca de n²/2, elementos, e cada um leva tempo constante, então o trabalho é O(n²). Além da saída, que você precisa retornar de qualquer forma, o método não exige memória extra. Para numRows = 30, são 465 elementos em vez de dois bilhões de chamadas.

Algoritmo

Comece com uma lista vazia de linhas.
Para cada row de 0 a numRows-1, crie row + 1 uns.
Para cada col de 1 a row-1, defina-o como a soma das posições col-1 e col da linha anterior.
Adicione a linha e continue. Retorne a lista.

def generate(numRows):
    triangle = [[1]]
    for row in range(1, numRows):
        above = triangle[-1]
        values = [1] * (row + 1)  # both edges are 1
        for col in range(1, row):
            values[col] = above[col - 1] + above[col]
        triangle.append(values)
    return triangle

Armadilhas e casos extremos

Os loops são curtos, então os erros estão relacionados aos limites e às primeiras linhas.

Retornar numRows + 1 linhas. Se você numerar as linhas a partir de 0, a última de que precisa é a linha numRows-1.
Executar o loop interno nas extremidades. A posição 0 não tem pai à esquerda e a posição row não tem pai à direita, então ler above[col-1] ou above[col] nesses pontos ultrapassa os limites. Preencha apenas as posições de 1 a row-1.
Escrever um intervalo que falha nas linhas pequenas. 1..<row do Swift falha quando row é 0, e 2:(row-1) do R conta regressivamente até 1 quando row é 2. Use uma condição para protegê-los ou inicie as posições internas com uns, para que as linhas 0 e 1 não precisem de loop.
Calcular as entradas usando fatoriais. C(29, 14) cabe em um int, mas 29! causa estouro mesmo em um inteiro de 64 bits, então uma fórmula baseada em fatoriais exibe números incorretos nas linhas inferiores.
Reutilizar o mesmo array para todas as linhas. Se você adicionar o mesmo array a cada vez e depois alterá-lo, todas as linhas da resposta acabam sendo iguais à última.

Perguntas frequentes4

Qual é a complexidade de tempo para gerar o triângulo de Pascal?

Construir cada linha a partir da linha acima leva tempo O(n²) para n linhas, porque o triângulo tem cerca de n²/2 entradas e cada uma envolve uma única adição. Isso é ideal, pois é preciso escrever cada entrada da saída. Além da saída, usa O(1) de espaço extra.

Como o triângulo de Pascal está relacionado aos coeficientes binomiais?

A entrada k da linha r, contando ambas a partir de 0, é o coeficiente binomial C(r, k), o número de maneiras de escolher k itens dentre r. A regra de que cada entrada é a soma das duas acima dela é a identidade C(r, k) = C(r-1, k-1) + C(r-1, k). Essa também é a razão pela qual a linha r soma 2^r.

Você consegue calcular uma linha sem construir as linhas acima dela?

Sim. Comece com 1 e obtenha cada próximo elemento a partir do anterior: C(r, k) = C(r, k-1) × (r-k+1) / k. Multiplique antes de dividir para que a divisão seja exata e use um inteiro de 64 bits para o produto. Assim, a linha r leva O(r) tempo, sem calcular outras linhas.

Por que o triângulo de Pascal é um problema de programação dinâmica?

Cada entrada depende de dois subproblemas menores, as entradas acima dela, e esses subproblemas se sobrepõem bastante: a recursão simples os recalcula repetidamente. Construir as linhas em ordem armazena cada subproblema uma única vez e o reutiliza, transformando um trabalho exponencial em O(n²).

Python

def generate(numRows):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

numRows = 5

Esperado

[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]