276. Paint Fence

leejan97 發布于2019-08-16 10:28 / 1274人閱讀

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方程為：
diff[i] = diff[i-1] * (k-1) + same[i-1] * (k-1),
same[i] = diff[i-1]，滾動數組優化

public class Solution {
    public int numWays(int n, int k) {
        if(n == 0) return 0;
        if(k == 0) return 0;
        
        int same = 0;
        int diff = k;
        for(int i = 1; i < n; i++) {
            int temp = diff;
            diff = (k-1) * (same + diff);
            same = temp;
        }
        return same + diff;
    }
}

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

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

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

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] 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
[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