276. Paint Fence

zhjx922 发布于2019-08-14 14:08 / 1261人阅读

摘要：代码如下表示跟前面不一样颜色，表示跟前面一样颜色跟前面不一样颜色的话，在这轮有种可能性跟前面一样颜色的话，在这轮有种可能性，且前一轮不能与前前一轮一样颜色因为这个的解法里，我们只用到变量和，所以我们可以进定步把空间复杂度降为

题目：
There is a fence with n posts, each post can be painted with one of the k colors.

You have to paint all the posts such that no more than two adjacent fence posts have the same color.

Return the total number of ways you can paint the fence.

Note:
n and k are non-negative integers.

解答：
这道题其实跟house rob很类似，用dp做的时候在function部分很容易写错，当取跟前面不一样的颜色时，这一轮一共有除了前面这个颜色的k-1个颜色可以选；当取跟前面一样的颜色的时候，这一轮只有一种情况可以选，且：前一轮不能取跟前前一轮一样的颜色，否则这三个post的颜色就都相同了，不符合题中说的最多两个相邻的post颜色相同。代码如下：

public class Solution {
    //State: f[i][j] is total number of ways we can paint the fence;
    //Function: f[i][0] = f[i - 1][0] * k - 1 + f[i - 1][1] * (k - 1)
    //          f[i][1] = f[i - 1][0] + f[i - 1][1]
    //Initialize: f[0][0] = k, f[0][1] = k; f[1][0] = k * (k - 1), f[1][1] = k;
    //Result: f[n - 1][0] + f[n - 1][1];
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int[][] f = new int[n][2];
        //Initialize
        f[0][1] = f[1][1] = k;
        f[0][0] = k;
        f[1][0] = k * (k - 1);
        //f[i][0]表示跟前面不一样颜色，f[i][1]表示跟前面一样颜色
        for (int i = 2; i < n; i++) {
            //跟前面不一样颜色的话，在这轮有k - 1种可能性
            f[i][0] = f[i - 1][0] * (k - 1) + f[i - 1][1] * (k - 1);
            //跟前面一样颜色的话，在这轮有1种可能性，且前一轮不能与前前一轮一样颜色
            f[i][1] = f[i - 1][0];
        }
        
        return f[n - 1][0] + f[n - 1][1];
    }
}

因为这个dp的解法里，我们只用到变量i - 1和i，所以我们可以进定步把空间复杂度降为o(1):

 //Save space to O(1) because it only cares about i - 1 and i
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int diff = k * (k - 1);
        int same = k;
        for (int i = 2; i < n; i++) {
            int tmp = diff;
            diff = (diff + same) * (k - 1);
            same = tmp;
        }
        return same + diff;
    }

GPU云服务器云服务器 Fence Paint wm paint picturebox1_paint

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64831.html

[LeetCode] 276. Paint Fence

Problem There is a fence with n posts, each post can be painted with one of the k colors.You have to paint all the posts such that no more than two adjacent fence posts have the same color.Return the ...

codeKK 2019-08-14 15:20 评论0 收藏0
276. Paint Fence

276. Paint Fence 题目链接：https://leetcode.com/problems... dp来解，subproblem是：diff[i]: number of paints when current i is different from i - 1, same[i]: number of paints when current i is same as i-1所以dp方程为...

leejan97 2019-08-16 10:28 评论0 收藏0
[Leetcode] Paint Fence 栅栏涂色

摘要：假设是第一根柱子及之前涂色的可能性数量，是第二根柱子及之前涂色的可能性数量，则。递推式有了，下面再讨论下情况，所有柱子中第一根涂色的方式有中，第二根涂色的方式则是，因为第二根柱子可以和第一根一样。 Paint Fence There is a fence with n posts, each post can be painted with one of the k colors. ...

sixleaves 2019-08-14 12:36 评论0 收藏0
LockSupport中的park与unpark原理

摘要：的好处在于，在诊断问题的时候能够知道的原因推荐使用带有的操作函数作用用于挂起当前线程，如果许可可用，会立马返回，并消费掉许可。 LockSupport是用来创建locks的基本线程阻塞基元，比如AQS中实现线程挂起的方法，就是park,对应唤醒就是unpark。JDK中有使用的如下 showImg(https://segmentfault.com/img/bVblcXS?w=884&h...

bigdevil_s 2019-08-16 14:00 评论0 收藏0
Java容器类研究4：ArrayList

摘要：显然，开发人员认为通过下标遍历的数组结构更加高效。在进行分裂时，原始保留中部至末尾的元素，新的保留原起始位置到中部的元素。同样，也会进行重新赋值，使得在使用前与保持一致。在遍历时，会调用方法，将动作施加于元素之上。 java.util.ArrayList ArrayList继承自AbstractList，AbstractList为随机访问数据的结构，如数组提供了基本实现，并且提供了It...

xfee 2019-08-15 12:08 评论0 收藏0