[LeetCode] 276. Paint Fence

codeKK 发布于2019-08-14 15:20 / 1606人阅读

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 total number of ways you can paint the fence.

Example

Given n=3, k=2 return 6

      post 1,   post 2, post 3
way1    0         0       1 
way2    0         1       0
way3    0         1       1
way4    1         0       0
way5    1         0       1
way6    1         1       0

Note

Solution

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

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

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

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
[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
力扣(LeetCode)276

摘要：不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。示例给定，并且是第一个错误的版本。否则把搜索下界变成因为左边一定都是，代表左边没有错误版本代码题目地址：https://leetcode-cn.com/probl...题目描述：你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质...

wushuiyong 2019-08-16 15:55 评论0 收藏0
[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原数组上动规，每一行对应一个房子，每一个元素代表从第一行的房子到这一行的房子选择这一种颜色所花的最小开销。所以每个元素该元素的值上一行两个与该元素不同列元素的值的较小者。不过这次要记录三个变量本行最小值，本行第二小值，本行最小值下标。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 评论0 收藏0