276. Paint Fence

leejan97 發(fā)布于2019-08-16 10:28 / 1285人閱讀

276. Paint Fence

題目鏈接：https://leetcode.com/problems...

dp來(lái)解，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]，滾動(dòng)數(shù)組優(yōu)化

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云服務(wù)器云服務(wù)器 Fence Paint wm paint picturebox1_paint

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.specialneedsforspecialkids.com/yun/69862.html

相關(guān)文章

276. Paint Fence

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

zhjx922 2019-08-14 14:08 評(píng)論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 評(píng)論0 收藏0
[Leetcode] Paint Fence 柵欄涂色

摘要：假設(shè)是第一根柱子及之前涂色的可能性數(shù)量，是第二根柱子及之前涂色的可能性數(shù)量，則。遞推式有了，下面再討論下情況，所有柱子中第一根涂色的方式有中，第二根涂色的方式則是，因?yàn)榈诙涌梢院偷谝桓粯印? 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 評(píng)論0 收藏0
LockSupport中的park與unpark原理

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

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

摘要：顯然，開發(fā)人員認(rèn)為通過(guò)下標(biāo)遍歷的數(shù)組結(jié)構(gòu)更加高效。在進(jìn)行分裂時(shí)，原始保留中部至末尾的元素，新的保留原起始位置到中部的元素。同樣，也會(huì)進(jìn)行重新賦值，使得在使用前與保持一致。在遍歷時(shí)，會(huì)調(diào)用方法，將動(dòng)作施加于元素之上。 java.util.ArrayList ArrayList繼承自AbstractList，AbstractList為隨機(jī)訪問(wèn)數(shù)據(jù)的結(jié)構(gòu)，如數(shù)組提供了基本實(shí)現(xiàn)，并且提供了It...

xfee 2019-08-15 12:08 評(píng)論0 收藏0