Edit on 8月5號。
我還以為Paint Fence這題我會做呢酱床。羊赵。。沒想到一點(diǎn)思路都沒有斤葱。 用DP記錄組合的數(shù)量好像我是第一次做吧慷垮？而且還是雙變量的DP問題。揍堕。料身。
他的答案是： 做一個(gè)DP array，這個(gè)array代表著假設(shè)我只有N個(gè)fence衩茸，有k個(gè)color芹血，一共有多少種組合。 所以說楞慈，也許多變量DP題幔烛，只用1D array 就可以了。
看到else?
dp[i] = dp[i-1](k-1) + dp(i-2)*(k-1) 我有點(diǎn)恍然大悟囊蓝。 其實(shí)就是把之前的combination數(shù)量記在array里饿悬。因?yàn)橛幸粋€(gè)no adjacent的限制。 而且還有一個(gè)重要的聚霜，當(dāng)看到問題為"return ...的數(shù)量" 這種問題大部分情況下不需要去想組合到底是什么狡恬，只要知道計(jì)算數(shù)量就好了。
