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?

imagem2

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?

imagem3

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.

9 ideias sobre “Lajotas Hexagonais”

  1. Olá, muito bom! Estou começando a entender como usar DP 😀
    Só uma coisa, no caso base: nc[N-1] = 1; não deveria ser nc[N-1] = 2;?

    1. Olá William.

      Dá uma olhada na imagem acima. Na lajota N-1, só temos uma opção: andar para a lajota N. Logo, esse caso base tem valor 1.

  2. Bonilha párabes pela iniciativa mas fiquei com algumas dúvidas aqui tipo se em n pra chegar até o n não seria 0 ? Visto que estou aqui ? Outra dúvida porque percorrer ao contrário ? Da direita pra esquerda o oposto não seria válido? Porque ? Obrigado

  3. Bonilha parabéns pela iniciativa mas fiquei com algumas dúvidas aqui tipo se estou em n pra chegar até o n não seria 0 ? Visto que estou aqui ? Como seria 1 caminho já? Outra dúvida porque percorrer ao contrário ? Da direita pra esquerda o oposto não seria válido? Porque ? Obrigado

  4. Neste trecho…
    “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.”

    Não seria 0 ? Se estou em n preciso de 0 caminhos até n não? Pois já me encontro em n

    E outra porque percorrer da direita pra esquerda ? O oposto não seria válido? Obrigado

  5. Li com calma entendi a idéia bacana

    Calcular Fibonacci ao contrário poderia calcular tb até n+1 e mostrar mas td bem bacana a idéia de empregar conceitos de programacao dinâmica nesse problema

Deixe uma resposta

O seu endereço de e-mail não será publicado. Campos obrigatórios são marcados com *