Ladrão de casas

Solução 1 - Recursao com incluir ou pular antes de memoization

Boa versão inicial para deixar a decisão central bem explicita.

export function rob(nums: number[]): number {
  function solve(index: number): number {
    if (index >= nums.length) {
      return 0
    }

    return Math.max(solve(index + 1), nums[index] + solve(index + 2))
  }

  return solve(0)
}

Funciona, mas desperdica trabalho repetindo os mesmos indices.

Solução 2 - Programacao dinamica com estado reduzido em espaco O(1)

Agora a mesma ideia roda de forma linear.

export function rob(nums: number[]): number {
  let twoHousesBefore = 0
  let oneHouseBefore = 0

  for (const value of nums) {
    const current = Math.max(oneHouseBefore, twoHousesBefore + value)
    twoHousesBefore = oneHouseBefore
    oneHouseBefore = current
  }

  return oneHouseBefore
}

O ponto forte aqui e enxergar a escolha incluir-ou-não como estado.

O que dizer na entrevista

Uma explicação curta e boa seria:

Para cada casa, eu escolho entre pular e manter a melhor resposta anterior, ou roubar e somar com a melhor resposta de duas casas atras. Isso gera a recorrencia max(best(i - 1), best(i - 2) + nums[i]). Como só dependo dos dois estados anteriores, posso reduzir o espaco para O(1).

Isso mostra que você:

• viu a decisão certa
• evitou cair em guloso local
• conectou a recorrencia a uma otimização de espaco

Quando esse padrão aparece de novo

Esse padrão reaparece quando você precisa:

• escolher entre incluir ou excluir um item
• lidar com restrição de adjacencia
• montar programacao dinamica linear com dois estados
• transformar uma recursão de decisão em iteração

O ponto não e decorar esse problema.

O ponto e aprender a modelar escolha com dependência curta.