House Robber

Q: Qual é a relação de recorrência para House Robber?

O melhor total entre as primeiras k casas é max(best[k-1], best[k-2] + nums[k-1]) . Você pode pular a casa k-1 e manter o melhor resultado das casas anteriores a ela, ou escolher a casa k-1 e somá-la ao melhor resultado que termina antes da casa vizinha. Os casos base são 0 para nenhuma casa e nums[0] para uma casa.

Q: Por que roubar uma casa sim e outra não não resolve o problema do Assaltante de Casas?

Às vezes, o melhor plano pula duas casas seguidas. Em [10, 1, 1, 10] , tanto as casas pares quanto as ímpares somam 11, enquanto pegar a primeira e a última casa dá 20. A programação dinâmica compara pular e pegar em cada casa, então encontra esses planos.

MédioProgramação dinâmica

+10

As casas ficam enfileiradas ao longo de uma rua, e nums[i] é o dinheiro na casa i. Você pode pegar o dinheiro de quaisquer casas que escolher, mas nunca de duas casas vizinhas. Retorne o maior total que você pode pegar.

Função

rob(nums: integer-array) → integer

numsinteger-array: o dinheiro em cada casa, na ordem da rua
Retornainteger: o maior total que você pode obter sem pegar dinheiro de duas casas adjacentes

Restrições

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
O resultado é, no máximo, 5 × 10⁶, então cabe em um inteiro com sinal de 32 bits.

Exemplos

Entrada: nums = [5, 3, 4, 11, 2]
Saída: 16
Explicação: Some 5 e 11 das casas 0 e 3 para obter 16. É permitido pular duas casas seguidas, e aqui isso supera todos os outros planos: 5 + 4 + 2 = 11 e 3 + 11 = 14.

+16 testes ocultos ao enviar

Para ir além

Retorne as casas a serem consideradas, bem como o total. O que você precisa manter da tabela para reconstruir essa lista, e os dois totais acumulados ainda conseguem fazer isso?

Dicas

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

0 de 3 abertas

Solução

Os atalhos óbvios não funcionam. Pegar uma casa sim, outra não, deixa passar planos que pulam duas casas seguidas, como 5 e 11 em [5, 3, 4, 11, 2], e pegar primeiro a casa mais valiosa falha em [3, 4, 3], em que 4 bloqueia duas casas que, juntas, valem 6. O que funciona é decidir uma casa de cada vez: o melhor total até uma casa depende apenas dos melhores totais até as duas casas anteriores.

Experimente as duas opções em cada casa

Correta, mas não termina nos maiores testes

Intuição

Observe a última casa, a casa n-1. Qualquer plano ou a ignora ou a inclui. Se a ignora, o melhor que pode fazer é seguir o melhor plano para as primeiras n-1 casas. Se a inclui, a casa n-2 fica indisponível, então ela soma nums[n-1] ao melhor plano para as primeiras n-2 casas. A resposta é o maior dos dois valores.

Escreva isso como uma função most(k), o máximo que você pode obter das primeiras k casas: most(k) = max(most(k-1), most(k-2) + nums[k-1]), com most(0) = 0 para nenhuma casa e most(1) = nums[0] para uma casa. Todo plano ignora ou inclui sua última casa, então os dois casos abrangem todos os planos, e o resultado está correto.

Isso é lento porque os casos se sobrepõem. most(k-1) chama most(k-2) novamente, então a mesma questão é respondida repetidamente, e o número de chamadas cresce como os números de Fibonacci, aproximadamente 1.6^n. Quarenta casas já exigem mais de 300 milhões de chamadas, e os testes têm até 10^4 casas. As chamadas também se aninham em n níveis de profundidade, ultrapassando o limite padrão de 1000 do Python.

Algoritmo

Escreva uma função auxiliar most(k) que retorne o máximo que você pode pegar das primeiras k casas.
Retorne 0 quando k for 0 e nums[0] quando k for 1.
Caso contrário, calcule skip = most(k-1) e take = most(k-2) + nums[k-1].
Retorne o maior dos dois. A resposta é most(n).

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

Tabela de baixo para cima

Intuição

A recursão só pergunta sobre most(0) até most(n), então há n + 1 perguntas diferentes. Responda a cada uma uma vez, armazene a resposta em uma tabela e preencha a tabela em uma ordem na qual todas as respostas que você consultar já estejam lá. Quatro decisões definem a tabela.

Estado: best[k] é o máximo que você pode pegar das primeiras k casas. Recorrência: best[k] = max(best[k-1], best[k-2] + nums[k-1]): pule a casa k-1 ou pegue o valor dela além do melhor resultado que termina antes da casa vizinha. Casos-base: best[0] = 0 e best[1] = nums[0]. Ordem: k de 2 até n, porque cada entrada consulta as duas entradas anteriores.

