0.01. Recomendo utilizar - beecrowd para testar a implementação (https://judge.beecrowd.com /pt/problems/view/1021), observando que a correção automática envolve a necessidade de especificar a saída em uma formatação particular. 4. Considerando o problema do troco descrito na questão anterior, responda: a. Como poderíamos resolver problema usando programação dinâmica e por que essa abordagem é menos efficiente (exponencial ou pseudopolinomial)? b. Por que a abordagem gulosa pode não ser ótima em todos os cenários desse problema? Imagine por exemplo, o troco de 30 reais e que as notas disponíveis são de 50,25,10 e 1 reais.

Vamos detalhar um pouco mais as respostas para garantir que tudo esteja claro.<br /><br />### a. Programação Dinâmica<br /><br />**Como resolver usando programação dinâmica:**<br /><br />1. **Defina a matriz DP:** Crie uma matriz DP onde DP[i][j] representa o número mínimo de notas de valor i que são necessárias para formar um valor j.<br />2. **Inicialize a matriz DP:** <br /> - DP[0][j] = 0 para todos os j, pois zero notas são necessárias para formar zero.<br /> - Para j > 0, inicialize DP[i][0] = ∞ para todos os i > 0, pois não é possível formar um valor zero usando notas de valor positivo.<br />3. **Preencha a matriz DP:** Para cada i e j, considere todas as notas disponíveis (50, 25, 10, 1) e atualize DP[i][j] com o mínimo entre DP[i][j] e DP[i-50][j-50] + 1, DP[i-25][j-25] + 1, DP[i-10][j-10] + 1, DP[i-1][j-1] + 1.<br />4. **Obtenha o resultado:** O valor mínimo em DP[N][T] será o número mínimo de notas necessárias para formar o troco T.<br /><br />**Por que essa abordagem é menos eficiente:**<br /><br />- **Complexidade Exponencial:** Cada célula DP[i][j] depende de todas as células DP[i-50][j-50], DP[i-25][j-25], DP[i-10][j-10] e DP[i-1][j-1]. Isso resulta em uma complexidade de O(T * N), onde T é o valor do troco e N é o número de notas disponíveis.<br />- **Espaço Exponencial:** A matriz DP terá tamanho N x T, o que também contribui para o aumento do espaço necessário.<br /><br />### b. Abordagem Gulosa<br /><br />**Por que a abordagem gulosa pode não ser ótima:**<br /><br />- **Exemplo de falha:** Considere o troco de 30 reais e as notas disponíveis (50, 25, 10, 1). A abordagem gulosa sempre escolherá a nota maior possível para cada passo. No entanto, isso pode levar a um número maior de notas do que necessário. Por exemplo, em vez de usar uma nota de 25 reais para formar 30 reais, você poderia usar uma nota de 10 reais e uma nota de 10 reais, resultando em um número menor de notas.<br /><br />**Exemplo concreto:**<br /><br />- **Troco de 30 reais:**<br /> - Abordagem gulosa: 1 nota de 25 reais + 1 nota de 5 reais = 2 notas.<br /> - Abordagem ótima: 1 nota de 10 reais + 1 nota de 10 reais + 1 nota de 5 reais + 1 nota de 5 reais = 4 notas.<br /><br />Portanto, a abordagem gulosa pode não ser a mais eficiente ou ótima, pois pode levar a soluções subótimas em alguns casos.