Perguntas sobre 'dynamic-programming'

4
respostas

Como você identifica um problema como adequado para programação dinâmica?

Eu tenho lido sobre programação dinâmica ultimamente. Gostaria de ouvir de alguém que começou do zero e agora é muito bom em identificar e resolver problemas de DP. Eu estou lutando para identificar esses problemas como DP e estruturar uma soluç...
28.11.2013 / 21:57
3
respostas

número de cadeias de caracteres, quando cada caractere deve ocorrer até mesmo

Eu tenho batido meu crânio neste problema há algum tempo, e isso realmente está começando a me frustrar. O problema é: Eu tenho um conjunto de caracteres, A , B , C e D . Eu tenho que dizer de quantas maneiras uma string pode ser con...
09.02.2015 / 23:08
2
respostas

Como o “problema de coleta de pizza” é resolvido usando técnicas de programação dinâmica?

Problema de coleta de pizza de Winkler: Uma pizza de pizza circular de n fatias, onde a fatia i tem área S_i , ou seja, a área é diferente para cada peça de pizza. Comedores Alice e Bob se revezam escolhendo fatias, mas é rude cria...
31.10.2011 / 16:23
2
respostas

Como melhorar na resolução de problemas de programação dinâmica

Recentemente me deparei com essa pergunta: "Você recebe uma expressão booleana que consiste em uma string dos símbolos 'true', 'false', 'e', 'ou' e 'xor'. Conte o número de maneiras para parênteses a expressão de modo que ele irá avaliar a true....
20.06.2012 / 09:58
3
respostas

Maior subsequência sem string

Existe um algoritmo de programação dinâmica para encontrar a subseqüência mais longa em uma string X que não contém Y como substring? Só que esse problema parece tão semelhante a outros algoritmos de string DP, como a subsequência e a string mai...
10.03.2013 / 19:15
1
resposta

Encontrando todas as maneiras possíveis de inserir um padrão em uma string

Eu estive pensando sobre este problema por um tempo, e eu só posso encontrar uma solução recursiva, mas eu estou sentindo que existe uma maneira dinâmica de programação para fazer isso, eu simplesmente não consigo descobrir. Esse é um problema f...
09.03.2016 / 16:06
2
respostas

Encontre o caminho de descida mais íngreme junto com o comprimento do caminho em uma matriz

Enfrentou este problema - Você recebe uma grade com números que representam a elevação em um determinado ponto. De cada caixa na grade você pode ir para o norte, sul, leste, oeste - mas somente se a elevação da área em que você está entrando for...
04.01.2016 / 08:45
3
respostas

Escolhendo o número m no melhor tempo possível

Imagine que queremos escolher m números de n números para que a diferença entre o máximo e o mínimo dos números m seja mínima, por exemplo, se m = 4 n =6 numbers: 10 12 10 7 5 22 A diferença mínima é 5, escolhendo 5, 7, 10,...
29.04.2015 / 20:41
3
respostas

Número de seqüências contendo uma substring específica

Eu vi várias perguntas (e respostas) sobre o número de strings binárias (por exemplo, "10010" contendo alguma substring binária (por exemplo, "00"). Gostaria de saber se existe uma maneira de generalizar isso: Dado um comprimento n e uma s...
12.02.2015 / 14:31
1
resposta

Ajuda / sugestões para programação de linha de montagem paralela (programação dinâmica)

Estou trabalhando em um problema similar ao escalonamento de linhas de montagem por programação dinâmica. A questão é que ao contrário do problema clássico onde temos estações pré-definidas agora eu só tenho informação qual tarefa deve rodar ant...
28.11.2013 / 11:39