给定一个有n根柱子和k种颜色的围栏，找出油漆围栏的方法，使最多两个相邻的柱子具有相同的颜色。因为答案可以是大的，所以返回10^9+7的模。 例如：
null
Input : n = 2 k = 4Output : 16We have 4 colors and 2 posts.Ways when both posts have same color : 4 Ways when both posts have diff color :4(choices for 1st post) * 3(choices for 2nd post) = 12Input : n = 3 k = 2Output : 6
下图描述了用2种颜色绘制3篇文章的6种可能方式：
![图片[1]-绘制栅栏算法-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_painting-fence-1.png)
考虑下面的图像，其中C、C’和C’是帖子I、I-1和I—2的各自颜色。
![图片[2]-绘制栅栏算法-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/geeks_painting-fence-2.png)
根据问题的约束条件，c=c’=c“不可能同时发生，所以c’！=c或c”！=c或两者兼而有之。c’！=c和k–1代表c”！=C
diff = no of ways when color of last two posts is different same = no of ways when color of last two posts is same total ways = diff + sumfor n = 1 diff = k, same = 0 total = kfor n = 2 diff = k * (k-1) //k choices for first post, k-1 for next same = k //k choices for common color of two posts total = k + k * (k-1)for n = 3 diff = k * (k-1)* (k-1) //(k-1) choices for the first place // k choices for the second place //(k-1) choices for the third place same = k * (k-1) * 2 // 2 is multiplied because consider two color R and B // R R B or B R R // B B R or R B B c'' != c, (k-1) choices for itHence we deduce that,total[i] = same[i] + diff[i]same[i] = diff[i-1]diff[i] = (diff[i-1] + diff[i-2]) * (k-1) = total[i-1] * (k-1)
以下是问题的实施情况：
C++
// C++ program for Painting Fence Algorithm // optimised version #include <bits/stdc++.h> using namespace std; // Returns count of ways to color k posts long countWays( int n, int k) { long dp[n + 1]; memset (dp, 0, sizeof (dp)); long long mod = 1000000007; dp[1] = k; dp[2] = k * k; for ( int i = 3; i <= n; i++) { dp[i] = ((k - 1) * (dp[i - 1] + dp[i - 2])) % mod; } return dp[n]; } // Driver code int main() { int n = 3, k = 2; cout << countWays(n, k) << endl; return 0; } |
JAVA
// Java program for Painting Fence Algorithm import java.util.*; class GfG { // Returns count of ways to color k posts // using k colors static long countWays( int n, int k) { // To store results for subproblems long dp[] = new long [n + 1 ]; Arrays.fill(dp, 0 ); int mod = 1000000007 ; // There are k ways to color first post dp[ 1 ] = k; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) int same = 0 , diff = k; // Fill for 2 posts onwards for ( int i = 2 ; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = ( int )(dp[i - 1 ] * (k - 1 )); diff = diff % mod; // Total choices till i. dp[i] = (same + diff) % mod; } return dp[n]; } // Driver code public static void main(String[] args) { int n = 3 , k = 2 ; System.out.println(countWays(n, k)); } } // This code contributed by Rajput-Ji |
Python3
# Python3 program for Painting Fence Algorithm # optimised version # Returns count of ways to color k posts def countWays(n, k): dp = [ 0 ] * (n + 1 ) total = k mod = 1000000007 dp[ 1 ] = k dp[ 2 ] = k * k for i in range ( 3 ,n + 1 ): dp[i] = ((k - 1 ) * (dp[i - 1 ] + dp[i - 2 ])) % mod return dp[n] # Driver code n = 3 k = 2 print (countWays(n, k)) # This code is contributed by shubhamsingh10 |
C#
// C# program for Painting Fence Algorithm using System; public class GFG { // Returns count of ways to color k posts // using k colors static long countWays( int n, int k) { // To store results for subproblems long [] dp = new long [n + 1]; Array.Fill(dp, 0); int mod = 1000000007; // There are k ways to color first post dp[1] = k; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) int same = 0, diff = k; // Fill for 2 posts onwards for ( int i = 2; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = ( int )(dp[i - 1] * (k - 1)); diff = diff % mod; // Total choices till i. dp[i] = (same + diff) % mod; } return dp[n]; } // Driver code static public void Main () { int n = 3, k = 2; Console.WriteLine(countWays(n, k)); } } // This code is contributed by avanitrachhadiya2155 |
Javascript
<script> // Javascript program for Painting Fence Algorithm // Returns count of ways to color k posts // using k colors function countWays(n, k) { // To store results for subproblems let dp = new Array(n + 1); dp.fill(0); let mod = 1000000007; // There are k ways to color first post dp[1] = k; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) let same = 0, diff = k; // Fill for 2 posts onwards for (let i = 2; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = (dp[i - 1] * (k - 1)); diff = diff % mod; // Total choices till i. dp[i] = (same + diff) % mod; } return dp[n]; } let n = 3, k = 2; document.write(countWays(n, k)); // This code is contributed by divyeshrabadiya07. </script> |
输出：
6
空间优化： 我们可以优化上述解决方案，使用一个变量而不是一个表。 以下是问题的实施情况：
C++
// C++ program for Painting Fence Algorithm #include <bits/stdc++.h> using namespace std; // Returns count of ways to color k posts // using k colors long countWays( int n, int k) { // There are k ways to color first post long total = k; int mod = 1000000007; // There are 0 ways for single post to // violate (same color) and k ways to // not violate (different color) int same = 0, diff = k; // Fill for 2 posts onwards for ( int i = 2; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = total * (k - 1); diff = diff % mod; // Total choices till i. total = (same + diff) % mod; } return total; } // Driver code int main() { int n = 3, k = 2; cout << countWays(n, k) << endl; return 0; } |
JAVA
// Java program for Painting Fence Algorithm class GFG { // Returns count of ways to color k posts // using k colors static long countWays( int n, int k) { // There are k ways to color first post long total = k; int mod = 1000000007 ; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) int same = 0 , diff = k; // Fill for 2 posts onwards for ( int i = 2 ; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = ( int )total * (k - 1 ); diff = diff % mod; // Total choices till i. total = (same + diff) % mod; } return total; } // Driver code public static void main(String[] args) { int n = 3 , k = 2 ; System.out.println(countWays(n, k)); } } // This code is contributed by Mukul Singh |
Python3
# Python3 program for Painting # Fence Algorithm # Returns count of ways to color # k posts using k colors def countWays(n, k) : # There are k ways to color first post total = k mod = 1000000007 # There are 0 ways for single post to # violate (same color_ and k ways to # not violate (different color) same, diff = 0 , k # Fill for 2 posts onwards for i in range ( 2 , n + 1 ) : # Current same is same as # previous diff same = diff # We always have k-1 choices # for next post diff = total * (k - 1 ) diff = diff % mod # Total choices till i. total = (same + diff) % mod return total # Driver code if __name__ = = "__main__" : n, k = 3 , 2 print (countWays(n, k)) # This code is contributed by Ryuga |
C#
// C# program for Painting Fence Algorithm using System; class GFG { // Returns count of ways to color k posts // using k colors static long countWays( int n, int k) { // There are k ways to color first post long total = k; int mod = 1000000007; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) long same = 0, diff = k; // Fill for 2 posts onwards for ( int i = 2; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = total * (k - 1); diff = diff % mod; // Total choices till i. total = (same + diff) % mod; } return total; } // Driver code static void Main() { int n = 3, k = 2; Console.Write(countWays(n, k)); } } // This code is contributed by DrRoot_ |
PHP
<?php // PHP program for Painting Fence Algorithm // Returns count of ways to color k // posts using k colors function countWays( $n , $k ) { // There are k ways to color first post $total = $k ; $mod = 1000000007; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) $same = 0; $diff = $k ; // Fill for 2 posts onwards for ( $i = 2; $i <= $n ; $i ++) { // Current same is same as previous diff $same = $diff ; // We always have k-1 choices for next post $diff = $total * ( $k - 1); $diff = $diff % $mod ; // Total choices till i. $total = ( $same + $diff ) % $mod ; } return $total ; } // Driver code $n = 3; $k = 2; echo countWays( $n , $k ) . "" ; // This code is contributed by ita_c ?> |
Javascript
<script> // JavaScript program for Painting Fence Algorithm // Returns count of ways to color k posts // using k colors function countWays(n, k) { // There are k ways to color first post let total = k; let mod = 1000000007; // There are 0 ways for single post to // violate (same color_ and k ways to // not violate (different color) let same = 0, diff = k; // Fill for 2 posts onwards for (let i = 2; i <= n; i++) { // Current same is same as previous diff same = diff; // We always have k-1 choices for next post diff = total * (k - 1); diff = diff % mod; // Total choices till i. total = (same + diff) % mod; } return total; } let n = 3, k = 2; document.write(countWays(n, k)); </script> |
输出：
6
本文由 阿迪蒂·夏尔马 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
