[LeetCode] 276. Paint Fence

codeKK 發布于2019-08-14 15:20 / 1708人閱讀

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

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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