Se você já programa há tempo suficiente, provavelmente já ouviu o termo programação dinâmica. Muitas vezes, um assunto-chave em entrevistas técnicas , a ideia também surgirá em reuniões de revisão de design ou interações regulares com colegas desenvolvedores. Este ensaio examinará o que é programação dinâmica e por que você a usaria. Ilustrarei esse conceito com exemplos de código específicos em Swift, mas os conceitos que apresento podem ser aplicados à sua linguagem de escolha. Vamos começar! 

Uma maneira de pensar

Ao contrário da sintaxe de codificação específica ou dos padrões de design, a programação dinâmica não é um algoritmo específico, mas uma maneira de pensar . Portanto, a técnica assume muitas formas quando se trata de implementação. 

A ideia principal da programação dinâmica é considerar um problema significativo e dividi-lo em componentes menores e individualizados. Quando se trata de implementação, as técnicas ideais dependem do armazenamento e reutilização de dados para aumentar a eficiência do algoritmo. Como veremos, muitas questões no desenvolvimento de software são resolvidas usando várias formas de programação dinâmica. O truque é reconhecer quando soluções ótimas podem ser criadas usando uma variável simples ou requerem uma estrutura de dados ou algoritmo sofisticado.

Por exemplo, variáveis ​​de código podem ser consideradas uma forma elementar de programação dinâmica. Como sabemos, o propósito de uma variável é reservar um lugar específico na memória para que um valor seja recuperado posteriormente.

//non-memoized function

func addNumbers(lhs: Int, rhs: Int) - Int {

   return lhs + rhs

}

//memoized function

func addNumbersMemo(lhs: Int, rhs: Int) - Int {

   let result: Int = lhs + rhs

     return result

}

Embora addNumbersMemoacima forneça uma introdução simples, o objetivo de uma solução de programação dinâmica é preservar os valores vistos anteriormente porque a alternativa pode ser ineficiente ou impedir que você responda à pergunta. Essa técnica de design é conhecida como memoização . 

Desafio de código—Par de números

Ao longo dos anos, tive a chance de conduzir entrevistas simuladas com dezenas de desenvolvedores que se preparavam para entrevistas em grandes empresas como Apple, Facebook e Amazon. A maioria de nós ficaria feliz em pular as realidades do temido quadro branco ou projeto de codificação para levar para casa. No entanto, o fato é que muitas dessas perguntas desafiadoras são projetadas para testar uma compreensão básica dos fundamentos da ciência da computação. Por exemplo, considere o seguinte:

/*

In a technical interview, you've been given an array of numbers and you need to find a pair of numbers that are equal to the given target value. Numbers can be either positive, negative, or both. Can you design an algorithm that works in O(n)—linear time or greater?

let sequence = [8, 10, 2, 9, 7, 5]

let results = pairValues(sum: 11) = //returns (9, 2)

*/

Como desenvolvedores, sabemos que geralmente existem várias maneiras de chegar a uma solução. Nesse caso, o objetivo é saber quais números devem ser pareados para alcançar o resultado esperado. Como pessoas, é fácil para nós escanear rapidamente a sequência de números e chegar rapidamente ao par de 9 e 2. No entanto, um algoritmo precisará verificar e comparar cada valor na sequência ou desenvolver uma solução mais simplificada para ajudar encontrarmos os valores que procuramos. Vamos rever ambas as técnicas.

Uma abordagem de força bruta

Nossa primeira abordagem envolve examinar o primeiro valor e, em seguida, revisar cada valor subsequente para determinar se ele fornecerá a diferença necessária para resolver a questão. Por exemplo, uma vez que nosso algoritmo verifica o valor do primeiro item do array, 8, ele então varrerá os valores restantes para 3 (por exemplo, 11 – 8 = 3). No entanto, podemos ver que o valor de 3 não existe, então o algoritmo repetirá o mesmo processo para o próximo valor (no nosso caso, 10) até encontrar um par de correspondência bem-sucedido. Sem entrar nos detalhes da notação big-O, podemos supor que esse tipo de solução teria um tempo de execução médio de O(n ^ 2)time ou maior, principalmente porque nosso algoritmo funciona comparando cada valor com todos os outros valores. No código, isso pode ser representado da seguinte forma:

let sequence = [8, 10, 2, 9, 7, 5]

//non-memoized version - O(n ^ 2)

