Número de formas de organizar N números que están en un rango de 1 a K bajo restricciones dadas.

Dados Cuatro enteros N , K , P y Q . La tarea es calcular el número de formas de ordenar N números que están en un rango de 1 a K de modo que el primer número sea P, el último número sea Q y no haya dos números adyacentes consecutivos. 
Ejemplos: 
 

Input:  N = 4, K = 3, P = 2, Q = 3 
Output: 3
Explanation:
For N=4, K=3, P=2, Q=3,
ways are [2, 1, 2, 3], [2, 3, 1, 3], [2, 3, 2, 3]

Input:  N = 5, K = 3, P = 2, Q = 1 
Output: 5

Enfoque: La idea es utilizar Programación Dinámica para resolver este problema. 

• Tratemos de entender esto tomando un ejemplo, N = 4, K = 3, P = 2, Q = 1. 
  Observaremos todos los arreglos posibles comenzando desde P e intentaremos encontrar cualquier patrón que pueda ser útil para aplicar la programación Dinámica. 
   
• A continuación se muestra la imagen que muestra todos los arreglos posibles a partir de P = 2. 
   

• Sea A el arreglo que consiste en el número de Nodes que terminan en Q en un nivel particular 
  A = { 0, 1, 1, 3 }
  Sea B el arreglo que consiste en el número de Nodes que NO terminan en Q en un nivel particular 
  B = {1, 1, 3, 5}
• En una observación cuidadosa se puede notar que:
  1. A[i] = B[i-1] 
     Motivo: 
     todos los Nodes favorables (que terminan en Q) solo serán producidos por Nodes no favorables (que NO terminan en Q) del nivel anterior. 
      
  2. B[i] = A[i-1]*(K – 1) + B[i-1]*(K – 2) Motivo 
     : 
     • Para A[i-1]*(K – 1), algunos de los Nodes no favorables son producidos por Nodes favorables del nivel anterior, multiplique por (K – 1) ya que cada Node favorable producirá K-1 no favorable Nodes 
        
     • Para B[i-1]*(K – 2), el resto de los Nodes no favorables son producidos por Nodes no favorables del nivel anterior, multiplicado por (K-2), ya que un Node producido es favorable, entonces restar 2 de esto. 

// C++ program to calculate Number of
// ways to arrange N numbers under
// given constraints.
#include <bits/stdc++.h>
using namespace std;
 
class element {
public:
    // For favourable nodes
    // (ending at Q)
    int A;
     
    // For Non-favourable nodes
    // (NOT ending at Q)
    int B;
};
 
// Function to print Total number
// of ways
void NumberOfWays(int n, int k, int p,
                                int q)
{
    element* dp = new element[n];
 
    // If the First number and the
    // last number is same.
    if (p == q) {
        dp[0].A = 1;
        dp[0].B = 0;
    }
    else
    {
        dp[0].A = 0;
        dp[0].B = 1;
    }
 
    // DP approach to find current state
    // with the help of previous state.
    for (int i = 1; i < n; i++)
    {
        dp[i].A = dp[i - 1].B;
        dp[i].B = (dp[i - 1].A * (k - 1))
                 + (dp[i - 1].B * (k - 2));
    }
     
    cout << dp[n - 1].A << endl;
 
    return;
}
 
// Driver code
int main()
{
    
   int N = 5;
   int K = 3;
   int P = 2;
   int Q = 1;
     
   // Function call
   NumberOfWays(N, K, P, Q);
}
    

// Java program to calculate number of 
// ways to arrange N numbers under
// given constraints.
import java.io.*;
import java.util.*;
 
class GFG{
 
// Function to print Total number
// of ways
static void NumberOfWays(int n, int k,
                         int p, int q)
{
    int[][] dp = new int[n][2];
 
    // If the First number and the
    // last number is same.
    if (p == q)
    {
        dp[0][0] = 1;
        dp[0][1] = 0;
    }
    else
    {
        dp[0][0] = 0;
        dp[0][1] = 1;
    }
 
    // DP approach to find current state
    // with the help of previous state.
    for(int i = 1; i < n; i++)
    {
        dp[i][0] = dp[i - 1][1];
        dp[i][1] = (dp[i - 1][0] * (k - 1)) +
                   (dp[i - 1][1] * (k - 2));
    }
    System.out.println(dp[n - 1][0]);
}
 
// Driver Code
public static void main(String args[])
{
    int N = 5;
    int K = 3;
    int P = 2;
    int Q = 1;
         
    // Function call
    NumberOfWays(N, K, P, Q);
}
}
 
// This code is contributed by offbeat

// C# code to implement the approach
using System;
 
public class GFG {
 
  // Function to print Total number
  // of ways
  static void NumberOfWays(int n, int k,
                           int p, int q)
  {
    int[,] dp = new int[n, 2];
 
    // If the First number and the
    // last number is same.
    if (p == q)
    {
      dp[0, 0] = 1;
      dp[0, 1] = 0;
    }
    else
    {
      dp[0, 0] = 0;
      dp[0, 1] = 1;
    }
 
    // DP approach to find current state
    // with the help of previous state.
    for(int i = 1; i < n; i++)
    {
      dp[i, 0] = dp[i - 1, 1];
      dp[i, 1] = (dp[i - 1, 0] * (k - 1)) +
        (dp[i - 1, 1] * (k - 2));
    }
    Console.WriteLine(dp[n - 1, 0]);
  }
 
  // Driver code
  public static void Main(string []args)
  {
    int N = 5;
    int K = 3;
    int P = 2;
    int Q = 1;
 
    // Function call
    NumberOfWays(N, K, P, Q);
 
  }
}
 
// This code is contributed by sanjoy_62.

5

Complejidad temporal: O(N).