Programacao Dinamica - Solucoes VA - Algoritmos e Problemas

Parte II 2ª VA 5 Programação Dinâmica 51 Inteiros positivos são arranjados em um triângulo equilátero com n números em sua base como o mostrado na figura abaixo para n 4 O problema é encontrar a menor soma em uma descida do ápice do triângulo até sua base por meio de uma sequência de números adjacentes mostrados na figura pelos círculos Projete um algoritmo de programação dinâmico para este problema 52 Algumas moedas são espalhadas nas células de um tabuleiro n m uma moeda por célula Um robô localizado na célula superior esquerda do tabuleiro precisa coletar o máximo de moedas possível e trazêlas para a célula inferior direita Em cada etapa o robô pode mover uma célula para a direita ou uma célula para baixo de sua localização atual Quando o robô visita uma célula com uma moeda ele pega a moeda Elabore um algoritmo para encontrar o número máximo de moedas que o robô pode coletar e um caminho que ele precisa seguir para fazer isso 53 Apresente o pseudocódigo do algoritmo de FloydWarshall para o problema dos caminhos mínimos entre todos os pares de vértices Apresente a recorrência para o cálculo da distância 54 Projete um algoritmo eficiente para encontrar o comprimento do caminho mais longo em um DAG Este problema é importante como um protótipo de muitos outros aplicativos de programação dinâmica pois determina o tempo mínimo necessário para concluir um projeto que compreende tarefas de precedência restrita