国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

[Leetcode] Paint Fence 柵欄涂色

sixleaves / 1221人閱讀

摘要：假設是第一根柱子及之前涂色的可能性數量，是第二根柱子及之前涂色的可能性數量，則。遞推式有了，下面再討論下情況，所有柱子中第一根涂色的方式有中，第二根涂色的方式則是，因為第二根柱子可以和第一根一樣。

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

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

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

  • 276. Paint Fence

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

    zhjx922 評論0 收藏0

  • CTF編碼全家桶小程序

    摘要：編碼全家桶小程序提供實體莫爾斯電碼等編碼轉換工具，凱撒密碼柵欄密碼等加密工具，及地址查詢信息查詢等工具。 CTF編碼全家桶小程序提供Base64、Url、HTML實體、莫爾斯電碼等編碼轉換工具，凱撒密碼、柵欄密碼、ROT13、MD5、SHA等加密工具，及IP地址查詢、Whois信息查詢等工具。showImg(https://segmentfault.com/img/bVbiudU?w=...

    zlyBear 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<