[Leetcode] Paint Fence 栅栏涂色

sixleaves 发布于2019-08-14 12:36 / 1050人阅读

摘要：假设是第一根柱子及之前涂色的可能性数量，是第二根柱子及之前涂色的可能性数量，则。递推式有了，下面再讨论下情况，所有柱子中第一根涂色的方式有中，第二根涂色的方式则是，因为第二根柱子可以和第一根一样。

Paint Fence

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.

哈希表法 复杂度

时间 O(N) 空间 O(1)

思路

这种给定一个规则，计算有多少种结果的题目一般都是动态规划，因为我们可以从这个规则中得到递推式。根据题意，不能有超过连续两根柱子是一个颜色，也就意味着第三根柱子要么根第一个柱子不是一个颜色，要么跟第二根柱子不是一个颜色。如果不是同一个颜色，计算可能性的时候就要去掉之前的颜色，也就是k-1种可能性。假设dp[1]是第一根柱子及之前涂色的可能性数量，dp[2]是第二根柱子及之前涂色的可能性数量，则dp[3]=(k-1)*dp[1] + (k-1)*dp[2]。

递推式有了，下面再讨论下base情况，所有柱子中第一根涂色的方式有k中，第二根涂色的方式则是k*k，因为第二根柱子可以和第一根一样。

代码

public class Solution {
    public int numWays(int n, int k) {
        // 当n=0时返回0
        int dp[] = {0, k , k*k, 0};
        if(n <= 2){
            return dp[n];
        }
        for(int i = 2; i < n; i++){
            // 递推式：第三根柱子要么根第一个柱子不是一个颜色，要么跟第二根柱子不是一个颜色
            dp[3] = (k - 1) * (dp[1] + dp[2]);
            dp[1] = dp[2];
            dp[2] = dp[3];
        }
        return dp[3];
    }
}

服务器托管私有云 Fence 栅栏 Paint LeetCode

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

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

[Leetcode] Paint House 房子涂色

摘要：动态规划复杂度时间空间思路直到房子，其最小的涂色开销是直到房子的最小涂色开销，加上房子本身的涂色开销。我们在原数组上修改，可以做到不用空间。代码找出最小和次小的，最小的要记录下标，方便下一轮判断 Paint House There are a row of n houses, each house can be painted with one of the three colors...

SunZhaopeng 2019-08-14 12:46 评论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
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
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
CTF编码全家桶小程序

摘要：编码全家桶小程序提供实体莫尔斯电码等编码转换工具，凯撒密码栅栏密码等加密工具，及地址查询信息查询等工具。 CTF编码全家桶小程序提供Base64、Url、HTML实体、莫尔斯电码等编码转换工具，凯撒密码、栅栏密码、ROT13、MD5、SHA等加密工具，及IP地址查询、Whois信息查询等工具。showImg(https://segmentfault.com/img/bVbiudU?w=...

zlyBear 2019-08-23 12:28 评论0 收藏0