Siga estas etapas para resolver qualquer problema em entrevistas sobre Programação Dinâmica

Artigo original: https://www.freecodecamp.org/news/follow-these-steps-to-solve-any-dynamic-programming-interview-problem-cc98e508cd0e/

Escrito por: Nikola Otasevic

Apesar de terem uma experiência significativa na criação de produtos de software, muitos engenheiros ficam nervosos com a ideia de passar por uma entrevista sobre programação com foco em algoritmos. Entrevistei centenas de engenheiros na Refdash, no Google e em startups das quais fiz parte. Algumas das perguntas mais comuns que deixam os engenheiros desconfortáveis são as que envolvem Programação Dinâmica (PD).

Muitas empresas de tecnologia gostam de fazer perguntas sobre PD em suas entrevistas. Embora possamos discutir se elas são eficazes para avaliar a capacidade de alguém para desempenhar uma função de engenheiro, a PD continua a ser uma área que atrapalha os engenheiros no caminho para encontrar um emprego que eles amam.

Programação Dinâmica – previsível e preparável

Um dos motivos pelos quais acredito que as perguntas sobre PD podem não ser a melhor maneira de se testar a capacidade de engenharia é o fato de serem previsíveis e fáceis de combinar com padrões. Elas nos permitem filtrar muito mais a preparação do que a capacidade de engenharia.

Essas perguntas normalmente parecem bastante complexas por fora e podem dar a impressão de que a pessoa que as resolve é muito boa em algoritmos. Da mesma forma, as pessoas que talvez não consigam superar alguns conceitos de PD que confundem a mente podem parecer muito fracas em seu conhecimento de algoritmos.

A realidade, porém, é diferente. O maior fator em seu desempenho é a preparação. Portanto, vamos nos certificar de que todos estejam preparados para elas de uma vez por todas.

7 etapas para resolver um problema de Programação Dinâmica

No restante deste artigo, examinarei uma receita que você pode seguir para descobrir se um problema é um "problema de PD", bem como para encontrar uma solução para esse problema. Especificamente, vou seguir as seguintes etapas:

1. Reconhecer um problema de PD
2. Identificar as variáveis do problema
3. Expressar claramente a relação de recorrência
4. Identificar os casos básicos
5. Decidir se você deseja implementá-lo de maneira iterativa ou recursiva
6. Adicionar memoização
7. Determinar a complexidade de tempo

Exemplo de problema de PD

Com o objetivo de ter um exemplo das abstrações que farei, vou apresentar um exemplo de problema. Em cada uma das seções, farei referência ao problema, mas você também pode ler as seções independentemente do problema.

Declaração do problema:

Neste problema, estamos em uma bola que salta loucamente e tentamos parar, evitando "estacas" que ficam no caminho.

As regras são:

1) Você recebe um caminho plana com várias estacas. O caminho é representado por um array de booleanos que indica se um determinado ponto (discreto) tem ou não tem uma estaca. O booleano diz True se não houver uma estaca e False se houver.

Exemplo de representação do array:

2) Você tem uma velocidade inicial S. S é um número inteiro não negativo em um determinado ponto e indica o quanto você avançará no próximo salto.

3) Sempre que aterrissar em um ponto, você poderá ajustar sua velocidade em até mais ou menos 1 unidade antes do próximo salto.

4) Você deseja parar com segurança em qualquer lugar do caminho (não precisa ser no final do array). Você para quando sua velocidade se torna 0. No entanto, se você parar em um estaca em qualquer ponto, sua bola saltitante maluca explode e o jogo acaba.

O resultado da função deve ser um booleano indicando se podemos parar com segurança em qualquer lugar do caminho.

Etapa 1: reconhecer um problema de Programação Dinâmica

Primeiro, vamos deixar claro que a PD é, essencialmente, apenas uma técnica de otimização. A PD é um método para resolver problemas, dividindo-os em um conjunto de subproblemas mais simples, resolvendo cada um desses subproblemas apenas uma vez e armazenando suas soluções. Na próxima vez em que o mesmo subproblema ocorrer, em vez de recalcular sua solução, basta consultar a solução calculada anteriormente. Isso economiza tempo de computação às custas de um gasto modesto (espera-se) em espaço de armazenamento.

Reconhecer que um problema pode ser resolvido com o uso da PD é a primeira etapa e, muitas vezes, a mais difícil para resolvê-lo. O que você deve perguntar a si mesmo é se a solução do seu problema pode ser expressa como uma função de soluções de pequenos problemas semelhantes.