Para [5, 3, 4, 11, 2], a tabela é 0, 5, 5, 9, 16, 16. Em k = 4, você compara pular a casa 3, que vale best[3] = 9, com pegar os 11 dela somados a best[2] = 5, e 16 vence. A resposta é a última entrada. Cada entrada exige uma comparação, então o tempo é O(n), e a tabela ocupa espaço O(n).

Algoritmo

Crie uma tabela best com n + 1 entradas.
Defina best[0] = 0 e best[1] = nums[0].
Para k de 2 até n, defina best[k] como o maior entre best[k-1] e best[k-2] + nums[k-1].
Retorne best[n].

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

Dois totais acumulados

Intuição

Cada entrada da tabela consulta apenas as duas entradas imediatamente anteriores. Depois que best[k] é conhecido, best[k-2] nunca mais é consultado. Então, em vez da tabela, mantenha dois números: twoBack, o total máximo das casas até duas posições atrás, e oneBack, o total máximo até a casa anterior.

Para uma casa que contém x, o novo máximo é max(oneBack, twoBack + x). Então, faça o deslocamento: twoBack recebe o valor antigo de oneBack, e oneBack recebe o novo máximo. Ambos começam em 0, que representa a rua vazia antes da primeira casa, então a primeira casa não precisa de um caso especial: seu máximo é max(0, 0 + nums[0]).

Para [5, 3, 4, 11, 2], o par fica (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16), e oneBack termina em 16. O trabalho é o mesmo O(n) que com a tabela, e o uso de memória cai para O(1).

Algoritmo

Defina twoBack e oneBack como 0.
Para cada valor x em nums, calcule current = max(oneBack, twoBack + x).
Mova oneBack para twoBack e, em seguida, current para oneBack.
Depois da última casa, retorne oneBack.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

Armadilhas e casos extremos

A maioria das respostas incorretas resulta de um atalho que funciona com entradas pequenas ou da atualização dos dois totais na ordem errada.

Somar as casas pares e as casas ímpares e escolher o maior total deixa passar planos que pulam duas casas seguidas. Em [10, 1, 1, 10], ambas as somas são 11, mas as casas 0 e 3 somam 20.
Escolher primeiro a casa mais rica falha em [3, 4, 3]: escolhe 4 e bloqueia os dois 3, que juntos somam 6.
Sobrescrever oneBack antes de copiá-lo para twoBack faz você perder o valor de que a próxima casa precisa. Calcule primeiro o novo melhor resultado e depois faça o deslocamento, ou atribua os dois valores de uma vez, quando a linguagem permitir.
Ler nums[1] ou definir best[1] e best[2] logo de início causa problemas em uma rua com uma única casa. Começar os dois totais em 0 elimina o caso especial.
Em Lua e R, os arrays começam em 1, então o dinheiro da casa k-1 está em nums[k].

Perguntas frequentes4

Qual é a relação de recorrência para House Robber?

O melhor total entre as primeiras k casas é max(best[k-1], best[k-2] + nums[k-1]). Você pode pular a casa k-1 e manter o melhor resultado das casas anteriores a ela, ou escolher a casa k-1 e somá-la ao melhor resultado que termina antes da casa vizinha. Os casos base são 0 para nenhuma casa e nums[0] para uma casa.

Qual é a complexidade de tempo e espaço do House Robber?

A solução de programação dinâmica analisa cada casa uma vez, então leva O(n) de tempo. Uma tabela completa usa O(n) de espaço, e manter apenas os dois últimos totais reduz isso para O(1). A recursão simples sem respostas armazenadas faz cerca de 1.6^n chamadas, o que é exponencial.

Por que roubar uma casa sim e outra não não resolve o problema do Assaltante de Casas?

Às vezes, o melhor plano pula duas casas seguidas. Em [10, 1, 1, 10], tanto as casas pares quanto as ímpares somam 11, enquanto pegar a primeira e a última casa dá 20. A programação dinâmica compara pular e pegar em cada casa, então encontra esses planos.

Como resolver o problema House Robber quando as casas formam um círculo?

Em um círculo, a primeira e a última casa são vizinhas, então um plano pode incluir no máximo uma delas. Execute a solução para rua reta duas vezes: uma sem a última casa e outra sem a primeira, e retorne o maior resultado. Uma rua com apenas uma casa é o caso especial: a resposta é essa casa.

Python

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

Casos de teste

Caso 1

Caso 2

Caso 3

Entrada

nums = [5, 3, 4, 11, 2]

Esperado

House Robber

Função

Restrições

Exemplos

Dicas

Solução

Experimente as duas opções em cada casa

Tabela de baixo para cima

Dois totais acumulados

Armadilhas e casos extremos

Perguntas frequentes4

Problemas parecidos