Burst Balloons

+10

Uma fileira de balões é dada como nums, em que nums[i] é o número no balão i. Você estoura todos eles, um de cada vez, em qualquer ordem que escolher. Estourar um balão rende left × nums[i] × right moedas, em que left e right são os números nos seus vizinhos atuais: os balões mais próximos em cada lado que ainda estão na fileira. Um vizinho ausente, além de qualquer uma das extremidades da fileira, conta como 1. Depois de estourar um balão, os dois vizinhos se tornam adjacentes. Retorne o maior número 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⁸, então cabe em um inteiro com sinal de 32 bits.

Exemplos

Entrada: nums = [2, 4, 3]
Saída: 33
Explicação: Estoure os 4 primeiros para ganhar 2 × 4 × 3 = 24 moedas. O 2 e o 3 agora são vizinhos, então estourar o 2 rende 1 × 2 × 3 = 6, e o 3, agora sozinho, rende 1 × 3 × 1 = 3. Isso totaliza 33, e nenhuma outra ordem resulta em um valor maior: estourar o pequeno 2 primeiro já limita o total a 24.

+15 testes ocultos ao enviar

Para ir além

Você também pode retornar uma ordem de explosão que ganhe mais 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 uma escolha agora muda o custo de cada estouro posterior. Tentar todas as ordens significa considerar n! sequências. Pensar no primeiro balão a estourar também não divide a fileira, porque os dois lados dele se tornam vizinhos. Pensar no último balão a estourar em um trecho funciona: ele permanece no lugar enquanto todo o resto é removido, então o trecho à sua esquerda e o trecho à sua direita são independentes. Uma tabela de intervalos sobre esses 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 qualquer balão para estourar agora, colete left × value × right com seus vizinhos atuais, remova-o da fileira e resolva a fileira menor da mesma forma. Faça isso para cada escolha e mantenha o melhor total. Uma função recursiva burstAll(row) faz exatamente isso. Ela explora todas as ordens possíveis, então a resposta está correta.

Isso é inviável para tamanhos reais. O primeiro estouro tem n opções, o segundo n-1, e assim por diante: n! ordens. Para 12 balões, isso já dá 479,001,600 ordens, e o maior teste tem 120 balões. Lembrar os resultados para cada conjunto de balões que ainda estão de pé não resolve o problema, porque há 2^n desses conjuntos.

A saída é perceber por que há tantos subproblemas. Depois que você estoura o balão k, o balão à sua esquerda e o da sua direita ficam lado a lado, então o que acontece à esquerda ainda depende do que acontece à direita. A próxima abordagem escolhe o balão sobre o qual pensar de modo que os dois lados deixem de afetar um ao outro.

Algoritmo

Escreva burstAll(row), que retorna o máximo de moedas obtidas com os balões em row.
Para cada posição k, leia os vizinhos, usando 1 além de cada extremidade.
Ganhe left × row[k] × right e some burstAll da linha sem row[k].
Retorne o melhor total entre todos os k, ou 0 para uma linha vazia.
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

Primeiro, coloque um 1 em cada extremidade: vals = [1] + nums + [1]. Esses dois nunca estouram e representam os vizinhos ausentes nas bordas. Agora observe um intervalo entre duas posições left e right que ainda estão de pé e pergunte: qual balão dentro do intervalo estoura por último?

Digamos que seja k. Enquanto os outros balões do intervalo estouram, k continua ali, de pé entre eles como uma parede. Todos os balões entre left e k têm vizinhos apenas desse trecho, com left e k como bordas fixas, e o mesmo vale entre k e right. Portanto, os dois trechos são problemas independentes do mesmo tipo. Quando k finalmente estoura, tudo entre as bordas já desapareceu, então seus vizinhos são exatamente left e right, e ele rende vals[left] × vals[k] × vals[right]. Escolher o primeiro balão não produz essa divisão, porque seus dois lados se tornam vizinhos.

Isso nos dá uma recursão. solve(left, right) retorna o máximo de moedas dos balões estritamente entre left e right: 0 quando o intervalo está vazio; caso contrário, o maior valor de solve(left, k) + solve(k, right) + vals[left] × vals[k] × vals[right] para cada k no intervalo. A resposta é solve(0, m-1), o intervalo entre os dois balões de borda.

Sozinha, a recursão encontra o mesmo intervalo repetidas vezes, então armazene cada resultado em uma tabela memo[left][right] e retorne-o nas visitas seguintes. Há cerca de n²/2 intervalos, e cada um testa até n balões, então o trabalho é O(n³). Use -1 para um intervalo ainda não resolvido, porque 0 é uma resposta válida. A recursão nunca ultrapassa n+1 chamadas de profundidade, pois cada chamada trabalha com um intervalo menor.

Algoritmo

Monte vals como nums com um 1 adicionado em cada extremidade e defina m como seu comprimento.
Crie uma tabela m × m preenchida com -1.
Escreva solve(left, right): retorne 0 se right - left < 2 e o valor armazenado, se houver.
Caso contrário, teste cada k estritamente entre eles como o último balão, mantenha o maior valor 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 pela largura

Intuição

