排列球的方式，使相邻的球具有不同的类型-yiteyi-C++库

有p型的“p”球，q型的“q”球和r型的“r”球。使用这些球，我们想要创建一条直线，这样就不会有两个相同类型的球相邻。 例如：

null

Input  : p = 1, q = 1, r = 0Output : 2There are only two arrangements PQ and QPInput  : p = 1, q = 1, r = 1Output : 6There are only six arrangements PQR, QPR,QRP, RQP, PRQ and RPQInput  : p = 2, q = 1, r = 1Output : 6There are only six arrangements PQRP, QPRP,PRQP, RPQP, PRPQ and PQPR

我们强烈建议您在继续解决方案之前单击此处并进行练习。

天真的解决方案： 这个问题的简单解决方案是递归解决方案。我们反复呼吁三个案例 1）最后一个要放置的球是P型的 2）最后一个要放置的球是Q型的 3）最后一个要放置的球是R型的下面是上述想法的实现。

C++

                         // C++ program to count number of ways to arrange three                       
                         // types of balls such that no two balls of same color                       
                         // are adjacent to each other                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
           
                         // Returns count of arrangements where last placed ball is                       
                         // 'last'.  'last' is 0 for 'p', 1 for 'q' and 2 for 'r'                       
                         int                                     countWays(                                     int                                     p,                                     int                                     q,                                     int                                     r,                                     int                                     last)                       
                         {                       
                                                 // if number of balls of any color becomes less                       
                                                 // than 0 the number of ways arrangements is 0.                       
                                                 if                                     (p<0 || q<0 || r<0)                       
                                                 return                                     0;                       
           
                                                 // If last ball required is of type P and the number                       
                                                 // of balls of P type is 1 while number of balls of                       
                                                 // other color is 0 the number of ways is 1.                       
                                                 if                                     (p==1 && q==0 && r==0 && last==0)                       
                                                 return                                     1;                       
           
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p==0 && q==1 && r==0 && last==1)                       
                                                 return                                     1;                       
                                                 if                                     (p==0 && q==0 && r==1 && last==2)                       
                                                 return                                     1;                       
           
                                                 // if last ball required is P and the number of ways is                       
                                                 // the sum of number of ways to form sequence with 'p-1' P                       
                                                 // balls, q Q Balls and r R balls ending with Q and R.                       
                                                 if                                     (last==0)                       
                                                 return                                     countWays(p-1,q,r,1) + countWays(p-1,q,r,2);                       
           
                                                 // Same as above case for 'q' and 'r'                       
                                                 if                                     (last==1)                       
                                                 return                                     countWays(p,q-1,r,0) + countWays(p,q-1,r,2);                       
                                                 if                                     (last==2)                       
                                                 return                                     countWays(p,q,r-1,0) + countWays(p,q,r-1,1);                       
                         }                       
           
                         // Returns count of required arrangements                       
                         int                                     countUtil(                                     int                                     p,                                     int                                     q,                                     int                                     r)                       
                         {                       
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r, 0) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r, 1) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r, 2);                                     // Last required balls is type R                       
                         }                       
           
                         // Driver code to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     p = 1, q = 1, r = 1;                       
                                                 printf                                     (                                     "%d"                                     , countUtil(p, q, r));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number                       
                         // of ways to arrange three types of                       
                         // balls such that no two balls of                       
                         // same color are adjacent to each other                       
                         class                                     GFG {                       
                                   
                                                 // Returns count of arrangements                       
                                                 // where last placed ball is                       
                                                 // 'last'. 'last' is 0 for 'p',                       
                                                 // 1 for 'q' and 2 for 'r'                       
                                                 static                                     int                                     countWays(                                     int                                     p,                                     int                                     q,                                     int                                     r,                                     int                                     last)                       
                                                 {                       
                                                 // if number of balls of any                       
                                                 // color becomes less than 0                       
                                                 // the number of ways arrangements is 0.                       
                                                 if                                     (p <                                     0                                     || q <                                     0                                     || r <                                     0                                     )                       
                                                 return                                     0                                     ;                       
                                   
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (p ==                                     1                                     && q ==                                     0                                     && r ==                                     0                                     && last ==                                     0                                     )                       
                                                 return                                     1                                     ;                       
                                   
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p ==                                     0                                     && q ==                                     1                                     && r ==                                     0                                     && last ==                                     1                                     )                       
                                                 return                                     1                                     ;                       
                                                 if                                     (p ==                                     0                                     && q ==                                     0                                     && r ==                                     1                                     && last ==                                     2                                     )                       
                                                 return                                     1                                     ;                       
                                   
                                                 // if last ball required is P                       
                                                 // and the number of ways is                       
                                                 // the sum of number of ways                       
                                                 // to form sequence with 'p-1' P                       
                                                 // balls, q Q Balls and r R balls                       
                                                 // ending with Q and R.                       
                                                 if                                     (last ==                                     0                                     )                       
                                                 return                                     countWays(p -                                     1                                     , q, r,                                     1                                     ) +                       
                                                 countWays(p -                                     1                                     , q, r,                                     2                                     );                       
                                   
                                                 // Same as above case for 'q' and 'r'                       
                                                 if                                     (last ==                                     1                                     )                       
                                                 return                                     countWays(p, q -                                     1                                     , r,                                     0                                     ) +                       
                                                 countWays(p, q -                                     1                                     , r,                                     2                                     );                       
                                   
                                                 if                                     (last ==                                     2                                     )                       
                                                 return                                     countWays(p, q, r -                                     1                                     ,                                     0                                     ) +                       
                                                 countWays(p, q, r -                                     1                                     ,                                     1                                     );                       
                                   
                                                 return                                     0                                     ;                       
                                                 }                       
                                   
                                                 // Returns count of required arrangements                       
                                                 static                                     int                                     countUtil(                                     int                                     p,                                     int                                     q,                                     int                                     r) {                       
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r,                                     0                                     ) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r,                                     1                                     ) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r,                                     2                                     );                                     // Last required balls is type R                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     p =                                     1                                     , q =                                     1                                     , r =                                     1                                     ;                       
                                                 System.out.print(countUtil(p, q, r));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

Python3

                         # Python3 program to count                       
                         # number of ways to arrange                       
                         # three types of balls such                       
                         # that no two balls of same                       
                         # color are adjacent to each                       
                         # other                       
           
                         # Returns count of arrangements                       
                         # where last placed ball is                       
                         # 'last'. 'last' is 0 for 'p',                       
                         # 1 for 'q' and 2 for 'r'                       
                         def                                     countWays(p, q, r, last):                       
                                   
                                                 # if number of balls of                       
                                                 # any color becomes less                       
                                                 # than 0 the number of                       
                                                 # ways arrangements is 0.                       
                                                 if                                     (p <                                     0                                     or                                     q <                                     0                                     or                                     r <                                     0                                     ):                       
                                                 return                                     0                                     ;                       
           
                                                 # If last ball required is                       
                                                 # of type P and the number                       
                                                 # of balls of P type is 1                       
                                                 # while number of balls of                       
                                                 # other color is 0 the number                       
                                                 # of ways is 1.                       
                                                 if                                     (p                                     =                                     =                                     1                                     and                                     q                                     =                                     =                                     0                                     and                       
                                                 r                                     =                                     =                                     0                                     and                                     last                                     =                                     =                                     0                                     ):                       
                                                 return                                     1                                     ;                       
           
                                                 # Same case as above                       
                                                 # for 'q' and 'r'                       
                                                 if                                     (p                                     =                                     =                                     0                                     and                                     q                                     =                                     =                                     1                                     and                       
                                                 r                                     =                                     =                                     0                                     and                                     last                                     =                                     =                                     1                                     ):                       
                                                 return                                     1                                     ;                       
                                   
                                                 if                                     (p                                     =                                     =                                     0                                     and                                     q                                     =                                     =                                     0                                     and                       
                                                 r                                     =                                     =                                     1                                     and                                     last                                     =                                     =                                     2                                     ):                       
                                                 return                                     1                                     ;                       
           
                                                 # if last ball required is P                       
                                                 # and the number of ways is                       
                                                 # the sum of number of ways                       
                                                 # to form sequence with 'p-1' P                       
                                                 # balls, q Q Balls and r R                       
                                                 # balls ending with Q and R.                       
                                                 if                                     (last                                     =                                     =                                     0                                     ):                       
                                                 return                                     (countWays(p                                     -                                     1                                     , q, r,                                     1                                     )                                     +                       
                                                 countWays(p                                     -                                     1                                     , q, r,                                     2                                     ));                       
           
                                                 # Same as above case                       
                                                 # for 'q' and 'r'                       
                                                 if                                     (last                                     =                                     =                                     1                                     ):                       
                                                 return                                     (countWays(p, q                                     -                                     1                                     , r,                                     0                                     )                                     +                       
                                                 countWays(p, q                                     -                                     1                                     , r,                                     2                                     ));                       
                                                 if                                     (last                                     =                                     =                                     2                                     ):                       
                                                 return                                     (countWays(p, q, r                                     -                                     1                                     ,                                     0                                     )                                     +                       
                                                 countWays(p, q, r                                     -                                     1                                     ,                                     1                                     ));                       
           
                         # Returns count of                       
                         # required arrangements                       
                         def                                     countUtil(p, q, r):                       
                                   
                                                 # Three cases arise:                       
                                                 # Last required balls is type P                       
                                                 # Last required balls is type Q                       
                                                 # Last required balls is type R                       
                                                 return                                     (countWays(p, q, r,                                     0                                     )                                     +                       
                                                 countWays(p, q, r,                                     1                                     )                                     +                       
                                                 countWays(p, q, r,                                     2                                     ));                       
           
                         # Driver Code                       
                         p                                     =                                     1                                     ;                       
                         q                                     =                                     1                                     ;                       
                         r                                     =                                     1                                     ;                       
                         print                                     (countUtil(p, q, r));                       
                                   
                         # This code is contributed by mits                       

C#

                         // C# program to count number                       
                         // of ways to arrange three types of                       
                         // balls such that no two balls of                       
                         // same color are adjacent to each other                       
                         using                                     System;                       
           
                         class                                     GFG {                       
                                   
                                                 // Returns count of arrangements                       
                                                 // where last placed ball is                       
                                                 // 'last'. 'last' is 0 for 'p',                       
                                                 // 1 for 'q' and 2 for 'r'                       
                                                 static                                     int                                     countWays(                                     int                                     p,                                     int                                     q,                       
                                                 int                                     r,                                     int                                     last)                       
                                                 {                       
                                   
                                                 // if number of balls of any                       
                                                 // color becomes less than 0                       
                                                 // the number of ways                       
                                                 // arrangements is 0.                       
                                                 if                                     (p < 0 || q < 0 || r < 0)                       
                                                 return                                     0;                       
                                   
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (p == 1 && q == 0 && r == 0                       
                                                 && last == 0)                       
                                                 return                                     1;                       
                                   
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p == 0 && q == 1 && r == 0                       
                                                 && last == 1)                       
                                                 return                                     1;                       
                                                 if                                     (p == 0 && q == 0 && r == 1                       
                                                 && last == 2)                       
                                                 return                                     1;                       
                                   
                                                 // if last ball required is P                       
                                                 // and the number of ways is                       
                                                 // the sum of number of ways                       
                                                 // to form sequence with 'p-1' P                       
                                                 // balls, q Q Balls and r R balls                       
                                                 // ending with Q and R.                       
                                                 if                                     (last == 0)                       
                                                 return                                     countWays(p - 1, q, r, 1) +                       
                                                 countWays(p - 1, q, r, 2);                       
                                   
                                                 // Same as above case for 'q' and 'r'                       
                                                 if                                     (last == 1)                       
                                                 return                                     countWays(p, q - 1, r, 0) +                       
                                                 countWays(p, q - 1, r, 2);                       
                                   
                                                 if                                     (last == 2)                       
                                                 return                                     countWays(p, q, r - 1, 0) +                       
                                                 countWays(p, q, r - 1, 1);                       
                                   
                                                 return                                     0;                       
                                                 }                       
                                   
                                                 // Returns count of required arrangements                       
                                                 static                                     int                                     countUtil(                                     int                                     p,                                     int                                     q,                                     int                                     r)                       
                                                 {                       
                                   
                                                 // Three cases arise:                       
                                                 // 1. Last required balls is type P                       
                                                 // 2. Last required balls is type Q                       
                                                 // 3. Last required balls is type R                       
                                                 return                                     countWays(p, q, r, 0) +                       
                                                 countWays(p, q, r, 1) +                       
                                                 countWays(p, q, r, 2);                       
                                                 }                       
                                   
                                                 // Driver code                       
                                                 public                                     static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     p = 1, q = 1, r = 1;                       
                                   
                                                 Console.Write(countUtil(p, q, r));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by nitin mittal.                       

PHP

                         <?php                       
                         // PHP program to count number                       
                         // of ways to arrange three                       
                         // types of balls such that                       
                         // no two balls of same color                       
                         // are adjacent to each other                       
           
                         // Returns count of arrangements                       
                         // where last placed ball is                       
                         // 'last'. 'last' is 0 for 'p',                       
                         // 1 for 'q' and 2 for 'r'                       
                         function                                     countWays(                                     $p                                     ,                                     $q                                     ,                       
                                                 $r                                     ,                                     $last                                     )                       
                         {                       
                                   
                                                 // if number of balls of                       
                                                 // any color becomes less                       
                                                 // than 0 the number of                       
                                                 // ways arrangements is 0.                       
                                                 if                                     (                                     $p                                     < 0 ||                                     $q                       
                                                 < 0 ||                                     $r                                     < 0)                       
                                                 return                                     0;                       
           
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (                                     $p                                     == 1 &&                                     $q                                     == 0 &&                       
                                                 $r                                     == 0 &&                                     $last                                     == 0)                       
                                                 return                                     1;                       
           
                                                 // Same case as above                       
                                                 // for 'q' and 'r'                       
                                                 if                                     (                                     $p                                     == 0 &&                                     $q                                     == 1 &&                       
                                                 $r                                     == 0 &&                                     $last                                     == 1)                       
                                                 return                                     1;                       
                                   
                                                 if                                     (                                     $p                                     == 0 &&                                     $q                                     == 0 &&                       
                                                 $r                                     == 1 &&                                     $last                                     == 2)                       
                                                 return                                     1;                       
           
                                                 // if last ball required is P                       
                                                 // and the number of ways is                       
                                                 // the sum of number of ways                       
                                                 // to form sequence with 'p-1' P                       
                                                 // balls, q Q Balls and r R                       
                                                 // balls ending with Q and R.                       
                                                 if                                     (                                     $last                                     == 0)                       
                                                 return                                     countWays(                                     $p                                     - 1,                                     $q                                     ,                                     $r                                     , 1) +                       
                                                 countWays(                                     $p                                     - 1,                                     $q                                     ,                                     $r                                     , 2);                       
           
                                                 // Same as above case                       
                                                 // for 'q' and 'r'                       
                                                 if                                     (                                     $last                                     == 1)                       
                                                 return                                     countWays(                                     $p                                     ,                                     $q                                     - 1,                                     $r                                     , 0) +                       
                                                 countWays(                                     $p                                     ,                                     $q                                     - 1,                                     $r                                     , 2);                       
                                                 if                                     (                                     $last                                     == 2)                       
                                                 return                                     countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     - 1, 0) +                       
                                                 countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     - 1, 1);                       
                         }                       
           
                         // Returns count of                       
                         // required arrangements                       
                         function                                     countUtil(                                     $p                                     ,                                     $q                                     ,                                     $r                                     )                       
                         {                       
                                   
                                                 // Three cases arise:                       
                                                 // Last required balls is type P                       
                                                 // Last required balls is type Q                       
                                                 // Last required balls is type R                       
                                                 return                                     countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     , 0) +                       
                                                 countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     , 1) +                       
                                                 countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     , 2);                       
                         }                       
           
                                                 // Driver Code                       
                                                 $p                                     = 1;                       
                                                 $q                                     = 1;                       
                                                 $r                                     = 1;                       
                                                 echo                                     (countUtil(                                     $p                                     ,                                     $q                                     ,                                     $r                                     ));                       
                                   
                         // This code is contributed by nitin mittal.                       
                         ?>                       

Javascript

                         <script>                       
           
                         // JavaScript program to count number                       
                         // of ways to arrange three                       
                         // types of balls such that no                       
                         // two balls of same color                       
                         // are adjacent to each other                       
                                   
                                                 // Returns count of arrangements                       
                                                 // where last placed ball is                       
                                                 // 'last'. 'last' is 0 for 'p',                       
                                                 // 1 for 'q' and 2 for 'r'                       
                                                 function                                     countWays(p, q, r, last)                       
                                                 {                       
                                   
                                                 // if number of balls of any                       
                                                 // color becomes less than 0                       
                                                 // the number of ways arrangements is 0.                       
                                                 if                                     (p < 0 || q < 0 || r < 0)                       
                                                 return                                     0;                       
                                   
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (p == 1 && q == 0 && r == 0 && last == 0)                       
                                                 return                                     1;                       
                                   
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p == 0 && q == 1 && r == 0 && last == 1)                       
                                                 return                                     1;                       
                                                 if                                     (p == 0 && q == 0 && r == 1 && last == 2)                       
                                                 return                                     1;                       
                                   
                                                 // if last ball required is P                       
                                                 // and the number of ways is                       
                                                 // the sum of number of ways                       
                                                 // to form sequence with 'p-1' P                       
                                                 // balls, q Q Balls and r R balls                       
                                                 // ending with Q and R.                       
                                                 if                                     (last == 0)                       
                                                 return                                     countWays(p - 1, q, r, 1) +                       
                                                 countWays(p - 1, q, r, 2);                       
                                   
                                                 // Same as above case for 'q' and 'r'                       
                                                 if                                     (last == 1)                       
                                                 return                                     countWays(p, q - 1, r, 0) +                       
                                                 countWays(p, q - 1, r, 2);                       
                                   
                                                 if                                     (last == 2)                       
                                                 return                                     countWays(p, q, r - 1, 0) +                       
                                                 countWays(p, q, r - 1, 1);                       
                                   
                                                 return                                     0;                       
                                                 }                       
                                   
                                                 // Returns count of required arrangements                       
                                                 function                                     countUtil(p, q, r)                       
                                                 {                       
                                   
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r, 0) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r, 1) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r, 2);                                     // Last required balls is type R                       
                                                 }                       
           
                         // Driver Code                       
           
                                                 let p = 1, q = 1, r = 1;                       
                                                 document.write(countUtil(p, q, r));                       
                                   
                                                 // This code is contributed by target_2.                       
                         </script>                       

输出：

这个解的时间复杂度是指数的。我们可以观察到，有许多子问题一次又一次地被解决，所以这个问题可以用动态规划（DP）来解决。我们可以很容易地用备忘录来解决这个问题。

C++

                         // C++ program to count number of ways to arrange three                       
                         // types of balls such that no two balls of same color                       
                         // are adjacent to each other                       
                         #include<bits/stdc++.h>                       
                         using                                     namespace                                     std;                       
                         #define MAX 100                       
           
                         // table to store to store results of subproblems                       
                         int                                     dp[MAX][MAX][MAX][3];                       
           
                         // Returns count of arrangements where last placed ball is                       
                         // 'last'.  'last' is 0 for 'p', 1 for 'q' and 2 for 'r'                       
                         int                                     countWays(                                     int                                     p,                                     int                                     q,                                     int                                     r,                                     int                                     last)                       
                         {                       
                                                 // if number of balls of any color becomes less                       
                                                 // than 0 the number of ways arrangements is 0.                       
                                                 if                                     (p<0 || q<0 || r<0)                       
                                                 return                                     0;                       
           
                                                 // If last ball required is of type P and the number                       
                                                 // of balls of P type is 1 while number of balls of                       
                                                 // other color is 0 the number of ways is 1.                       
                                                 if                                     (p==1 && q==0 && r==0 && last==0)                       
                                                 return                                     1;                       
           
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p==0 && q==1 && r==0 && last==1)                       
                                                 return                                     1;                       
                                                 if                                     (p==0 && q==0 && r==1 && last==2)                       
                                                 return                                     1;                       
           
                                                 // If this subproblem is already evaluated                       
                                                 if                                     (dp[p][q][r][last] != -1)                       
                                                 return                                     dp[p][q][r][last];                       
           
                                                 // if last ball required is P and the number of ways is                       
                                                 // the sum of number of ways to form sequence with 'p-1' P                       
                                                 // balls, q Q Balls and r R balls ending with Q and R.                       
                                                 if                                     (last==0)                       
                                                 dp[p][q][r][last] = countWays(p-1,q,r,1) + countWays(p-1,q,r,2);                       
           
                                                 // Same as above case for 'q' and 'r'                       
                                                 else                                     if                                     (last==1)                       
                                                 dp[p][q][r][last] = countWays(p,q-1,r,0) + countWays(p,q-1,r,2);                       
                                                 else                                     //(last==2)                       
                                                 dp[p][q][r][last] =  countWays(p,q,r-1,0) + countWays(p,q,r-1,1);                       
           
                                                 return                                     dp[p][q][r][last];                       
                         }                       
           
                         // Returns count of required arrangements                       
                         int                                     countUtil(                                     int                                     p,                                     int                                     q,                                     int                                     r)                       
                         {                       
                                                 // Initialize 'dp' array                       
                                                 memset                                     (dp, -1,                                     sizeof                                     (dp));                       
           
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r, 0) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r, 1) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r, 2);                                     // Last required balls is type R                       
                         }                       
           
                         // Driver code to test above                       
                         int                                     main()                       
                         {                       
                                                 int                                     p = 1, q = 1, r = 1;                       
                                                 printf                                     (                                     "%d"                                     , countUtil(p, q, r));                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java program to count number                       
                         // of ways to arrange three                       
                         // types of balls such that no                       
                         // two balls of same color                       
                         // are adjacent to each other                       
                         import                                     java.util.Arrays;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 static                                     final                                     int                                     MAX =                                     100                                     ;                       
                                   
                                                 // table to store to store results of subproblems                       
                                                 static                                     int                                     dp[][][][] =                                     new                                     int                                     [MAX][MAX][MAX][                                     3                                     ];                       
                                   
                                                 // Returns count of arrangements                       
                                                 // where last placed ball is                       
                                                 // 'last'. 'last' is 0 for 'p',                       
                                                 // 1 for 'q' and 2 for 'r'                       
                                                 static                                     int                                     countWays(                                     int                                     p,                                     int                                     q,                                     int                                     r,                                     int                                     last)                       
                                                 {                       
                                                 // if number of balls of any                       
                                                 // color becomes less than 0                       
                                                 // the number of ways arrangements is 0.                       
                                                 if                                     (p <                                     0                                     || q <                                     0                                     || r <                                     0                                     )                       
                                                 return                                     0                                     ;                       
                                   
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (p ==                                     1                                     && q ==                                     0                                     && r ==                                     0                                     && last ==                                     0                                     )                       
                                                 return                                     1                                     ;                       
                                   
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p ==                                     0                                     && q ==                                     1                                     && r ==                                     0                                     && last ==                                     1                                     )                       
                                                 return                                     1                                     ;                       
                                   
                                                 if                                     (p ==                                     0                                     && q ==                                     0                                     && r ==                                     1                                     && last ==                                     2                                     )                       
                                                 return                                     1                                     ;                       
                                   
                                                 // If this subproblem is already evaluated                       
                                                 if                                     (dp[p][q][r][last] != -                                     1                                     )                       
                                                 return                                     dp[p][q][r][last];                       
                                   
                                                 // if last ball required is P and                       
                                                 // the number of ways is the sum                       
                                                 // of number of ways to form sequence                       
                                                 // with 'p-1' P balls, q Q balss and                       
                                                 // r R balls ending with Q and R.                       
                                                 if                                     (last ==                                     0                                     )                       
                                                 dp[p][q][r][last] = countWays(p -                                     1                                     , q, r,                                     1                                     ) +                       
                                                 countWays(p -                                     1                                     , q, r,                                     2                                     );                       
                                   
                                                 // Same as above case for 'q' and 'r'                       
                                                 else                                     if                                     (last ==                                     1                                     )                       
                                                 dp[p][q][r][last] = countWays(p, q -                                     1                                     , r,                                     0                                     ) +                       
                                                 countWays(p, q -                                     1                                     , r,                                     2                                     );                       
                                                 //(last==2)                       
                                                 else                       
                                                 dp[p][q][r][last] = countWays(p, q, r -                                     1                                     ,                                     0                                     ) +                       
                                                 countWays(p, q, r -                                     1                                     ,                                     1                                     );                       
                                   
                                                 return                                     dp[p][q][r][last];                       
                                                 }                       
                                   
                                                 // Returns count of required arrangements                       
                                                 static                                     int                                     countUtil(                                     int                                     p,                                     int                                     q,                                     int                                     r)                       
                                                 {                       
                                                 // Initialize 'dp' array                       
                                                 for                                     (                                     int                                     [][][] row : dp)                       
                                                 {                       
                                                 for                                     (                                     int                                     [][] innerRow : row)                       
                                                 {                       
                                                 for                                     (                                     int                                     [] innerInnerRow : innerRow)                       
                                                 {                       
                                                 Arrays.fill(innerInnerRow, -                                     1                                     );                       
                                                 }                       
                                                 }                       
                                                 };                       
                                   
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r,                                     0                                     ) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r,                                     1                                     ) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r,                                     2                                     );                                     // Last required balls is type R                       
                                                 }                       
           
                                                 // Driver code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     p =                                     1                                     , q =                                     1                                     , r =                                     1                                     ;                       
                                                 System.out.print(countUtil(p, q, r));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by Anant Agarwal.                       

C#

                         // C# program to count number                       
                         // of ways to arrange three                       
                         // types of balls such that no                       
                         // two balls of same color                       
                         // are adjacent to each other                       
                         using                                     System;                       
           
                         class                                     GFG                       
                         {                       
           
                                                 static                                     int                                     MAX = 101;                       
                                   
                                                 // table to store to store results of subproblems                       
                                                 static                                     int                                     [,,,] dp =                                     new                                     int                                     [MAX, MAX, MAX, 4];                       
                                   
                                                 // Returns count of arrangements                       
                                                 // where last placed ball is                       
                                                 // 'last'. 'last' is 0 for 'p',                       
                                                 // 1 for 'q' and 2 for 'r'                       
                                                 static                                     int                                     countWays(                                     int                                     p,                                     int                                     q,                                     int                                     r,                                     int                                     last)                       
                                                 {                       
                                                 // if number of balls of any                       
                                                 // color becomes less than 0                       
                                                 // the number of ways arrangements is 0.                       
                                                 if                                     (p < 0 || q < 0 || r < 0)                       
                                                 return                                     0;                       
                                   
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (p == 1 && q == 0 && r == 0 && last == 0)                       
                                                 return                                     1;                       
                                   
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p == 0 && q == 1 && r == 0 && last == 1)                       
                                                 return                                     1;                       
                                   
                                                 if                                     (p == 0 && q == 0 && r == 1 && last == 2)                       
                                                 return                                     1;                       
                                   
                                                 // If this subproblem is already evaluated                       
                                                 if                                     (dp[p, q, r, last] != -1)                       
                                                 return                                     dp[p, q, r, last];                       
                                   
                                                 // if last ball required is P and                       
                                                 // the number of ways is the sum                       
                                                 // of number of ways to form sequence                       
                                                 // with 'p-1' P balls, q Q balss and                       
                                                 // r R balls ending with Q and R.                       
                                                 if                                     (last == 0)                       
                                                 dp[p, q, r, last] = countWays(p - 1, q, r, 1) +                       
                                                 countWays(p - 1, q, r, 2);                       
                                   
                                                 // Same as above case for 'q' and 'r'                       
                                                 else                                     if                                     (last == 1)                       
                                                 dp[p, q, r, last] = countWays(p, q - 1, r, 0) +                       
                                                 countWays(p, q - 1, r, 2);                       
                                                 //(last==2)                       
                                                 else                       
                                                 dp[p, q, r, last] = countWays(p, q, r - 1, 0) +                       
                                                 countWays(p, q, r - 1, 1);                       
                                   
                                                 return                                     dp[p, q, r, last];                       
                                                 }                       
                                   
                                                 // Returns count of required arrangements                       
                                                 static                                     int                                     countUtil(                                     int                                     p,                                     int                                     q,                                     int                                     r)                       
                                                 {                       
                                                 // Initialize 'dp' array                       
                                                 for                                     (                                     int                                     i = 0; i < MAX; i++)                       
                                                 for                                     (                                     int                                     j = 0; j < MAX; j++)                       
                                                 for                                     (                                     int                                     k = 0; k < MAX; k++)                       
                                                 for                                     (                                     int                                     l = 0; l < 4; l++)                       
                                                 dp[i, j, k, l] = -1;                       
                                   
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r, 0) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r, 1) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r, 2);                                     // Last required balls is type R                       
                                                 }                       
           
                                                 // Driver code                       
                                                 static                                     void                                     Main()                       
                                                 {                       
                                                 int                                     p = 1, q = 1, r = 1;                       
                                                 Console.WriteLine(countUtil(p, q, r));                       
                                                 }                       
                         }                       
           
                         // This code is contributed by mits.                       

Python3

                         # Python3 program to count number of ways to                       
                         # arrange three types of balls such that no                       
                         # two balls of same color are adjacent to each other                       
                         MAX                                     =                                     100                                     ;                       
           
                         # table to store to store results of subproblems                       
                         dp                                     =                                     [[[[                                     -                                     1                                     ]                                     *                                     4                                     for                                     i                                     in                                     range                                     (                                     MAX                                     )]                       
                                                 for                                     j                                     in                                     range                                     (                                     MAX                                     )]                       
                                                 for                                     k                                     in                                     range                                     (                                     MAX                                     )];                       
           
                         # Returns count of arrangements where last                       
                         # placed ball is 'last'. 'last' is 0 for 'p',                       
                         # 1 for 'q' and 2 for 'r'                       
                         def                                     countWays(p, q, r, last):                       
           
                                                 # if number of balls of any color becomes less                       
                                                 # than 0 the number of ways arrangements is 0.                       
                                                 if                                     (p <                                     0                                     or                                     q <                                     0                                     or                                     r <                                     0                                     ):                       
                                                 return                                     0                                     ;                       
           
                                                 # If last ball required is of type P and the                       
                                                 # number of balls of P type is 1 while number                       
                                                 # of balls of other color is 0 the number of                       
                                                 # ways is 1.                       
                                                 if                                     (p                                     =                                     =                                     1                                     and                                     q                                     =                                     =                                     0                                     and                       
                                                 r                                     =                                     =                                     0                                     and                                     last                                     =                                     =                                     0                                     ):                       
                                                 return                                     1                                     ;                       
           
                                                 # Same case as above for 'q' and 'r'                       
                                                 if                                     (p                                     =                                     =                                     0                                     and                                     q                                     =                                     =                                     1                                     and                       
                                                 r                                     =                                     =                                     0                                     and                                     last                                     =                                     =                                     1                                     ):                       
                                                 return                                     1                                     ;                       
                                                 if                                     (p                                     =                                     =                                     0                                     and                                     q                                     =                                     =                                     0                                     and                       
                                                 r                                     =                                     =                                     1                                     and                                     last                                     =                                     =                                     2                                     ):                       
                                                 return                                     1                                     ;                       
           
                                                 # If this subproblem is already evaluated                       
                                                 if                                     (dp[p][q][r][last] !                                     =                                     -                                     1                                     ):                       
                                                 return                                     dp[p][q][r][last];                       
           
                                                 # if last ball required is P and the number                       
                                                 # of ways is the sum of number of ways to                       
                                                 # form sequence with 'p-1' P balls, q Q Balls                       
                                                 # and r R balls ending with Q and R.                       
                                                 if                                     (last                                     =                                     =                                     0                                     ):                       
                                                 dp[p][q][r][last]                                     =                                     (countWays(p                                     -                                     1                                     , q, r,                                     1                                     )                                     +                       
                                                 countWays(p                                     -                                     1                                     , q, r,                                     2                                     ));                       
           
                                                 # Same as above case for 'q' and 'r'                       
                                                 elif                                     (last                                     =                                     =                                     1                                     ):                       
                                                 dp[p][q][r][last]                                     =                                     (countWays(p, q                                     -                                     1                                     , r,                                     0                                     )                                     +                       
                                                 countWays(p, q                                     -                                     1                                     , r,                                     2                                     ));                       
                                                 else                                     :                       
                                   
                                                 #(last==2)                       
                                                 dp[p][q][r][last]                                     =                                     (countWays(p, q, r                                     -                                     1                                     ,                                     0                                     )                                     +                       
                                                 countWays(p, q, r                                     -                                     1                                     ,                                     1                                     ));                       
           
                                                 return                                     dp[p][q][r][last];                       
           
                         # Returns count of required arrangements                       
                         def                                     countUtil(p, q, r):                       
                                   
                                                 # Three cases arise:                       
                                                 # Last required balls is type P                       
                                                 # Last required balls is type Q                       
                                                 # Last required balls is type R                       
                                                 return                                     (countWays(p, q, r,                                     0                                     )                                     +                       
                                                 countWays(p, q, r,                                     1                                     )                                     +                       
                                                 countWays(p, q, r,                                     2                                     ));                       
           
                         # Driver Code                       
                         p, q, r                                     =                                     1                                     ,                                     1                                     ,                                     1                                     ;                       
                         print                                     (countUtil(p, q, r));                       
           
                         # This code is contributed by mits                       

PHP

                         <?php                       
                         // PHP program to count number of ways to                       
                         // arrange three types of balls such that                       
                         // no two balls of same color are adjacent                       
                         // to each other                       
                         $MAX                                     = 100;                       
           
                         // table to store to store results of subproblems                       
                         $dp                                     =                                     array_fill                                     (0,                                     $MAX                                     ,                                     array_fill                                     (0,                                     $MAX                                     ,                       
                                                 array_fill                                     (0,                                     $MAX                                     ,                                     array_fill                                     (0, 3, -1))));                       
           
                         // Returns count of arrangements where last                       
                         // placed ball is 'last'. 'last' is 0 for 'p',                       
                         // 1 for 'q' and 2 for 'r'                       
                         function                                     countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     ,                                     $last                                     )                       
                         {                       
                                                 global                                     $dp                                     ;                       
                                   
                                                 // if number of balls of any color becomes less                       
                                                 // than 0 the number of ways arrangements is 0.                       
                                                 if                                     (                                     $p                                     < 0 ||                                     $q                                     < 0 ||                                     $r                                     < 0)                       
                                                 return                                     0;                       
           
                                                 // If last ball required is of type P and the                       
                                                 // number of balls of P type is 1 while number                       
                                                 // of balls of other color is 0 the number of                       
                                                 // ways is 1.                       
                                                 if                                     (                                     $p                                     == 1 &&                                     $q                                     == 0 &&                                     $r                                     == 0 &&                                     $last                                     == 0)                       
                                                 return                                     1;                       
           
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (                                     $p                                     == 0 &&                                     $q                                     == 1 &&                                     $r                                     == 0 &&                                     $last                                     == 1)                       
                                                 return                                     1;                       
                                                 if                                     (                                     $p                                     == 0 &&                                     $q                                     == 0 &&                                     $r                                     == 1 &&                                     $last                                     == 2)                       
                                                 return                                     1;                       
           
                                                 // If this subproblem is already evaluated                       
                                                 if                                     (                                     $dp                                     [                                     $p                                     ][                                     $q                                     ][                                     $r                                     ][                                     $last                                     ] != -1)                       
                                                 return                                     $dp                                     [                                     $p                                     ][                                     $q                                     ][                                     $r                                     ][                                     $last                                     ];                       
           
                                                 // if last ball required is P and the number of                       
                                                 // ways is the sum of number of ways to form                       
                                                 // sequence with 'p-1' P balls, q Q Balls and r                       
                                                 // R balls ending with Q and R.                       
                                                 if                                     (                                     $last                                     == 0)                       
                                                 $dp                                     [                                     $p                                     ][                                     $q                                     ][                                     $r                                     ][                                     $last                                     ] = countWays(                                     $p                                     - 1,                                     $q                                     ,                                     $r                                     , 1) +                       
                                                 countWays(                                     $p                                     - 1,                                     $q                                     ,                                     $r                                     , 2);                       
           
                                                 // Same as above case for 'q' and 'r'                       
                                                 else                                     if                                     (                                     $last                                     == 1)                       
                                                 $dp                                     [                                     $p                                     ][                                     $q                                     ][                                     $r                                     ][                                     $last                                     ] = countWays(                                     $p                                     ,                                     $q                                     - 1,                                     $r                                     , 0) +                       
                                                 countWays(                                     $p                                     ,                                     $q                                     - 1,                                     $r                                     , 2);                       
                                                 else                                     //(last==2)                       
                                                 $dp                                     [                                     $p                                     ][                                     $q                                     ][                                     $r                                     ][                                     $last                                     ] = countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     - 1, 0) +                       
                                                 countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     - 1, 1);                       
           
                                                 return                                     $dp                                     [                                     $p                                     ][                                     $q                                     ][                                     $r                                     ][                                     $last                                     ];                       
                         }                       
           
                         // Returns count of required arrangements                       
                         function                                     countUtil(                                     $p                                     ,                                     $q                                     ,                                     $r                                     )                       
                         {                       
           
                         // Three cases arise:                       
                         return                                     countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     , 0) +                                     // Last required balls is type P                       
                                                 countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     , 1) +                                     // Last required balls is type Q                       
                                                 countWays(                                     $p                                     ,                                     $q                                     ,                                     $r                                     , 2);                                     // Last required balls is type R                       
                         }                       
           
                         // Driver code                       
                         $p                                     = 1;                       
                         $q                                     = 1;                       
                         $r                                     = 1;                       
                         print                                     (countUtil(                                     $p                                     ,                                     $q                                     ,                                     $r                                     ));                       
           
                         // This code is contributed by mits                       
                         ?>                       

Javascript

                         <script>                       
           
                         // javascript program to count number                       
                         // of ways to arrange three                       
                         // types of balls such that no                       
                         // two balls of same color                       
                         // are adjacent to each other                       
           
           
                         var                                     MAX = 100;                       
           
                         // table to store to store results of subproblems                       
                         var                                     dp = Array(MAX).fill(-1).map(x =>                       
                         Array(MAX).fill(-1).map(x =>                       
                         Array(MAX).fill(-1).map(x => Array(3).fill(-1))));                       
           
                         // Returns count of arrangements                       
                         // where last placed ball is                       
                         // 'last'. 'last' is 0 for 'p',                       
                         // 1 for 'q' and 2 for 'r'                       
                         function                                     countWays( p , q , r , last)                       
                         {                       
                                                 // if number of balls of any                       
                                                 // color becomes less than 0                       
                                                 // the number of ways arrangements is 0.                       
                                                 if                                     (p < 0 || q < 0 || r < 0)                       
                                                 return                                     0;                       
           
                                                 // If last ball required is                       
                                                 // of type P and the number                       
                                                 // of balls of P type is 1                       
                                                 // while number of balls of                       
                                                 // other color is 0 the number                       
                                                 // of ways is 1.                       
                                                 if                                     (p == 1 && q == 0 && r == 0 && last == 0)                       
                                                 return                                     1;                       
           
                                                 // Same case as above for 'q' and 'r'                       
                                                 if                                     (p == 0 && q == 1 && r == 0 && last == 1)                       
                                                 return                                     1;                       
                                   
                                                 if                                     (p == 0 && q == 0 && r == 1 && last == 2)                       
                                                 return                                     1;                       
           
                                                 // If this subproblem is already evaluated                       
                                                 if                                     (dp[p][q][r][last] != -1)                       
                                                 return                                     dp[p][q][r][last];                       
           
                                                 // if last ball required is P and                       
                                                 // the number of ways is the sum                       
                                                 // of number of ways to form sequence                       
                                                 // with 'p-1' P balls, q Q balss and                       
                                                 // r R balls ending with Q and R.                       
                                                 if                                     (last == 0)                       
                                                 dp[p][q][r][last] = countWays(p - 1, q, r, 1) +                       
                                                 countWays(p - 1, q, r, 2);                       
           
                                                 // Same as above case for 'q' and 'r'                       
                                                 else                                     if                                     (last == 1)                       
                                                 dp[p][q][r][last] = countWays(p, q - 1, r, 0) +                       
                                                 countWays(p, q - 1, r, 2);                       
                                                 //(last==2)                       
                                                 else                       
                                                 dp[p][q][r][last] = countWays(p, q, r - 1, 0) +                       
                                                 countWays(p, q, r - 1, 1);                       
           
                                                 return                                     dp[p][q][r][last];                       
                         }                       
           
                         // Returns count of required arrangements                       
                         function                                     countUtil(p , q , r)                       
                         {                       
           
                                                 // Three cases arise:                       
                                                 return                                     countWays(p, q, r, 0) +                                     // Last required balls is type P                       
                                                 countWays(p, q, r, 1) +                                     // Last required balls is type Q                       
                                                 countWays(p, q, r, 2);                                     // Last required balls is type R                       
                         }                       
           
                         // Driver code                       
                         var                                     p = 1, q = 1, r = 1;                       
                         document.write(countUtil(p, q, r));                       
           
                         // This code contributed by Princi Singh                       
                         </script>                       

输出：

时间复杂性： O（p*q*r） 辅助空间： O（p*q*r*3）本文由 巴武克·查拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章