Burst Balloons

Q: Qual é a complexidade de tempo de Burst Balloons?

tempo O(n³) e memória O(n²) : cerca de n²/2 intervalos, cada um tentando até n balões como o último. Para 300 balões, isso dá cerca de 4.5 × 10^6 passos. Tentar todas as ordens é O(n · n!) .

Q: É possível resolver Burst Balloons com uma ordem gulosa?

Não. Estourar primeiro o menor balão rende 24 em [2, 4, 3] , onde é possível obter 33. Estourar agora o balão que paga mais rende 42 em [2, 9, 2] , onde estourar primeiro um 2 rende 18 + 18 + 9 = 45. Cada estouro altera os valores dos balões restantes.

DifícilProgramação dinâmica

+10

Uma fileira de balões é fornecida como nums, em que nums[i] é o número do balão i. Você estoura todos eles, um de cada vez, em qualquer ordem. Estourar um balão rende left × nums[i] × right moedas, em que left e right são os números dos seus vizinhos atuais, os balões mais próximos de cada lado que ainda estão na fileira. Um vizinho inexistente conta como 1. Depois de estourar um balão, seus dois vizinhos ficam adjacentes. Retorne o máximo de moedas que você pode coletar.

Função

maxCoins(nums: integer-array) → integer

numsinteger-array: os números nos balões, da esquerda para a direita
Retornainteger: o maior número de moedas que você pode coletar estourando todos os balões

Restrições

1 ≤ nums.length ≤ 300
0 ≤ nums[i] ≤ 100
A resposta é menor que 3 × 10⁸, portanto cabe em um inteiro assinado de 32 bits.

Exemplos

Entrada: nums = [2, 4, 3]
Saída: 33
Explicação: Estoure o 4 para obter 2 × 4 × 3 = 24. O 2, agora ao lado do 3, vale 1 × 2 × 3 = 6, e o 3 vale 3: 33 ao todo.

Para ir além

Você também pode retornar um pedido explosivo que renda o máximo de moedas?

Dicas

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

0 de 3 abertas

Solução

Cada estouro muda quem fica ao lado de quem, então o primeiro balão que você estoura não divide a fileira: os dois lados dele se tornam vizinhos. O último balão a estourar em um trecho é que faz isso. Ele permanece enquanto todo o resto desaparece, então os trechos dos dois lados são independentes, e uma tabela de intervalos sobre os trechos resolve o problema em O(n³).

Experimente todas as ordens de explosão

Correta, mas não termina nos maiores testes

Intuição

Escolha um balão, some left × value × right, remova-o e resolva a fileira mais curta da mesma maneira, mantendo o melhor total entre todas as escolhas. O método tenta todas as ordens, então está correto.

O primeiro estouro tem n opções, o próximo n-1, e assim por diante: n! ordens, chegando a 479,001,600 com apenas 12 balões. Memorizar os resultados para cada conjunto de balões restantes não ajuda, pois existem 2^n conjuntos.

Algoritmo

Escreva burstAll(row), que retorna o máximo de moedas dos balões em row, ou 0 para uma linha vazia.
Para cada posição k, ganhe left × row[k] × right, usando 1 além de cada extremidade, mais burstAll da linha sem row[k].
Retorne o melhor total entre todos os k e chame burstAll(nums).

def maxCoins(nums):
    # Most coins you can still collect from the balloons in row
    def burst_all(row):
        top = 0
        for k in range(len(row)):
            left = row[k - 1] if k > 0 else 1
            right = row[k + 1] if k + 1 < len(row) else 1
            # Burst row[k] now, then do as well as possible with the rest
            coins = left * row[k] * right + burst_all(row[:k] + row[k + 1:])
            top = max(top, coins)
        return top

    return burst_all(nums)

Recursão no último balão, com uma memória

Intuição

Complete a linha com um 1 em cada extremidade: vals = [1] + nums + [1]. Os preenchimentos nunca estouram e substituem os vizinhos ausentes. Seja solve(left, right) o máximo de moedas obtidas com os balões estritamente entre duas posições que permanecem de pé.

Digamos que k seja o último a estourar nesse intervalo. Todos os outros balões nele estouram enquanto k permanece de pé como uma parede, então a parte entre left e k vê apenas seus próprios balões e duas bordas fixas, e o mesmo vale para a parte entre k e right. Quando k estoura, seus vizinhos são exatamente left e right. Portanto, o melhor resultado para o intervalo é, considerando cada k, o melhor resultado das duas partes mais vals[left] × vals[k] × vals[right]. A resposta é o intervalo entre os dois preenchimentos. Cerca de n²/2 intervalos tentam até n balões cada, então uma memorização torna a complexidade O(n³).

Algoritmo

