題目：

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.

鏈接：?http://leetcode.com/problems/paint-fence/

題解：

又是數(shù)學(xué)題，給籬笆涂色，相鄰最多兩個post可以同色。第一思路就是Dynamic Programming了。代碼大都參考了Discuss的Jenny_Shaw的。要注意的就是每次計算， 當(dāng)前的結(jié)果應(yīng)該等于sameColor和differentColor的和，而differentColor只能在k - 1種color里選，等于之前結(jié)果 * (k - 1)， sameColor等于之前的differentColor，之后進行下一次計算。

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {public int numWays(int n, int k) {if(n <= 0 || k <= 0) {return 0;}if(n == 1) {return k;}int sameColor = k;int differentColor = k * (k - 1);for(int i = 2; i < n; i++) {int tmp = differentColor;differentColor = (sameColor + differentColor) * (k - 1);sameColor = tmp;}return sameColor + differentColor;} }

?

二刷:

依然是使用dp。題目給定最多兩個fence可以用一種顏色噴漆。下面我們來仔細(xì)分析一下。

首先我們判斷邊界的條件，n <=0， ?k <= 0， n == 1

我們初始化兩個變量，sameColorLastTwo和diffColorLastTwo， 假如位于0和1位置的兩個fence用一種顏色噴的話，那么我們可以設(shè)定sameColorLastTwo = k， ?假如它們用兩種顏色噴的話，那么我們可以設(shè)定diffColorLastTwo = k * (k - 1)

接下來我們從i到n開始遍歷，我們設(shè)定diffColorLastTwo +?sameColorLastTwo等于到第i位之前，我們一種有多少種噴漆方法

先建立一個tmp保存當(dāng)前的diffColorLastTwo，也就是i-1位與i-2位使用不同顏色

假如我們我們第i位，不使用與第i-1位相同的顏色，那么我們更新diffColorLastTwo = (diffColorLastTwo +?sameColorLastTwo) * (k - 1)

假如我們第i位使用和第i - 1位相同的顏色，那么第i位的sameColorLastTwo = 第i - 1位的diffColorLastTwo?

遍歷完第n-1位后返回結(jié)果sameColorLastTwo +?diffColorLastTwo

Java:

Time Complexity - O(n)， Space Complexity - O(1)

public class Solution {public int numWays(int n, int k) {if (n <= 0 || k <= 0) {return 0;}if (n == 1) {return k;}int sameColorLastTwo = k;int diffColorLastTwo = k * (k - 1);for (int i = 2; i < n; i++) {int tmp = diffColorLastTwo;diffColorLastTwo = (sameColorLastTwo + diffColorLastTwo) * (k - 1);sameColorLastTwo = tmp;}return sameColorLastTwo + diffColorLastTwo;} }

?

三刷:

換了一點點寫法，看起來更簡潔，不過最后多做了兩次計算操作。

Java:

public class Solution {public int numWays(int n, int k) {if (n <= 0 || k <= 0) return 0;if (n == 1) return k;int res = 0;int sameColorLastTwo = k, diffColorLastTwo = k * (k - 1);for (int i = 2; i <= n; i++) {res = sameColorLastTwo + diffColorLastTwo;sameColorLastTwo = diffColorLastTwo;diffColorLastTwo = res * (k - 1);}return res;} }

?

?

Reference:

https://leetcode.com/discuss/56173/o-n-time-java-solution-o-1-space

https://leetcode.com/discuss/58451/java-dp-solution

https://leetcode.com/discuss/58879/python-solution-with-explanation

https://leetcode.com/discuss/56245/lucas-formula-maybe-o-1-and-3-4-liners

https://leetcode.com/discuss/62587/7-lines-no-special-case-code-o-n-o-1

?

轉(zhuǎn)載于:https://www.cnblogs.com/yrbbest/p/5034815.html

總結(jié)

以上是生活随笔為你收集整理的276.Paint Fence的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。