Número de caminos cíclicos diferentes de longitud N en un tetraedro

Dado un tetraedro (los vértices son A, B, C, D), la tarea es encontrar el número de caminos cíclicos diferentes con longitud n desde un vértice.
Nota: Considerando un solo vértice B, es decir, encontrar el número de caminos cíclicos diferentes de longitud N desde B hacia sí mismo.

Ejemplos: 

Input: 2
Output: 3
The paths of length 2 which starts and ends at D are:
B-A-B
B-D-B
B-C-B

Input: 3
Output: 6

Enfoque: la programación dinámica se puede utilizar para realizar un seguimiento de la cantidad de rutas para valores anteriores de N. Verifique la cantidad de movimientos que quedan y dónde estamos cuando nos movemos en una ruta. Eso es 4n estados, cada uno con 3 opciones. Observa que todos los vértices A, B, C son equivalentes. Sea zB 1 inicialmente y como en 0 pasos, solo podemos llegar a B. Sea zACD 1 ya que los caminos para llegar a otros vértices A, C y D son 0. Por lo tanto, la relación de recurrencia formada será:  

Caminos para que N pasos alcancen b es = zADC*3 

En cada paso, zADC se multiplica por 2 (2 estados) y se suma por zB ya que zB es el número de caminos en el paso n-1 que comprende los 2 estados restantes. 

A continuación se muestra la implementación del enfoque anterior:  

// C++ program count total number of
// paths to reach B from B
#include <bits/stdc++.h>
#include <math.h>
using namespace std;
 
// Function to count the number of
// steps in a tetrahedron
int countPaths(int n)
{
    // initially coming to B is B->B
    int zB = 1;
 
    // cannot reach A, D or C
    int zADC = 0;
 
    // iterate for all steps
    for (int i = 1; i <= n; i++) {
 
        // recurrence relation
        int nzB = zADC * 3;
 
        int nzADC = (zADC * 2 + zB);
 
        // memoize previous values
        zB = nzB;
        zADC = nzADC;
    }
 
    // returns steps
    return zB;
}
 
// Driver Code
int main()
{
    int n = 3;
    cout << countPaths(n);
 
    return 0;
}

// Java program count total
// number of paths to reach
// B from B
import java.io.*;
 
class GFG
{
     
// Function to count the
// number of steps in a
// tetrahedron
static int countPaths(int n)
{
    // initially coming
    // to B is B->B
    int zB = 1;
 
    // cannot reach A, D or C
    int zADC = 0;
 
    // iterate for all steps
    for (int i = 1; i <= n; i++)
    {
 
        // recurrence relation
        int nzB = zADC * 3;
 
        int nzADC = (zADC * 2 + zB);
 
        // memoize previous values
        zB = nzB;
        zADC = nzADC;
    }
 
    // returns steps
    return zB;
}
 
// Driver Code
public static void main (String[] args)
{
    int n = 3;
    System.out.println(countPaths(n));
}
}
 
// This code is contributed by ajit

# Python3 program count total number of
# paths to reach B from B
 
# Function to count the number of
# steps in a tetrahedron
def countPaths(n):
     
    # initially coming to B is B->B
    zB = 1
 
    # cannot reach A, D or C
    zADC = 0
 
    # iterate for all steps
    for i in range(1, n + 1):
 
        # recurrence relation
        nzB = zADC * 3
 
        nzADC = (zADC * 2 + zB)
 
        # memoize previous values
        zB = nzB
        zADC = nzADC
     
    # returns steps
    return zB
 
# Driver code
n = 3
print(countPaths(n))
 
# This code is contributed by ashutosh450

// C# program count total
// number of paths to reach
// B from B
using System;
 
class GFG{
         
// Function to count the
// number of steps in a
// tetrahedron
static int countPaths(int n)
{
     
    // initially coming
    // to B is B->B
    int zB = 1;
 
    // cannot reach A, D or C
    int zADC = 0;
 
    // iterate for all steps
    for (int i = 1; i <= n; i++)
    {
 
        // recurrence relation
        int nzB = zADC * 3;
 
        int nzADC = (zADC * 2 + zB);
 
        // memoize previous values
        zB = nzB;
        zADC = nzADC;
    }
 
    // returns steps
    return zB;
}
 
    // Driver Code
    static public void Main ()
    {
        int n = 3;
        Console.WriteLine(countPaths(n));
    }
}
 
// This code is contributed by Sach

<?php
// PHP program count total number
// of paths to reach B from B
 
// Function to count the number 
// of steps in a tetrahedron
function countPaths($n)
{
    // initially coming to B is B->B
    $zB = 1;
 
    // cannot reach A, D or C
    $zADC = 0;
 
    // iterate for all steps
    for ($i = 1; $i <= $n; $i++)
    {
 
        // recurrence relation
        $nzB = $zADC * 3;
 
        $nzADC = ($zADC * 2 + $zB);
 
        // memoize previous values
        $zB = $nzB;
        $zADC = $nzADC;
    }
 
    // returns steps
    return $zB;
}
 
// Driver Code
$n = 3;
echo countPaths($n);
 
 
// This code is contributed
// by Sachin
?>

<script>
 
// Javascript program count total
// number of paths to reach
// B from B
 
// Function to count the
// number of steps in a
// tetrahedron
function countPaths(n)
{
     
    // Initially coming
    // to B is B->B
    let zB = 1;
 
    // Cannot reach A, D or C
    let zADC = 0;
 
    // Iterate for all steps
    for(let i = 1; i <= n; i++)
    {
         
        // recurrence relation
        let nzB = zADC * 3;
 
        let nzADC = (zADC * 2 + zB);
 
        // Memoize previous values
        zB = nzB;
        zADC = nzADC;
    }
 
    // Returns steps
    return zB;
}
 
// Driver code
let n = 3;
document.write(countPaths(n));
 
// This code is contributed by mukesh07      
 
</script>

6