Programação dinâmica: exemplos, problemas comuns e soluções

Não há dúvida de que os problemas de programação dinâmica podem ser muito intimidantes em uma entrevista de codificação. Mesmo quando você sabe que um problema precisa ser resolvido usando um método de programação dinâmico, é um desafio ser capaz de chegar a uma solução funcional em um período de tempo limitado.

A melhor maneira de ser bom em problemas de programação dinâmica é passar por tantos deles quanto possível. Embora você não precise necessariamente memorizar a solução para cada problema, é bom ter uma ideia de como implementar uma.

O que é programação dinâmica?

Simplificando, a programação dinâmica é um método de otimização para algoritmos recursivos, muitos dos quais são usados ​​para resolver problemas de computação ou matemáticos.

Você também pode chamá-la de técnica algorítmica para resolver um problema de otimização, dividindo-a em subproblemas mais simples. Um princípio fundamental no qual a programação dinâmica se baseia é que a solução ótima para um problema depende das soluções para seus subproblemas.

Sempre que vemos uma solução recursiva que tem chamadas repetidas para as mesmas entradas, podemos otimizá-la usando a programação dinâmica. A ideia é simplesmente armazenar os resultados dos subproblemas para que não tenhamos que recalculá-los quando necessário posteriormente.

Soluções programadas dinamicamente têm uma complexidade polinomial que garante um tempo de execução muito mais rápido do que outras técnicas como recursão ou retrocesso. Na maioria dos casos, a programação dinâmica reduz as complexidades do tempo, também conhecidas como big-O, de exponencial para polinomial.

O que é notação Big-O?

Seu código precisa ser eficiente, mas como você mostra o quão eficiente algo é? Com o Big-O!

Agora que você tem uma boa ideia do que é programação dinâmica, é hora de verificar alguns problemas comuns e suas soluções.

Problemas de programação dinâmica

1. Problema da mochila

Declaração do Problema

Dado um conjunto de itens, cada um com um peso e um valor, determine o número de cada item a ser incluído em um coleta de modo que o peso total não exceda um determinado limite e o valor total seja tão grande quanto possível.

Você recebeu duas matrizes de inteiros valores [0..n-1] e pesos [0..n-1] que representam valores e pesos associados a n itens, respectivamente. Também é fornecido um número inteiro C que representa a capacidade da mochila.

Aqui estamos resolvendo o problema da mochila 0/1, o que significa que podemos escolher adicionar um item ou excluí-lo.

Algoritmo

• Crie uma matriz bidimensional com n + 1 linhas e w + 1 colunas. Um número de linha n denota o conjunto de itens de 1 a eu, e um número de coluna C denota a capacidade máxima de carga da bolsa.
• O valor numérico em [eu j] denota o valor total dos itens até eu em uma bolsa que pode carregar um peso máximo de j.
• Em cada coordenada [eu j] na matriz, escolha o valor máximo que podemos obter sem item i, ou o valor máximo que podemos obter com item io que for maior.
• O valor máximo que pode ser obtido incluindo o item i é a soma do item eu em si e o valor máximo que pode ser obtido com a capacidade restante da mochila.
• Execute esta etapa até encontrar o valor máximo para o C^º fileira.

Código

def FindMax (W, n, valores, pesos):
MaxVals = [[0 para x no intervalo (W + 1)] para x no intervalo (n + 1)]
para i no intervalo (n + 1):
para w no intervalo (W + 1):
se i == 0 ou w == 0:
MaxVals [i] [w] = 0
pesos elif [i-1] <= w:
MaxVals [i] [w] = max (valores [i-1]
+ MaxVals [i-1] [pesos w [i-1]], 
MaxVals [i-1] [w])
outro:
MaxVals [i] [w] = MaxVals [i-1] [w]
retornar MaxVals [n] [W]

2. Problema de troca de moeda

Declaração do Problema

Suponha que você receba uma matriz de números que representa os valores de cada moeda. Dada uma quantia específica, encontre o número mínimo de moedas necessárias para fazer essa quantia.

Algoritmo

• Inicializa uma matriz de tamanho n + 1, onde n é a quantidade. Inicialize o valor de cada índice eu na matriz para ser igual ao valor. Isso denota o número máximo de moedas (usando moedas de denominação 1) necessárias para perfazer esse montante.
• Uma vez que não há denominação para 0, inicialize o caso base onde matriz [0] = 0.
• Para todos os outros índices eu, comparamos o valor nele (que é inicialmente definido como n + 1) com o valor matriz [i-k] +1, Onde k é menos do que eu. Isso essencialmente verifica todo o array até i-1 para encontrar o número mínimo possível de moedas que podemos usar.
• Se o valor for qualquer matriz [i-k] + 1 é menor do que o valor existente em array [i], substitua o valor em array [i] com aquele em matriz [i-k] +1.

Código

def coin_change (d, amount, k):
números = [0] * (valor + 1)
para j no intervalo (1, valor + 1):
mínimo = quantidade
para i no intervalo (1, k + 1):
if (j> = d [i]):
mínimo = min (mínimo, 1 + números [j-d [i]])
números [j] = mínimo
números de retorno [montante]

3. Fibonacci

Declaração do Problema

A Série de Fibonacci é uma sequência de inteiros onde o próximo inteiro na série é a soma dos dois anteriores.

É definido pela seguinte relação recursiva: F (0) = 0, F (n) = F (n-1) + F (n-2), Onde F (n) é então^º prazo. Neste problema, temos que gerar todos os números em uma sequência de Fibonacci até um determinado n^º prazo.

Algoritmo

• Primeiro, use uma abordagem recursiva para implementar a relação de recorrência fornecida.
• Resolver recursivamente este problema envolve quebrar F (n) em F (n-1) + F (n-2)e, em seguida, chamar a função com F (n-1) e F (n + 2) como parâmetros. Fazemos isso até os casos básicos onde n = 0, ou n = 1 são alcançados.
• Agora, usamos uma técnica chamada memoização. Armazene os resultados de todas as chamadas de função em uma matriz. Isso garantirá que para cada n, F (n) só precisa ser calculado uma vez.
• Para quaisquer cálculos subsequentes, seu valor pode simplesmente ser recuperado da matriz em tempo constante.

Código

def fibonacci (n): 
fibNums = [0, 1] 
para i no intervalo (2, n + 1):
fibNums.append (fibNums [i-1] + fibNums [i-2])
retornar fibNums [n] 

4. Subseqüência mais longa e crescente

Declaração do Problema

Encontre o comprimento da maior subsequência crescente dentro de um determinado array. A maior subsequência crescente é uma subsequência dentro de uma matriz de números com uma ordem crescente. Os números dentro da subsequência têm que ser únicos e em ordem crescente.

Além disso, os itens da sequência não precisam ser consecutivos.

Algoritmo

• Comece com uma abordagem recursiva onde você calcula o valor da maior subsequência crescente de cada submatriz possível do índice zero ao índice i, onde i é menor ou igual ao tamanho do variedade.
• Para transformar esse método em dinâmico, crie uma matriz para armazenar o valor de cada subsequência. Inicialize todos os valores desta matriz para 0.
• Cada índice eu desta matriz corresponde ao comprimento da maior subsequência crescente para uma submatriz de tamanho eu.
• Agora, para cada chamada recursiva de findLIS (arr, n), Verifica a n^º índice da matriz. Se este valor for 0, calcule o valor usando o método da primeira etapa e armazene-o no n^º índice.
• Finalmente, retorne o valor máximo da matriz. Este é o comprimento da maior subsequência crescente de um determinado tamanho n.

Código

def findLIS (myArray):
n = len (meuVetor)
lis = [0] * n
para i no intervalo (1, n):
para j no intervalo (0, i):
if myArray [i]> myArray [j] e lis [i] lis [i] = lis [j] +1
maxVal = 0
para i no intervalo (n):
maxVal = max (maxVal, lis [i])
return maxVal

Soluções para problemas de programação dinâmica

Agora que você já passou por alguns dos problemas de programação dinâmica mais populares, é hora de tentar implementar as soluções sozinho. Se você estiver travado, pode sempre voltar e consultar a seção de algoritmo para cada problema acima.

Dada a popularidade de técnicas como recursão e programação dinâmica hoje, não custa nada verificar algumas plataformas populares onde você pode aprender esses conceitos e aprimorar suas habilidades de codificação. Embora você possa não se deparar com esses problemas diariamente, certamente os encontrará em uma entrevista técnica.

Naturalmente, ter o know-how de problemas comuns certamente renderá dividendos na sua próxima entrevista. Então abra seu IDE favoritoe comece!

Os 9 melhores canais do YouTube codificados para aprender programação

Pronto para começar a programar? Esses canais do YouTube são uma ótima maneira de começar no desenvolvimento de jogos, aplicativos, web e outros.

Sobre o autor