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