DAA 2021/2022 (CC2001) - DCC/FCUP

Aula Prática #05 - Programação Dinâmica
(semana de 04/04 08/04)

Exercícios para submissão

Para efeitos da nota atribuída à resolução de exercícios ao longo do semestre, os exercícios a submeter desta aula são:

[DAA 017] Pirâmides (peso 50%) (exercício do guião principal)
[DAA 018] Troco de moedas (peso 50%) (exercício do guião principal)
[DAA 019] Capicuas (peso 50%) (exercício extra)
[DAA 020] Números sortudos (peso 50%) (exercício de desafio)

Prazo de submissão: 1 de Maio (submeter no Mooshak de DAA)

Não se esqueçam que qualquer ajuda que tenham recebido de outros colegas deve ser reconhecida nos comentário do programa que submetem.
Depois do prazo os problemas continuarão disponíveis no Mooshak, mas as submissões não contarão para a sua nota. Relembre que cada aula vale 10% da nota desta componente.
Para um problema contar tem acertar todos os testes. Mesmo que resolva todos os problemas, o máximo numa aula é de 100%.

Conteúdos das teóricas

Nesta aula iremos abordar conceitos de programação dinâmica. Será por isso conveniente ver o que foi falado nas teóricas:

Slides (capítulo "4 - Programação Dinâmica")
Vídeos: (vídeos #12 e #13)

Exercício 1) Programação Dinâmica - Contagens

Implemente e submeta uma solução para o problema [DAA 017] Pirâmides.

Comece por recordar os problemas "Pirâmide de Números" [slides 8 a 22] e "Obras na Estrada" [slides 46 a 50], dados nas teóricas. Este problema é no fundo um problema de contagem (como o das obras) numa pirâmide (como o dos números).
Seja count[i][j] uma matriz que diz quantos caminhos possíveis existem a partir da posição j da camada i. Como preencher esta matriz a partir de outros valores já calculados? Como percorrer a pirâmide para garantir que quando precisamos de um valor já o temos calculado?
No final onde fica o resultado que queremos escrever?
Cuidado com resultado M, porque pode não caber num int (M < 2⁶³). Use long em Java e long long em C/C++ (imprima com "%lld")

Exercício 2) Programação Dinâmica - Mínimo e reconstrução de solução

Implemente e submeta uma solução para o problema [DAA 018] Troco de moedas.

Este problema foi explicado nas aulas teóricas [slides 41 a 45].

Exercício extra 1) Programação Dinâmica - Strings

Este exercício é um extra, e não é considerado essencial no contexto desta aula. Use-o se quiser consolidar os seus conhecimentos num problema um pouco mais complicado, pois implica ser eficiente (para além de correcto).

Implemente e submeta uma solução para o problema [DAA 019] Capicuas.

Exercício Extra 2) Programação Dinâmica - Partições

Se quiserem treinar, podem voltar a resolver o problema [DAA 011] Viagem de Mochila às Costas, mas agora com Programação Dinâmica. Conseguem imaginar como? Falem com o docente nas aulas se quiserem ter dicas.

Exercício de Desafio

Todas as semanas vou colocar disponível pelo menos mais um exercício um pouco mais desafiante.

Para esta semana o desafio é resolver um problema do nível de uma final das (a Olimpíadas Nacionais de Informática), o concurso de programação mais prestigiado para alunos pré-universitários nacionais. O problema, criado por mim, era um dos mais "complicados" da final de 2016 e está disponível para submissão no Mooshak:

[DAA 020] Números sortudos

Se já tiverem feito tudo e estiverem "presos" neste, e quiserem mesmo fazer o desafio, podem contactar-me para eu "dosear" as dicas, sabendo que este problema é substancialmente mais complicado que os outros desta aula e é também algoritmicamente o desafio mais complicado que já coloquei nas aulas de DAA 21/22.