House Robber

Q: Por que roubar casas alternadas não resolve o problema do Ladrão de Casas?

Às vezes, o melhor plano pula duas casas seguidas. Em [10, 1, 1, 10] , as casas pares e as casas ímpares somam 11, enquanto a primeira e a última casa somam 20.

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
A resposta é no máximo 5 × 10⁶, então cabe em um inteiro de 32 bits com sinal.

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 qualquer outro plano: 5 + 4 + 2 = 11 e 3 + 11 = 14.

Para ir além

Retorne as casas que devem ser levadas, assim como o total. O que você precisa guardar da tabela para reconstruir essa lista, e dois totais acumulados ainda podem fazer isso?

Dicas

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

0 de 3 abertas

Solução

Atalhos falham: pegar uma casa sim, outra não, faz com que você perca 5 e 11 em [5, 3, 4, 11, 2], e pegar primeiro a casa mais rica leva a um resultado pior em [3, 4, 3]. Decida 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

Qualquer plano ou pula a última casa ou a pega. Pular deixa o melhor plano para as primeiras n-1 casas; pegar adiciona nums[n-1] ao melhor plano para as primeiras n-2. Assim, most(k) = max(most(k-1), most(k-2) + nums[k-1]), com most(0) = 0 e most(1) = nums[0]. Os dois casos abrangem todos os planos, portanto a resposta está correta.

Os casos se sobrepõem: most(k-1) solicita most(k-2) novamente, e o número de chamadas cresce como os números de Fibonacci, cerca de 1.6^n. Quarenta casas levam a mais de 300 milhões de chamadas, e n chega a 10^4.

Algoritmo

Escreva uma função auxiliar most(k) que retorna 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 pergunta apenas sobre most(0) até most(n): n + 1 perguntas. Responda a cada uma uma vez em uma tabela best, começando com best[0] = 0 e best[1] = nums[0] e preenchendo-a de baixo para cima a partir de k = 2, para que as duas entradas lidas em cada resposta já estejam lá.

Para [5, 3, 4, 11, 2], a tabela é 0, 5, 5, 9, 16, 16. Em k = 4, pular a casa 3 mantém best[3] = 9, enquanto pegar seus 11 somados a best[2] = 5 resulta em 16, que vence. Cada entrada custa uma comparação: tempo O(n) e 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 a 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 lê apenas as duas entradas anteriores, então mantenha dois números em vez da tabela: twoBack e oneBack, os melhores totais até duas casas atrás e até a casa anterior. Para uma casa que contém x, o novo melhor é max(oneBack, twoBack + x); então avance ambos. Ambos começam em 0, a rua vazia antes da primeira casa, portanto uma rua com uma casa não precisa de um caso especial. O tempo continua sendo O(n), e a 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

Sobrescrever oneBack antes de copiá-lo para twoBack. A próxima casa então lê o total errado. Calcule primeiro o novo melhor resultado e depois faça o deslocamento, ou atribua ambos de uma vez.
Ler nums[1] ou definir best[1] e best[2] logo de início. Ambos falham em uma rua com uma casa, como [0].
Em Lua e R, os arrays começam em 1, então o dinheiro na casa k-1 está em nums[k].

Perguntas frequentes3

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

A 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 esse valor para O(1). A recursão simples sem respostas armazenadas faz cerca de 1.6^n chamadas.

Por que roubar casas alternadas não resolve o problema do Ladrão de Casas?

Às vezes, o melhor plano pula duas casas seguidas. Em [10, 1, 1, 10], as casas pares e as casas ímpares somam 11, enquanto a primeira e a última casa somam 20.

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 escolhe no máximo uma delas. Execute a solução para uma rua reta duas vezes, uma sem a última casa e outra sem a primeira, e retorne o maior resultado. Uma única casa é o caso especial: a resposta é essa casa.

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

Teste #1

Teste #2

Teste #3

Argumento

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

Saída Esperada

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 frequentes3

Problemas parecidos