Recuento de formas de recorrer un camino cíclico en N pasos en una pirámide triangular

Dada una pirámide triangular con sus vértices marcados como O, A, B y C y un número N , la tarea es encontrar el número de formas en que una persona que parte del origen O inicialmente llega al origen en N pasos. En un solo paso, una persona puede ir a cualquiera de sus vértices adyacentes.
 

Ejemplos: 
 

Entrada: N = 1 
Salida: 0 
Explicación: 
En 1 paso, es imposible volver a estar en la posición O.
Entrada: N = 2 
Salida: 3 
Explicación: 
Las tres formas de volver a O en dos pasos son: 
O-> A->O 
O->B->O 
O->C->O
Entrada: N = 3 
Salida: 6 
Explicación: 
Las 6 formas de volver a O en tres pasos son: 
O->A->B-> O 
O->A->C->O 
O->B->A->O 
O->B->C->O 
O->C->A->O 
O->C->B-> O 
 

Planteamiento: La idea es utilizar el concepto de programación Dinámica . 
 

1. Se crea una tabla T[][] donde la fila representa el número de formas y la columna representa la posición.
2. Para llenar la tabla, se necesita hacer una observación. Es decir, podemos volver a la posición O si no estamos en O en el paso anterior.
3. Por lo tanto, el número de formas de llegar al origen O en el paso actual es igual a la suma del número de formas en que la persona no está en el origen O en los pasos anteriores.
4. Entendamos cómo se llena la tabla para N = 3: 
    

    0   1    2   3
O   1   0    3   6
A   0   1    2   7
B   0   1    2   7
C   0   1    2   7

1. El caso base de esta tabla es cuando N = 1. Podemos llegar al origen en 1 paso desde todas las posiciones excepto O.

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

// C++ program for Dynamic
// Programming implementation of
// Number of Path in a Triangular
// pyramid
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the number of
// ways we can reach back to the
// initial position O
 
int fun(int n)
{
    int sum=0;
    for(int i=1;i<n;i++)
    {
      sum=sum*3;
      if(i%2)
      {
        sum+=3;
      }
      else
      {
        sum-=3;
      }
     }
     return sum;
}
 
// Driver code
int main()
{
 
    int n = 3;
    cout << fun(n) << endl;
 
    n = 4;
    cout << fun(n) << endl;
 
    return 0;
}

// Java program for dynamic programming
// implementation of number of path in
// a triangular pyramid
class GFG{
 
// Function to return the number of
// ways we can reach back to the
// initial position O
static int count(int n)
{
     
    // If n is 0 then there is
    // 1 solution
    if (n == 0)
        return 1;
 
    // If n is equal to 1 then we
    // can't reach at position O
    if (n == 1)
        return 0;
 
    int [][]dp = new int[4][n + 1];
 
    // Initial Conditions
 
    // Represents position O
    dp[0][0] = 1;
 
    // Represents position A
    dp[1][0] = 0;
 
    // Represents position B
    dp[2][0] = 0;
 
    // Represents position C
    dp[3][0] = 0;
 
    // Filling the table
    for(int i = 1; i <= n; i++)
    {
        
       // The number of ways to reach
       // a particular position (say X)
       // at the i'th step is equivalent
       // to the sum of the number
       // of ways the person is not at
       // position X in the last step.
       int countPositionO = dp[1][i - 1] +
                            dp[2][i - 1] +
                            dp[3][i - 1];
       int countPositionA = dp[0][i - 1] +
                            dp[2][i - 1] +
                            dp[3][i - 1];
       int countPositionB = dp[0][i - 1] +
                            dp[1][i - 1] +
                            dp[3][i - 1];
       int countPositionC = dp[0][i - 1] +
                            dp[1][i - 1] +
                            dp[2][i - 1];
        
       dp[0][i] = countPositionO;
       dp[1][i] = countPositionA;
       dp[2][i] = countPositionB;
       dp[3][i] = countPositionC;
    }
    return dp[0][n];
}
 
// Driver code
public static void main(String[] args)
{
    int n = 3;
    System.out.print(count(n) + "\n");
 
    n = 4;
    System.out.print(count(n) + "\n");
}
}
 
// This code is contributed by sapnasingh4991

# Python3 program for Dynamic
# Programming implementation of
# Number of Path in a Triangular
# pyramid
 
# Function to return the number of
# ways we can reach back to the
# initial position O
def count(n):
 
    # If n is 0 then there is
    # 1 solution
    if (n == 0):
        return 1
 
    # If n is equal to 1
    # then we can't reach at position O
    if (n == 1):
        return 0
 
    dp = [[0 for i in range(n + 1)]
             for j in range(4)]
 
    # Initial Conditions
 
    # Represents position O
    dp[0][0] = 1
 
    # Represents position A
    dp[1][0] = 0
 
    # Represents position B
    dp[2][0] = 0
 
    # Represents position C
    dp[3][0] = 0
 
    # Filling the table
    for i in range(1, n + 1):
 
        # The number of ways to reach
        # a particular position (say X)
        # at the i'th step is equivalent
        # to the sum of the number
        # of ways the person is not at
        # position X in the last step.
 
        countPositionO = (dp[1][i - 1] +
                          dp[2][i - 1] +
                          dp[3][i - 1])
 
        countPositionA = (dp[0][i - 1] +
                          dp[2][i - 1] +
                          dp[3][i - 1])
 
        countPositionB = (dp[0][i - 1] +
                          dp[1][i - 1] +
                          dp[3][i - 1])
 
        countPositionC = (dp[0][i - 1] +
                          dp[1][i - 1] +
                          dp[2][i - 1])
 
        dp[0][i] = countPositionO
        dp[1][i] = countPositionA
        dp[2][i] = countPositionB
        dp[3][i] = countPositionC
     
    return dp[0][n]
 
