X

LEETCODE 276. Paint Fence 解题思路分析

题目大意:

粉刷栅栏

一个栅栏上有n个柱子,每个柱子可以从k个颜色中选择一种进行粉刷。

粉刷所有柱子,并且最多只允许2棵相邻柱子颜色相同。

求总共的粉刷方案数。

注意:n和k都是非负整数。

示例:

输入: n = 3, k = 2
输出: 6
解释: 颜色1为c1,颜色2为c2,所有的粉刷方案如下:

            post1  post2  post3      
 -----      -----  -----  -----       
   1         c1     c1     c2 
   2         c1     c2     c1 
   3         c1     c2     c2 
   4         c2     c1     c1  
   5         c2     c1     c2
   6         c2     c2     c1

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=276

解题思路分析:

我们可以按照从左至右的顺序粉刷柱子,当前柱子可以选择的颜色种类取决于,相邻之前柱子连续相同颜色的个数。如果之前相同个数等于2,说明这个颜色当前不能使用,因此可选的颜色种类为k-1。在这k-1种颜色中任选一种都不会和之前相邻的颜色冲重复,因此,此时连续相同颜色变为1,递归至下一层继续。如果之前的连续相同颜色数小于2,那么我们不仅可以使用其他的k-1种颜色,同时还可以使用相邻之前柱子的颜色,此时,可选择的颜色种类为1,连续相同颜色个数加一。

实现代码:

int[][] memo; // 记忆数组
public int numWays(int n, int k) {
    // 例外情况返回0
    if(n==0 || k==0 || k==1 && n>2) return 0;
    // 初始化记忆数组
    memo=new int[n][3];
    // 递归求解
    return help(n,k,0,0);
}

int help(int n, int k, int index, int sameCount){
    // 如果越界,返回1
    if(index==n) return 1;
    // 如果记忆数组中存在当前解,返回记忆数组中的值
    if(memo[index][sameCount]>0) return memo[index][sameCount];
    // 返回值
    int count=0;
    // 如果连续相同颜色数小于等于1,
    if(sameCount<=1){
        // 选择与之前相同的颜色,连续相同颜色数加一
        count+= help(n, k, index+1, sameCount+1);
    }
    // 选择与之前不同的颜色,有k-1中选法
    // 此时连续相同颜色为1
    count+= (k-1)*help(n, k, index+1, 1);
    // 将结果保存至记忆数组
    memo[index][sameCount]=count;
    return count;
}

本题解法执行时间为0ms。

Runtime: 0 ms, faster than 100.00% of Java online submissions for Paint Fence.

Memory Usage: 32.8 MB, less than 22.22% of Java online submissions for Paint Fence.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-276-paint-fence-解题思路分析/
Categories: leetcode
kwantong: