Count Derangements ( Permutation such that no element appears in its original position ) | A Dynamic programming based C ++ program to count derangements ; Function to count derangements ; Create an array to store counts for subproblems ; Base cases ; Fill der [ 0. . n ] in bottom up manner using above recursive formula ; Return result for n ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countDer ( int n ) { int der [ n + 1 ] = { 0 } ; der [ 1 ] = 0 ; der [ 2 ] = 1 ; for ( int i = 3 ; i <= n ; ++ i ) der [ i ] = ( i - 1 ) * ( der [ i - 1 ] + der [ i - 2 ] ) ; return der [ n ] ; } int main ( ) { int n = 4 ; cout << " Count ▁ of ▁ Derangements ▁ is ▁ " << countDer ( n ) ; return 0 ; }