func pairNumbers(sum: Int) - (Int, Int) {

 for a in sequence {

      let diff = sum - a

      for b in sequence {

          if (b != a) (b == diff) {

              return (a, b)

          }

      }

 }    

 return (0, 0)

}

Uma abordagem memorizada

Em seguida, vamos tentar uma abordagem diferente usando a ideia de memorização. Antes de implementar nosso código, podemos pensar em como armazenar valores vistos anteriormente ajudará a simplificar o processo. Embora o uso de uma matriz padrão seja viável, um objeto de coleção de conjuntos (também conhecido como tabela de hash ou mapa de hash) pode fornecer uma solução otimizada.

//memoized version - O(n + d)

func pairNumbersMemoized(sum: Int) - (Int, Int) {

 var addends = SetInt()

 for a in sequence {

      let diff = sum - a

     if addends.contains(diff) { //O(1) - constant time lookup

           return (a, diff)

      }

      //store previously seen value

      else {

          addends.insert(a)

      }

      }

 return (0, 0)

 }

Usando uma abordagem memoizada, melhoramos a eficiência média do tempo de execução do algoritmo para O(n + d) adicionando valores vistos anteriormente a um objeto de coleção definido. Aqueles familiarizados com estruturas baseadas em hash saberão que a inserção e recuperação de itens ocorre em O(1) – tempo constante. Isso agiliza ainda mais a solução, pois o conjunto é projetado para recuperar valores de forma otimizada, independentemente do tamanho. 

A sequência de Fibonacci

Ao aprender várias técnicas de programação, um tópico que vem à mente é a recursão. As soluções recursivas funcionam tendo um modelo que se refere a si mesmo. Como tal, as técnicas recursivas são implementadas através de algoritmos ou estruturas de dados. Um exemplo bem conhecido de recursão pode ser visto com a sequência de Fibonacci - uma sequência numérica feita adicionando os dois números anteriores (0, 1, 1, 2, 3, 5, 8, 13, 21, etc):

public func fibRec(_ n: Int) - Int {

     if n 2 {

         return n

     } else {

         return fibRec(n-1) + fibRec(n-2)

     }

 }

Quando examinado, nosso código está livre de erros e funciona conforme o esperado. No entanto, observe algumas coisas sobre o desempenho do algoritmo:

Cargos (n) fibRec()– Número de vezes que ligou

   2                    1

   4                    5

  10                 109

  15                 1219

Como mostrado, há um aumento significativo no número de vezes que nossa função é chamada. Semelhante ao nosso exemplo anterior, o desempenho do algoritmo diminui exponencialmente com base no tamanho da entrada. Isso ocorre porque a operação não armazena valores calculados anteriormente. Sem acesso a variáveis ​​armazenadas, a única maneira de obter os valores necessários (anteriores) é por meio de recursão. Supondo que esse código seja usado em uma configuração de produção, a função pode apresentar bugs ou erros de desempenho. Vamos refatorar o código para dar suporte a uma abordagem memoizada:

func fibMemoizedPosition(_ n: Int) - Int {

     var sequence: ArrayInt = [0, 1]

     var results: Int = 0

     var i: Int = sequence.count

     //trivial case

     guard n i else {

         return n

     }

     //all other cases..

     while i = n {

         results = sequence[i - 1] + sequence[i - 2]

         sequence.append(results)

         i += 1

     }

     return results

}

Esta solução revisada agora oferece suporte à memorização por meio do uso de variáveis ​​armazenadas. Observe como o código refatorado não requer mais uma técnica recursiva. Os dois valores mais anteriores são adicionados a um resultado, que é anexado à sequência da matriz principal. Embora o desempenho do algoritmo ainda dependa do tamanho da sequência, nossas revisões aumentaram a eficiência algorítmica para O(n) – tempo linear. Além disso, nossa solução iterativa deve ser mais fácil de revisar, testar e depurar, pois uma única função é adicionada à pilha de chamadas, reduzindo assim as complexidades com gerenciamento de memória e escopo de objeto.

Conclusão

Aprendemos que a programação dinâmica não é um padrão de design específico, pois é uma maneira de pensar. Seu objetivo é criar uma solução para preservar os valores vistos anteriormente para aumentar a eficiência do tempo. Embora os exemplos incluam algoritmos básicos, a programação dinâmica fornece uma base em quase todos os programas. Isso inclui o uso de variáveis ​​simples e estruturas de dados complexas.