276. Paint Fence

leejan97 发布于2019-08-16 10:28 / 1064人阅读

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方程为：
diff[i] = diff[i-1] * (k-1) + same[i-1] * (k-1),
same[i] = diff[i-1]，滚动数组优化

public class Solution {
    public int numWays(int n, int k) {
        if(n == 0) return 0;
        if(k == 0) return 0;
        
        int same = 0;
        int diff = k;
        for(int i = 1; i < n; i++) {
            int temp = diff;
            diff = (k-1) * (same + diff);
            same = temp;
        }
        return same + diff;
    }
}

私有云云服务器 Fence Paint wm paint picturebox1_paint

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

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

276. Paint Fence

摘要：代码如下表示跟前面不一样颜色，表示跟前面一样颜色跟前面不一样颜色的话，在这轮有种可能性跟前面一样颜色的话，在这轮有种可能性，且前一轮不能与前前一轮一样颜色因为这个的解法里，我们只用到变量和，所以我们可以进定步把空间复杂度降为题目：There is a fence with n posts, each post can be painted with one of the k colo...

zhjx922 2019-08-14 14:08 评论0 收藏0
[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
[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