Monte vals como nums com 1 adicionado em cada extremidade e defina m como o seu comprimento.
Crie uma tabela de memorização m × m preenchida com -1.
Escreva solve(left, right): retorne 0 se right - left < 2 e o valor armazenado, se houver.
Caso contrário, tente cada k estritamente entre eles como o último balão, mantenha o maior resultado de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] e armazene-o.
Retorne solve(0, m-1).

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    memo = [[-1] * m for _ in range(m)]

    # Most coins from the balloons strictly between left and right
    def solve(left, right):
        if right - left < 2:
            return 0
        if memo[left][right] >= 0:
            return memo[left][right]
        top = 0
        for last in range(left + 1, right):
            # last bursts after every other balloon in the gap
            coins = solve(left, last) + solve(last, right) + vals[left] * vals[last] * vals[right]
            top = max(top, coins)
        memo[left][right] = top
        return top

    return solve(0, m - 1)

Preencha a tabela de intervalos por largura

Intuição

A recursão pergunta apenas sobre intervalos menores, então preencha a mesma tabela com laços, dos intervalos menores para os maiores. Assim, best[left][k] e best[k][right] já estarão definidos sempre que um intervalo maior precisar deles.

Para [2, 4, 3], completado com [1, 2, 4, 3, 1], best[0][4] testa cada balão como o último. Deixar o 3 por último resulta em best[0][3] = 30 mais 1 × 3 × 1, totalizando 33, o melhor resultado entre os três.

O trabalho é equivalente ao da versão com memoização, mas os laços simples evitam milhões de chamadas de função, o que torna esta versão várias vezes mais rápida em uma linguagem como Python ou R.

Algoritmo

Crie vals como nums com um 1 adicionado em cada extremidade, e defina m como seu comprimento.
Crie uma tabela m × m best preenchida com 0.
Para cada largura de 2 a m-1 e cada left com right = left + width dentro do array, teste todos os k estritamente entre eles.
Defina best[left][right] como o maior valor entre best[left][k] + best[k][right] + vals[left] × vals[k] × vals[right].
Retorne best[0][m-1].

def maxCoins(nums):
    # A 1 on each side stands for the ends of the row
    vals = [1] + nums + [1]
    m = len(vals)
    # best[left][right]: most coins from the balloons strictly between left and right
    best = [[0] * m for _ in range(m)]
    for width in range(2, m):
        for left in range(m - width):
            right = left + width
            edge = vals[left] * vals[right]
            top = 0
            for last in range(left + 1, right):
                # last goes after every other balloon in the gap,
                # so left and right are its neighbours when it bursts
                coins = best[left][last] + best[last][right] + edge * vals[last]
                if coins > top:
                    top = coins
            best[left][right] = top
    return best[0][m - 1]

Armadilhas e casos extremos

Dividir considerando o primeiro estouro com seus vizinhos originais, nums[k-1] × nums[k] × nums[k+1], mais os dois lados. Esses vizinhos podem já ter sido removidos: em [2, 4, 3], isso retorna 44, mais do que qualquer ordem real consegue obter.
Preencher a tabela linha por linha, aumentando left. Então best[k][right] para k > left ainda não foi calculado e é lido como 0. Preencha por largura ou percorra left em ordem decrescente.
Marcar uma lacuna não resolvida na memoização com 0. Uma lacuna de balões com valor zero realmente vale 0, então ela é resolvida novamente a cada visita. Use -1.
Em Lua e R, as posições preenchidas vão de 1 a m, então a resposta é best[1][m].

Perguntas frequentes3

Por que Burst Balloons escolhe o último balão em vez do primeiro?

Após a primeira explosão, seus dois lados se tornam vizinhos, então ainda afetam um ao outro. O último balão de um trecho permanece enquanto os outros estouram, então seus dois lados nunca se encontram e cada um é um subproblema independente. Quando ele estoura, seus vizinhos são os limites do trecho.

Qual é a complexidade de tempo de Burst Balloons?

tempo O(n³) e memória O(n²): cerca de n²/2 intervalos, cada um tentando até n balões como o último. Para 300 balões, isso dá cerca de 4.5 × 10^6 passos. Tentar todas as ordens é O(n · n!).

É possível resolver Burst Balloons com uma ordem gulosa?

Não. Estourar primeiro o menor balão rende 24 em [2, 4, 3], onde é possível obter 33. Estourar agora o balão que paga mais rende 42 em [2, 9, 2], onde estourar primeiro um 2 rende 18 + 18 + 9 = 45. Cada estouro altera os valores dos balões restantes.

def maxCoins(nums):
    # Escreva o código aqui

Teste #1

Teste #2

Teste #3

Argumento

nums = [2, 4, 3]

Saída Esperada

Burst Balloons

Função

Restrições

Exemplos

Dicas

Solução

Experimente todas as ordens de explosão

Recursão no último balão, com uma memória

Preencha a tabela de intervalos por largura

Armadilhas e casos extremos

Perguntas frequentes3

Problemas parecidos