[LeetCode] 276. Paint Fence

codeKK 發(fā)布于2019-08-14 15:20 / 1711人閱讀

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];
    }
}

GPU云服務(wù)器云服務(wù)器 Fence Paint LeetCode wm paint

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/65637.html

相關(guān)文章

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 評(píng)論0 收藏0
276. Paint Fence

摘要：代碼如下表示跟前面不一樣顏色，表示跟前面一樣顏色跟前面不一樣顏色的話，在這輪有種可能性跟前面一樣顏色的話，在這輪有種可能性，且前一輪不能與前前一輪一樣顏色因?yàn)檫@個(gè)的解法里，我們只用到變量和，所以我們可以進(jìn)定步把空間復(fù)雜度降為題目：There is a fence with n posts, each post can be painted with one of the k colo...

zhjx922 2019-08-14 14:08 評(píng)論0 收藏0
[Leetcode] Paint Fence 柵欄涂色

摘要：假設(shè)是第一根柱子及之前涂色的可能性數(shù)量，是第二根柱子及之前涂色的可能性數(shù)量，則。遞推式有了，下面再討論下情況，所有柱子中第一根涂色的方式有中，第二根涂色的方式則是，因?yàn)榈诙涌梢院偷谝桓粯印? 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 評(píng)論0 收藏0
力扣(LeetCode)276

摘要：不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)量檢測(cè)。由于每個(gè)版本都是基于之前的版本開發(fā)的，所以錯(cuò)誤的版本之后的所有版本都是錯(cuò)的。示例給定，并且是第一個(gè)錯(cuò)誤的版本。否則把搜索下界變成因?yàn)樽筮呉欢ǘ际牵碜筮厸]有錯(cuò)誤版本代碼題目地址：https://leetcode-cn.com/probl...題目描述：你是產(chǎn)品經(jīng)理，目前正在帶領(lǐng)一個(gè)團(tuán)隊(duì)開發(fā)新的產(chǎn)品。不幸的是，你的產(chǎn)品的最新版本沒有通過質(zhì)...

wushuiyong 2019-08-16 15:55 評(píng)論0 收藏0
[LintCode/LeetCode] Paint House I & Paint Hous

摘要：在原數(shù)組上動(dòng)規(guī)，每一行對(duì)應(yīng)一個(gè)房子，每一個(gè)元素代表從第一行的房子到這一行的房子選擇這一種顏色所花的最小開銷。所以每個(gè)元素該元素的值上一行兩個(gè)與該元素不同列元素的值的較小者。不過這次要記錄三個(gè)變量本行最小值，本行第二小值，本行最小值下標(biāo)。 Paint House Problem There are a row of n houses, each house can be painted ...

ChristmasBoy 2019-08-14 16:22 評(píng)論0 收藏0