No caso do nosso problema de exemplo, dado um ponto no caminho, uma velocidade e o caminho à frente, poderíamos determinar os pontos onde poderíamos saltar em seguida. Além disso, parece que o fato de podermos parar no ponto atual com a velocidade atual depende apenas do fato de podermos parar no ponto para o qual escolhemos ir em seguida.

Isso é ótimo porque, ao avançarmos, encurtamos o caminho e tornamos nosso problema menor. Devemos ser capazes de repetir esse processo até chegarmos a um ponto em que seja óbvio que podemos parar.

Reconhecer um problema de Programação Dinâmica geralmente é a etapa mais difícil para resolvê-lo. A solução do problema pode ser expressa como uma função de soluções de pequenos problemas semelhantes?

Etapa 2: identificar as variáveis do problema

Agora, estabelecemos que há alguma estrutura recursiva em nossos subproblemas. Em seguida, precisamos expressar o problema em termos dos parâmetros da função e ver quais desses parâmetros estão mudando.

Normalmente, nas entrevistas, você terá um ou dois parâmetros variáveis, mas, tecnicamente, pode ser qualquer número. Um exemplo clássico de um problema com um parâmetro variável é "determinar o n-ésimo número de Fibonacci". Um exemplo de problema de dois parâmetros variáveis é "Calcular a distância de edição entre strings". Se você não estiver familiarizado com esses problemas, não se preocupe.

Uma maneira de determinar o número de parâmetros variáveis é listar exemplos de vários subproblemas e comparar os parâmetros. A contagem do número de parâmetros variáveis é importante para determinar o número de subproblemas que temos de resolver. Ela também é importante por si só, pois nos ajuda a fortalecer a compreensão da relação de recorrência da etapa 1.

Em nosso exemplo, os dois parâmetros que podem mudar em cada subproblema são:

1. Posição no array (P)
2. Velocidade (S)

É possível dizer que o caminho à frente também está mudando, mas isso seria redundante, considerando que o caminho imutável inteiro e que a posição (P) já contêm essas informações.

Agora, com esses dois parâmetros variáveis e outros parâmetros estáticos, temos a descrição completa dos nossos subproblemas.

Identifique os parâmetros variáveis e determine o número de subproblemas.

Etapa 3: expressar claramente a relação de recorrência

Essa é uma etapa importante que muitos atravessam rapidamente para poderem começar a programar. Expressar a relação de recorrência do modo mais clara possível fortalecerá sua compreensão do problema e facilitará significativamente todo o resto.

Depois de descobrir que a relação de recorrência existe e especificar os problemas em termos de parâmetros, essa deve ser uma etapa natural. Como os problemas se relacionam entre si? Em outras palavras, vamos supor que você tenha calculado os subproblemas. Como você calcularia o problema principal?

Veja como pensamos sobre isso em nosso problema de exemplo:

Como você pode ajustar sua velocidade em até 1 antes de pular para a próxima posição, há apenas 3 velocidades possíveis e, portanto, 3 pontos que poderiam ser o próximo.

Em termos mais formais, se nossa velocidade for S, posição P, poderíamos ir de (S, P) para:

1. (S, P + S); # se não alterarmos a velocidade
2. (S — 1, P + S — 1); # se alterarmos a velocidade em -1
3. (S + 1, P + S + 1); # se alterarmos a velocidade em +1

Se conseguirmos encontrar uma maneira de parar em qualquer um dos subproblemas acima, também poderemos parar em (S, P). Isso ocorre porque podemos fazer a transição de (S, P) para qualquer uma das três opções acima.

Normalmente, esse é um bom nível de compreensão do problema (explicação em inglês simples), mas, às vezes, você também pode querer expressar a relação matematicamente. Vamos chamar uma função que estamos tentando calcular de canStop (possível de parar). Então:

canStop(S, P) = canStop(S, P + S) || canStop(S — 1, P + S — 1) || canStop(S + 1, P + S + 1)

Certo! Parece que temos nossa relação de recorrência!

Relação de recorrência: supondo que você tenha calculado os subproblemas, como você calcularia o problema principal?

Etapa 4: identificar os casos básicos

Um caso básico, ou de base, é um subproblema que não depende de nenhum outro subproblema. Para encontrar esses subproblemas, você normalmente quer experimentar alguns exemplos, ver como o problema se simplifica em subproblemas menores e identificar em que ponto ele não pode ser mais simplificado.

O motivo pelo qual um problema não pode ser simplificado ainda mais é que um dos parâmetros se tornaria um valor que não é possível, dadas as restrições do problema.

Em nosso problema de exemplo, temos dois parâmetros variáveis, S e P. Vamos pensar sobre quais valores possíveis de S e P podem não ser legais:

1. P deve estar dentro dos limites do caminho determinada
2. Não é possível que runway[P] (o ponto P no array runway) seja false, pois isso significaria que cairemos sobre uma estaca
3. S não pode ser negativo, e um S==0 indica que paramos

Às vezes, pode ser um pouco desafiador converter as afirmações que fazemos sobre os parâmetros em casos básicos de programação. Isso ocorre porque, além de listar as afirmações para que o código pareça conciso e não verifique condições desnecessárias, você também precisa pensar em quais dessas condições são possíveis.

No nosso exemplo:

1. P < 0 || P >= comprimento do caminho parece fazer sentido. Uma alternativa poderia ser considerar fazer de P == fim do caminho um caso básico. No entanto, é possível que um problema se divida em um subproblema que vá além do final do caminho. Portanto, precisamos realmente verificar a desigualdade.
2. Isso parece bastante óbvio. Podemos simplesmente verificar se runway[P] é false.
3. Semelhante ao caso número 1, poderíamos simplesmente verificar se S < 0 e S == 0. No entanto, aqui podemos raciocinar que é impossível que S seja < 0 porque S diminui em no máximo 1. Assim, teria que passar pelo caso S == 0 antes. Portanto, S == 0 é um caso base suficiente para o parâmetro S.

Etapa 5: decidir se você deseja implementá-lo de maneira iterativa ou recursiva

A maneira como falamos sobre as etapas até agora pode levá-lo a pensar que devemos implementar o problema de modo recursivo. No entanto, tudo o que falamos até agora é completamente indiferente ao fato de você decidir implementar o problema recursiva ou iterativamente. Em ambas as abordagens, você teria que determinar a relação de recorrência e os casos de base.

Para decidir se a opção é iterativa ou recursiva, você deve pensar cuidadosamente sobre as vantagens e desvantagens.

Os problemas de estouro de pilha (do inglês, stack overflow) costumam ser um obstáculo e um motivo pelo qual você não gostaria de ter recursão em um sistema de produção (back-end). No entanto, para fins de entrevista, contanto que você mencione as vantagens e desvantagens, normalmente não terá problemas com nenhuma das implementações. Você deve se sentir à vontade para implementar ambas.

Em nosso problema específico, implementei as duas versões. Aqui está o código em Python para isso:
Uma solução recursiva (os trechos de código originais podem ser encontrados aqui):

Uma solução iterativa: (os trechos de código originais podem ser encontrados aqui)

Etapa 6: adicionar memoização

Memoização é uma técnica que está intimamente associada à PD. Ela é usada para armazenar os resultados de chamadas de funções dispendiosas, retornando o resultado em cache quando as mesmas entradas ocorrerem novamente.

Por que estamos adicionando memoização à nossa recursão? Encontramos os mesmos subproblemas que, sem a memoização, são computados repetidamente. Essas repetições muitas vezes levam a complexidades de tempo exponenciais.

Em soluções recursivas, adicionar memoização deve ser simples. Vejamos por quê. Lembre-se de que a memoização é apenas um cache dos resultados da função. Há ocasiões em que você deseja se desviar dessa definição para conseguir algumas otimizações menores, mas tratar a memoização como um cache de resultados de funções é a maneira mais intuitiva de implementá-la.

Isso significa que você deve:

1. Armazenar o resultado da função na memória antes de cada declaração de retorno
2. Procurar na memória o resultado da função antes de começar a fazer qualquer outro cálculo

Abaixo vemos o código acima com a memoização adicionada. As linhas adicionadas estão destacadas (os trechos de código originais podem ser encontrados aqui):

Para ilustrar a eficácia da memoização e das diferentes abordagens, vamos fazer alguns testes rápidos. Farei um teste de estresse com os três métodos que vimos até agora. Aqui está a configuração:

1. Criei um caminho com 1000 metros de comprimento e estacas em locais aleatórios (optei por uma probabilidade de 20% de uma estaca estar em um determinado local)
2. initSpeed (velocidade inicial) = 30
3. Executei todas as funções 10 vezes e medi o tempo médio de execução

Aqui estão os resultados (em segundos):

Você pode ver que a abordagem recursiva pura leva cerca de 500 vezes mais tempo do que a abordagem iterativa e cerca de 1300 vezes mais tempo do que a abordagem recursiva com memoização. Observe que essa discrepância cresceria rapidamente com o comprimento do caminho. Eu o encorajo a tentar executar esse teste por conta própria.

Etapa 7: determinar a complexidade do tempo

Existem algumas regras simples que podem facilitar muito o cálculo da complexidade do tempo de um problema de programação dinâmica. Aqui estão duas etapas que você precisa seguir:

1. Contar o número de estados — isso dependerá do número de parâmetros variáveis em seu problema
2. Pense no trabalho realizado por cada estado. Em outras palavras, se tudo o mais, exceto um estado, tiver sido computado, quanto trabalho terá de ser feito para computar esse último estado?

Em nosso problema de exemplo, o número de estados é |P| * |S|, onde

• P é o conjunto de todas as posições (|P| indica o número de elementos em P)
• S é o conjunto de todas as velocidades

O trabalho realizado por cada estado é O(1) nesse problema porque, considerando todos os outros estados, basta examinar 3 subproblemas para determinar o estado resultante.

Como observamos no código anterior, |S| é limitado pelo comprimento do caminho. Portanto, poderíamos dizer que o número de estados é |P|² e, como o trabalho realizado por cada estado é O(1), a complexidade de tempo total é O(|P|²).

No entanto, parece que |S| pode ser ainda mais limitado, porque se fosse realmente |P|, é muito claro que não seria possível parar, porque você teria que saltar o comprimento de todo o caminho no primeiro movimento.

Então, vamos ver como podemos colocar um limite mais estreito em |S|. Vamos chamar a velocidade máxima de S. Suponha que estejamos partindo da posição 0. Com que rapidez poderíamos parar se estivéssemos tentando parar o mais rápido possível e se ignorássemos as estacas possíveis?

Na primeira iteração, teríamos de chegar pelo menos ao ponto (S-1), ajustando nossa velocidade em zero para -1. A partir daí, avançaríamos pelo menos (S-2) passos e assim por diante.

Para um caminho de comprimento L, o seguinte deve ser válido:

=> (S-1) + (S-2) + (S-3) + ….+ 1 < L

=> S*(S-1) / 2 < L

=> S² — S — 2L < 0

Se você encontrar as raízes da função acima, elas serão:

r1 = 1/2 + sqrt(1/4 + 2L) e r2 = 1/2 — sqrt(1/4 + 2L)

Podemos escrever nossa inequação como:

(S — r1) * (S — r2) <; 0

Considerando que S — r2 > 0 para qualquer S > 0 e L > 0, precisamos do seguinte:

S — 1/2 — sqrt(1/4 + 2L) <; 0

=> S < 1/2 + sqrt(1/4 + 2L)

Essa é a velocidade máxima que poderíamos ter em um caminho de comprimento L. Se tivéssemos uma velocidade maior do que essa, teoricamente, não poderíamos parar, independentemente da posição das estacas.

Isso significa que a complexidade total do tempo depende apenas do comprimento do caminho L, assim:

O(L * sqrt(L)) que é melhor do que O(L²)

O(L * sqrt(L)) é o limite superior da complexidade de tempo

Parabéns! Você conseguiu! :)

As 7 etapas que seguimos devem dar a você uma estrutura para resolver sistematicamente qualquer problema de programação dinâmica. Recomendo fortemente que você pratique essa metodologia em mais alguns problemas para aperfeiçoar sua técnica.

Aqui estão algumas das próximas etapas que você pode seguir

1. Amplie o problema de exemplo tentando encontrar um caminho para um ponto de parada. Resolvemos um problema que informa se você pode parar, mas e se você também quisesse saber as etapas a serem seguidas para parar eventualmente ao longo do caminho? Como você modificaria a implementação existente para fazer isso?
2. Se quiser solidificar sua compreensão da memoização e entender que ela é apenas um cache de resultados de uma função, leia sobre decorators em Python ou conceitos semelhantes em outras linguagens. Pense em como eles permitiriam que você implementasse a memoização em geral para qualquer função que queira memoizar.
3. Trabalhe em mais problemas de PD seguindo as etapas que fizemos. Você sempre pode encontrar vários deles on-line (por exemplo, no LeetCode ou no GeeksForGeeks). Ao praticar, lembre-se de uma coisa: aprenda ideias, não aprenda problemas. O número de ideias é significativamente menor e é um espaço mais fácil de conquistar, o que também será muito mais útil para você.

Quando achar que já superou essas ideias, confira o Refdash, onde você é entrevistado por um engenheiro sênior e recebe um feedback detalhado sobre sua programação, algoritmos e projeto de sistema.

Publicado originalmente no blog do Refdash. O Refdash é uma plataforma de entrevistas que ajuda os engenheiros a entrevistar anonimamente engenheiros experientes das principais empresas, como Google, Facebook ou Palantir, e obter um feedback detalhado. O Refdash também ajuda os engenheiros a descobrir oportunidades de trabalho incríveis com base em suas habilidades e interesses.