# Driver code
if __name__ == "__main__":
 
    n = 3
    print(count(n))
 
    n = 4
    print(count(n))
 
# This code is contributed by ChitraNayal

// C# program for dynamic programming
// implementation of number of path in
// a triangular pyramid
using System;
 
class GFG{
 
// Function to return the number
// of ways we can reach back to
// the initial position O
static int count(int n)
{
     
    // If n is 0 then there is
    // 1 solution
    if (n == 0)
        return 1;
 
    // If n is equal to 1 then we
    // can't reach at position O
    if (n == 1)
        return 0;
 
    int [,]dp = new int[4, n + 1];
 
    // Initial Conditions
 
    // Represents position O
    dp[0, 0] = 1;
 
    // Represents position A
    dp[1, 0] = 0;
 
    // Represents position B
    dp[2, 0] = 0;
 
    // Represents position C
    dp[3, 0] = 0;
 
    // Filling the table
    for(int i = 1; i <= n; i++)
    {
         
       // The number of ways to reach
       // a particular position (say X)
       // at the i'th step is equivalent
       // to the sum of the number
       // of ways the person is not at
       // position X in the last step.
       int countPositionO = dp[1, i - 1] +
                            dp[2, i - 1] +
                            dp[3, i - 1];
       int countPositionA = dp[0, i - 1] +
                            dp[2, i - 1] +
                            dp[3, i - 1];
       int countPositionB = dp[0, i - 1] +
                            dp[1, i - 1] +
                            dp[3, i - 1];
       int countPositionC = dp[0, i - 1] +
                            dp[1, i - 1] +
                            dp[2, i - 1];
        
       dp[0, i] = countPositionO;
       dp[1, i] = countPositionA;
       dp[2, i] = countPositionB;
       dp[3, i] = countPositionC;
    }
    return dp[0, n];
}
 
// Driver code
public static void Main(String[] args)
{
    int n = 3;
    Console.Write(count(n) + "\n");
 
    n = 4;
    Console.Write(count(n) + "\n");
}
}
 
// This code is contributed by sapnasingh4991

<script>
// Javascript program for dynamic programming
// implementation of number of path in
// a triangular pyramid
 
// Function to return the number of
// ways we can reach back to the
// initial position O
function count(n)
{
 
    // If n is 0 then there is
    // 1 solution
    if (n == 0)
        return 1;
   
    // If n is equal to 1 then we
    // can't reach at position O
    if (n == 1)
        return 0;
   
    let dp = new Array(4);
    for(let i = 0; i < 4; i++)
    {
        dp[i] = new Array(n + 1);
        for(let j = 0; j < (n + 1); j++)
        {
            dp[i][j] = 0;
        }
    }
   
    // Initial Conditions
   
    // Represents position O
    dp[0][0] = 1;
   
    // Represents position A
    dp[1][0] = 0;
   
    // Represents position B
    dp[2][0] = 0;
   
    // Represents position C
    dp[3][0] = 0;
   
    // Filling the table
    for(let i = 1; i <= n; i++)
    {
          
       // The number of ways to reach
       // a particular position (say X)
       // at the i'th step is equivalent
       // to the sum of the number
       // of ways the person is not at
       // position X in the last step.
       let countPositionO = dp[1][i - 1] +
                            dp[2][i - 1] +
                            dp[3][i - 1];
       let countPositionA = dp[0][i - 1] +
                            dp[2][i - 1] +
                            dp[3][i - 1];
       let countPositionB = dp[0][i - 1] +
                            dp[1][i - 1] +
                            dp[3][i - 1];
       let countPositionC = dp[0][i - 1] +
                            dp[1][i - 1] +
                            dp[2][i - 1];
          
       dp[0][i] = countPositionO;
       dp[1][i] = countPositionA;
       dp[2][i] = countPositionB;
       dp[3][i] = countPositionC;
    }
    return dp[0][n];
}
 
// Driver code
let n = 3;
    document.write(count(n) + "<br>");
   
    n = 4;
    document.write(count(n) + "<br>");
 
// This code is contributed by avanitrachhadiya2155
</script>

6
21

Complejidad temporal: O(N). 
Complejidad del espacio auxiliar: O(1)
Nota: 
 

• Este programa funciona de manera más eficiente para encontrar el número de formas en tiempo constante después del preprocesamiento de múltiples consultas si llenamos la tabla con el mayor número entre el conjunto de consultas.