A recursão sempre pergunta sobre intervalos menores. Então, você pode preencher a mesma tabela sem recursão, desde que preencha os intervalos menores antes dos maiores. Seja best[left][right] o número máximo de moedas obtidas com os balões estritamente entre left e right, 0 para um intervalo vazio. Para cada largura a partir de 2 e cada intervalo dessa largura, teste cada k interno como o último balão. best[left][k] e best[k][right] são menores, então já têm seus valores finais.

Considere [2, 4, 3]. Com o preenchimento, fica vals = [1, 2, 4, 3, 1] nas posições de 0 a 4, e a resposta é best[0][4]. Preencha os intervalos do menor para o maior:

Largura 2, um balão dentro: best[0][2] = 1 × 2 × 4 = 8, best[1][3] = 2 × 4 × 3 = 24, best[2][4] = 4 × 3 × 1 = 12.
best[0][3], balões 2 e 4: deixar o 2 por último dá 0 + 24 + 1 × 2 × 3 = 30; deixar o 4 por último dá 8 + 0 + 1 × 4 × 3 = 20. Então, 30.
best[1][4], balões 4 e 3: deixar o 4 por último dá 0 + 12 + 2 × 4 × 1 = 20; deixar o 3 por último dá 24 + 0 + 2 × 3 × 1 = 30. Então, 30.
best[0][4], os três balões: deixar o 2 por último dá 0 + 30 + 1 × 2 × 1 = 32; deixar o 4 por último dá 8 + 12 + 1 × 4 × 1 = 24; deixar o 3 por último dá 30 + 0 + 1 × 3 × 1 = 33. Então, 33.

Ao reconstruir as escolhas vencedoras, você obtém a ordem: o 3 vai por último; antes dele, o 2 é o último do trecho à sua esquerda, e o 4 vai primeiro. Isso dá 24 + 6 + 3 = 33.

O trabalho é o mesmo que com a memoização: 302 × 301 × 300 / 6 ≈ 4.5 × 10^6 etapas para 300 balões e uma tabela de 302 × 302 números. Laços simples evitam milhões de chamadas de função, o que torna esta versão várias vezes mais rápida que a recursão em uma linguagem como Python ou R.

Algoritmo

Construa 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 cada 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

Os erros mais comuns são uma ordem gulosa, uma recursão baseada no primeiro balão estourado, um marcador de memoização incorreto e uma tabela preenchida na ordem errada.

Ordens gulosas falham. Estourar primeiro o menor balão rende 24 em [2, 4, 3], em vez de 33, e estourar o balão que rende mais no momento rende 42 em [2, 9, 2], enquanto estourar primeiro um 2 rende 18 + 18 + 9 = 45.
Dividir pelo primeiro balão estourado usando seus vizinhos originais, nums[k-1] × nums[k] × nums[k+1], mais os dois lados, conta vizinhos que talvez já tenham sido estourados. Para [2, 4, 3], o resultado é 44, mais do que qualquer ordem real consegue render.
Contar as bordas como parte do intervalo. left e right ainda permanecem quando o intervalo é esvaziado; somente os balões estritamente entre eles são estourados.
Preencher a tabela linha por linha, com left aumentando. 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 um intervalo não resolvido na memoização com 0. Um intervalo cheio de balões com valor zero realmente vale 0, então parece não resolvido para sempre e é resolvido novamente a cada visita. Use -1.
Esquecer os dois 1s de preenchimento, deixando os balões das extremidades sem vizinhos para multiplicar.
Em Lua e R, as posições preenchidas vão de 1 a m, então a resposta é best[1][m].

Perguntas frequentes4

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

Após a primeira explosão, os balões dos dois lados se tornam vizinhos, então a parte esquerda e a parte direita ainda afetam uma à outra e não podem ser resolvidas separadamente. O último balão de um trecho permanece no lugar enquanto os outros estouram, então os dois lados nunca se encontram; quando ele estoura, seus vizinhos são os limites fixos do trecho. Isso torna cada trecho um subproblema independente, que é o que a programação dinâmica exige.

Qual é a complexidade de tempo de Burst Balloons?

A tabela de intervalos tem cerca de n²/2 lacunas, e cada uma tenta até n balões como o último, então o tempo é O(n³) e a memória é O(n²). Para 300 balões, isso dá cerca de 4.5 × 10^6 etapas. Tentar todas as ordens é O(n · n!).

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

Não. Toda regra simples falha em uma sequência pequena. Estourar primeiro o menor balão rende 24 em [2, 4, 3], quando é possível obter 33. Estourar o balão que paga mais no momento rende 42 em [2, 9, 2], quando estourar primeiro um balão de valor 2 rende 45. Estourar um balão altera os preços dos que vêm depois, então você precisa usar programação dinâmica sobre intervalos.

Por que adicionar um 1 nas duas extremidades do array?

Um vizinho ausente conta como 1, então dois balões de preenchimento com valor 1 que nunca estouram dão a cada balão real dois vizinhos sem casos especiais. Eles também servem como limites do problema inteiro: a resposta é o intervalo entre os dois balões de preenchimento, best[0][m-1].

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [2, 4, 3]

Esperado

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 pela largura

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos