leetcode276. 栅栏涂色

有 k 种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。

你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个 颜色相同。然后，返回所有有效涂色的方案数。

注意:
n 和 k 均为非负的整数。

示例:

输入: n = 3，k = 2
输出: 6
解析: 用 c1 表示颜色 1，c2 表示颜色 2，所有可能的涂色方案有:

            柱 1    柱 2   柱 3     
 -----      -----  -----  -----       
   1         c1     c1     c2 
   2         c1     c2     c1 
   3         c1     c2     c2 
   4         c2     c1     c1  
   5         c2     c1     c2
   6         c2     c2     c1

思路：动态规划。

n=1,k钟

n=2,k*k种。

n>2:

n可以和n-1位置颜色相同，这时这两个位置可选项有k-1种颜色可用，再乘n-2位置方案总数。

n可以和n-1位置颜色不同，这时这个位置有k-1种颜色可用，再乘n-1位置的方案总数。

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 public int numWays(int n, int k) {
     
    
   

    

     

    
    

     
 if(n==0)return 0;
     
    
   

    

     

    
    

     
 if(n==1)return k;
     
    
   

    

     

    
    

     
 int[] arr=new int[n];
     
    
   

    

     

    
    

     

       arr[0]=k;
     
    
   

    

     

    
    

     

       arr[1]=k*k;
     
    
   

    

     

    
    

     
 for(int i=2;i<n;i++){
     
    
   

    

     

    
    

     

       arr[i]=(arr[i-1]+arr[i-2])*(k-1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return arr[n-1];
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104143343