>
A programação dinâmica pode ser a banalidade da existência da maioria dos engenheiros de software. Acho que não há nenhum tópico sobre o qual eu tenha recebido mais perguntas.
E eu entendo totalmente.
Os entrevistados adoram fazer essas perguntas porque elas são difíceis.
Os entrevistados realmente lutam porque eles não têm um framework de solução de problemas para abordar problemas de DP.
Isso significa que toda vez que você tenta resolver um problema de programação dinâmica, você está começando da estaca zero. Você não pode aplicar padrões que você viu com outros problemas de DP porque eles parecem totalmente diferentes. Então você está sempre começando de novo e tentando resolver esses problemas difíceis do zero.
Neste post, eu quero mostrar uma maneira melhor.
Os vídeos a seguir vão guiá-lo através de 6 dos problemas DP mais comuns que você pode esperar ver em suas entrevistas. Se você aprender esses problemas e aprender como aplicar o Método RÁPIDO, você estará em muito boa forma para enfrentar a programação dinâmica em suas entrevistas.
Protip: Se você ainda é novo em programação dinâmica, confira nosso ebook grátis de 42 páginas, Dynamic Programming for Interviews, first
Check out the problems:
Smallest Change
Dado uma quantidade de mudança x, escreva uma função para determinar o número mínimo de moedas necessárias para fazer essa quantidade de mudança.
eg. (usando moedas americanas)
|
1
2
3
4
> |
change(1) = 1
change(3) = 3
change(7) = 3
change(32) = 4
|
Substring Comum Mais Longo
Dado duas cordas, escrever uma função que devolva o substrato mais longo comum.
eg.
longestSubstring("ABAB", "BABA") = "ABA"
Número de Fibonacci
Dado um número inteiro n, escreva uma função para calcular o n-ésimo número de Fibonacci.
eg.
fibonacci(1) = 1fibonacci(5) = 5fibonacci(10) = 55
Submatriz quadrada
Dado um array 2D de 1s e 0s, encontre o maior subarranjo quadrado de todos os 1s.
eg.
|
1
2
3
|
subarranjo(
) = 2
|
Produto matricial
Dado uma matriz, encontrar o caminho de cima para baixo, da esquerda para a direita, com o maior produto, movendo-se apenas para baixo e para a direita.
eg.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
1 -> 4 -> 7 -> 8 -> 9
2016
-1 -> 4 -> 5 -> -6 -> 9
1080
|
0-1 Mochila
Dar uma lista de itens com valores e pesos, assim como um peso máximo, encontre o valor máximo que pode gerar a partir de itens onde a soma dos pesos é menor que o máximo.
eg.
|
1
2
3
|
itens = {(w:1, v:6), (w:2, v:10), (w:3, v:12)}
peso máximo = 5
mochila(itens, peso máximo) = 22
|