Um exemplo simples para quem quer entender a Programação Dinâmica [fechado]

96

Estou procurando um exemplo de fácil compreensão para alguém que deseja aprender Programação Dinâmica. Existem boas respostas aqui sobre o que é programação dinâmica . A sequência de fibonacci é um ótimo exemplo, mas é muito pequena para arranhar a superfície. Parece um ótimo assunto para aprender, embora eu não tenha feito a aula de algoritmos ainda, espero que esteja na minha lista para a primavera.

algorithm dynamic-programming AraK
fonte

Respostas:

30

Confira este site: Problemas de prática de programação dinâmica

Nick Dandoulakis
fonte
1
Assistir a esta palestra do MIT video.mit.edu/watch/… e então resolver os problemas acima ajudaria você a entender por que o DP é útil.
pg2286
Caso em questão, o link do youtube no comentário já está quebrado. Novo link: youtube.com/watch?v=OQ5jsbhAv_M
AJP
Confira este conjunto de vídeos que descobri que cobre os aspectos de cima para baixo e de baixo para cima dos algoritmos de forma bastante intuitiva: youtube.com/playlist?list=PLx-Ye3Zw0WL0O_IDmbcVHlKqJuGEfw3VG
william007
Parece que o MIT moveu seu conteúdo da página principal para a página do MIT OpenCourseWare, então o link @ pg2286 fornecido é inválido. O link agora é 19. Programação dinâmica I A lista de reprodução completa Introdução aos algoritmos também está disponível
rite2hhh
7

A ideia por trás da programação dinâmica é que você armazene em cache (memoizing) soluções para subproblemas, embora eu ache que há mais do que isso.

Existem muitos problemas do Google Code Jam, de forma que as soluções exigem uma programação dinâmica para serem eficientes. Exemplos:

Bem-vindo ao Code Jam (moderado)

Trapaceando uma árvore booleana (moderado)

PermRLE (difícil)

Observe que cada um dos concursos de prática do Code Jam tem uma seção de "Análise do Concurso" para se você não conseguir resolver o problema.

Joey Adams
fonte
Obrigado pelos recursos. Resolvo uma ou duas questões do projeto euler de vez em quando, e parece que estou realmente preso a alguns problemas que precisam de conhecimento sobre DP.
AraK,
5
  1. Geeks para geeks tem uma grande coleção de problemas de programação dinâmica. Acho que este conjunto é um dos melhores se você está se preparando para uma entrevista.
  2. Se você quiser pequenos vídeos tutoriais sobre problemas de DP, você pode verificar esse conjunto de problemas no MIT.
Diptendu
fonte
4

Calcular distâncias de Levenshtein foi um dos primeiros problemas que resolvi com a programação dinâmica; Acho que é um próximo passo decente da sequência de Fibonacci em termos de complexidade.

http://en.wikipedia.org/wiki/Levenshtein_distance

David Winslow
fonte