Lajotas Hexagonais

Neste post vou explicar como resolver o exercício Lajotas Hexagonais [link], utilizando o conceito de Programação Dinâmica.

Esse exercício é bem simples, e é um bom começo para quem ainda não tem familiaridade com o conceito de Programação Dinâmica.

Clique no link abaixo para ver o resto do post.

O conceito de Programação Dinâmica pode ser explicado de diversas formas, e eu vou usar uma delas aqui.
Vou dividir o exercício em problema principal, e sub-problema:

• Problema principal é o problema objetivo, aquele o qual queremos saber a resposta.
• Sub-problema é um problema semelhante ao problema principal. Ele não é o problema objetivo, mas a sua resolução pode ajudar na resolução do problema objetivo.

Com essa breve definição em mente, voltemos nossa atenção ao exercício: desejamos descobrir o número de caminhos diferentes, partindo-se da lajota 0 (aquela com o rosto sorridente), e terminando na lajota N.

Aqui o problema principal é óbvio: Número de caminhos, iniciando da lajota 0, e terminando na lajota N.

Mas qual é o sub-problema?
De acordo com a definição, ele é semelhante ao problema principal.
Vamos tentar isso: Número de caminhos, iniciando da lajota K, e terminando na lajota N.

É semelhante ao problema principal, e desde que K seja diferente de 0, ele não é o problema objetivo.

Ok, definidos o problema principal e os sub-problemas, como é que um sub-problema pode ajudar na resolução do problema principal, ou até na resolução de outros sub-problemas?

Vamos visualizar o problema. Se estamos na lajota K, para onde podemos andar?

Ok, se estamos na lajota K, temos dois caminhos: Podemos ir para a lajota K+1, e seguir caminho de lá até a lajota N; ou podemos ir para a lajota K+2, e seguir caminho de lá até a lajota N.

Se, por acaso, formos para a lajota K+1. E agora, para onde podemos andar?

Notaram a semelhança?

Todos os sub-problemas são iguais, a única coisa que muda é o valor de K. E o melhor: todos estão relacionados entre si!
Se resolvermos um, ajudaremos a resolver outro, e isso consequentemente nos levará à resolução do problema principal, uma vez que ele é semelhante ao sub-problema, e também está relacionado com eles.

Vamos bolar uma fórmula: seja “nc” igual a “número de caminhos”, temos:
nc[K] = nc[K+1] + nc[K+2].

Para descobrirmos nc[K], precisamos descobrir nc[K+1] e nc[K+2]. Para descobrirmos nc[K+1], precisamos descobrir nc[K+2] e nc[K+3]. Quando isso acaba?
Apresento-lhes uma coisa chamada caso base.
Caso base é aquele sub-problema tão ridiculamente simples, que não é preciso recorrer a outros sub-problemas para resolvê-lo. Você pode resolvê-lo sozinho.

Por exemplo, se estamos na lajota N, quantos caminhos há até a lajota N? Oras, 1, pois já estamos lá.
E se estamos na lajota N-1, quantos caminhos há até a lajota N? Oras, 1, pois é só seguir em frente.

Agora basta resolver os sub-problemas, da direita para a esquerda, e chegaremos ao problema final. Eis o código em C++:

// número de lajotas
int N;
scanf("%d", &N);

// vetor com as respostas dos sub-problemas
int nc[N+1];

// casos bases
nc[N] = 1;
nc[N-1] = 1;

// sub-problemas
for(int K=N-2; K>=0; K--) {
     nc[K] = nc[K+1] + nc[K+2];
}
// o problema principal é resolvido quando K é igual a 0, no laço acima.

// resposta
printf("%d\n", nc[0]);

Qualquer dúvida, sugestão ou crítica, deixe um comentário abaixo.