276. Paint Fence

zhjx922 發布于2019-08-14 14:08 / 1264人閱讀

摘要：代碼如下表示跟前面不一樣顏色，表示跟前面一樣顏色跟前面不一樣顏色的話，在這輪有種可能性跟前面一樣顏色的話，在這輪有種可能性，且前一輪不能與前前一輪一樣顏色因為這個的解法里，我們只用到變量和，所以我們可以進定步把空間復雜度降為

題目：
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.

解答：
這道題其實跟house rob很類似，用dp做的時候在function部分很容易寫錯，當取跟前面不一樣的顏色時，這一輪一共有除了前面這個顏色的k-1個顏色可以選；當取跟前面一樣的顏色的時候，這一輪只有一種情況可以選，且：前一輪不能取跟前前一輪一樣的顏色，否則這三個post的顏色就都相同了，不符合題中說的最多兩個相鄰的post顏色相同。代碼如下：

public class Solution {
    //State: f[i][j] is total number of ways we can paint the fence;
    //Function: f[i][0] = f[i - 1][0] * k - 1 + f[i - 1][1] * (k - 1)
    //          f[i][1] = f[i - 1][0] + f[i - 1][1]
    //Initialize: f[0][0] = k, f[0][1] = k; f[1][0] = k * (k - 1), f[1][1] = k;
    //Result: f[n - 1][0] + f[n - 1][1];
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int[][] f = new int[n][2];
        //Initialize
        f[0][1] = f[1][1] = k;
        f[0][0] = k;
        f[1][0] = k * (k - 1);
        //f[i][0]表示跟前面不一樣顏色，f[i][1]表示跟前面一樣顏色
        for (int i = 2; i < n; i++) {
            //跟前面不一樣顏色的話，在這輪有k - 1種可能性
            f[i][0] = f[i - 1][0] * (k - 1) + f[i - 1][1] * (k - 1);
            //跟前面一樣顏色的話，在這輪有1種可能性，且前一輪不能與前前一輪一樣顏色
            f[i][1] = f[i - 1][0];
        }
        
        return f[n - 1][0] + f[n - 1][1];
    }
}

因為這個dp的解法里，我們只用到變量i - 1和i，所以我們可以進定步把空間復雜度降為o(1):

 //Save space to O(1) because it only cares about i - 1 and i
    public int numWays(int n, int k) {
        if (n == 0 || k == 0) return 0;
        if (n == 1) return k;
        int diff = k * (k - 1);
        int same = k;
        for (int i = 2; i < n; i++) {
            int tmp = diff;
            diff = (diff + same) * (k - 1);
            same = tmp;
        }
        return same + diff;
    }

GPU云服務器云服務器 Fence Paint wm paint picturebox1_paint

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64831.html

[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 2019-08-14 15:20 評論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 2019-08-16 10:28 評論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
LockSupport中的park與unpark原理

摘要：的好處在于，在診斷問題的時候能夠知道的原因推薦使用帶有的操作函數作用用于掛起當前線程，如果許可可用，會立馬返回，并消費掉許可。 LockSupport是用來創建locks的基本線程阻塞基元，比如AQS中實現線程掛起的方法，就是park,對應喚醒就是unpark。JDK中有使用的如下 showImg(https://segmentfault.com/img/bVblcXS?w=884&h...

bigdevil_s 2019-08-16 14:00 評論0 收藏0
Java容器類研究4：ArrayList

摘要：顯然，開發人員認為通過下標遍歷的數組結構更加高效。在進行分裂時，原始保留中部至末尾的元素，新的保留原起始位置到中部的元素。同樣，也會進行重新賦值，使得在使用前與保持一致。在遍歷時，會調用方法，將動作施加于元素之上。 java.util.ArrayList ArrayList繼承自AbstractList，AbstractList為隨機訪問數據的結構，如數組提供了基本實現，并且提供了It...

xfee 2019-08-15 12:08 評論0 收藏0