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.
一刷
题解：
用两个变量(二变量dp)，一个保存如果当前跟上一个颜色相同所有的组合，一个跟上一个不同，所有的组合
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;//combine
int diffColorLastTwo = k*(k-1);
for(int i=2; i<=n; i++){
res = sameColorLastTwo + diffColorLastTwo;
sameColorLastTwo = diffColorLastTwo;//overall
diffColorLastTwo = res*(k-1);
}
return res;
}
}
二刷-二变量dp
class Solution {
public int numWays(int n, int k) {
if(n<=0 || k<=0) return 0;
if(n == 1) return k;
int same = k, diff = k*(k-1);
for(int i=2; i<n; i++){
int same_ori = same;
same = diff;
diff = (same_ori + diff)*(k-1);
}
return same + diff;
}
}
