Subida de Escadas e Combinações de Moedas
Crie recorrências clássicas unidimensionais do zero.
Subida de Escadas e Combinações de Moedas é uma aula grátis de Competitive Programming Academy no CoddyKit. Esta é a aula 3 de 4. Você pode ler a aula completa abaixo gratuitamente — depois pratica ao vivo no navegador com um editor de código integrado e um tutor de IA 24/7. Faz parte do caminho de aprendizado de Competitive Programming Academy, e seu progresso é sincronizado entre a web e o app CoddyKit. O curso de Competitive Programming Academy inclui 4 aulas no total.
Conheça o problema das escadas
Você pode subir 1 ou 2 degraus por vez. De quantas maneiras é possível chegar ao degrau n? Esta clássica DP 1D é apenas Fibonacci disfarçado.
Encontre a recorrência
Para chegar ao degrau i, você veio de i-1 ou i-2. Portanto, dp[i] = dp[i-1] + dp[i-2], somando os dois últimos movimentos.
dp[i] = dp[i-1] + dp[i-2]Defina os casos-base
Há uma maneira de permanecer no chão e uma de chegar ao degrau 1. Esses casos-base iniciam toda a tabela.
dp[0], dp[1] = 1, 1Preencha e leia a resposta
Percorra os degraus para cima, e a última célula conterá a contagem. A solução completa é um pequeno laço de preenchimento da tabela.
for i in range(2, n+1):
dp[i] = dp[i-1] + dp[i-2]Reduza a duas variáveis
Você só precisa dos dois últimos valores, então elimine o vetor. Esta versão com espaço O(1) é a favorita das competições.
a, b = 1, 1
for _ in range(n):
a, b = b, a+bPasse para combinações de moedas
Dados os valores das moedas, conte as maneiras de formar o valor A. A ordem não importará aqui; portanto, contamos combinações, não sequências.
coins = [1, 2, 5]A tabela de combinações
Seja dp[x] o número de maneiras de formar x. Comece com uma maneira de formar zero: o conjunto vazio de moedas.
dp = [0]*(A+1)
dp[0] = 1Coloque as moedas no laço externo
Coloque o laço das moedas por fora do laço do valor. Essa ordem conta cada combinação exatamente uma vez, nunca permutações.
for c in coins:
for x in range(c, A+1):
dp[x] += dp[x-c]Combinações versus permutações
Troque a ordem dos laços e, em vez disso, você contará maneiras ordenadas. Apenas o aninhamento dos laços altera o significado da resposta.
Variante de troco mínimo
Para obter o menor número de moedas, armazene um mínimo em vez de uma soma. Inicialize com infinito e use 1 mais o melhor subproblema.
dp[x] = min(dp[x], dp[x-c] + 1)Um padrão, muitas formas
Escadas e moedas compartilham uma estrutura: cada estado soma ou minimiza entre alguns estados anteriores. Perceba isso, e o código praticamente se escreverá sozinho.
Verificação rápida
Ao contar combinações de moedas, qual ordem dos laços evita duplicatas?
Recapitulação: some os últimos movimentos
Agora você consegue resolver escadas e contagem de moedas com uma recorrência 1D. Cada resposta soma alguns estados anteriores, e a ordem dos laços decide entre combinações e permutações.
Perguntas Frequentes
A aula “Subida de Escadas e Combinações de Moedas” é grátis?
Sim — o texto completo de “Subida de Escadas e Combinações de Moedas” é grátis para ler aqui na web. Para praticá-la interativamente (um editor de código integrado e um tutor de IA 24/7) e desbloquear o restante do curso de Competitive Programming Academy, atualize para CoddyKit PRO. O curso de Competitive Programming Academy inclui 4 aulas no total.
O que vou aprender em “Subida de Escadas e Combinações de Moedas”?
Crie recorrências clássicas unidimensionais do zero. Você pratica Competitive Programming Academy com código prático que executa diretamente no navegador, e um tutor de IA 24/7 responde suas dúvidas enquanto trabalha na aula.
Preciso ter experiência prévia para começar Competitive Programming Academy?
Nenhuma experiência prévia é necessária. Competitive Programming Academy no CoddyKit é estruturado para alunos iniciantes até avançados, então você pode começar aqui ou desde o início e aprender no seu ritmo. Esta é a aula 3 de 4.
Quanto tempo leva a aula “Subida de Escadas e Combinações de Moedas”?
A maioria das aulas CoddyKit leva cerca de 5–10 minutos. Cada uma é compacta e interativa, então você faz progresso constante e retoma exatamente de onde parou entre web e app.
Posso escrever e executar código nesta aula de Competitive Programming Academy?
Sim. Cada aula de Competitive Programming Academy inclui um editor de código integrado, então você escreve e executa código real direto no navegador e recebe feedback de IA instantaneamente — nenhuma configuração local necessária.
Todas as aulas deste curso
- Memoização versus Tabulação
- Defina o Estado e a Transição
- Subida de Escadas e Combinações de Moedas
- Maior Subsequência Crescente