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
示例

解题
f(n - 1)
,再前一个栅栏的颜色数量为f(n - 2
。k - 1
(因为当前栅栏和前一个栅栏颜色一样,所以前一个栅栏颜色和更前一个展览的颜色不能一样,少一种颜色选择),这种情况的颜色数量为f(n - 2) * (k - 1)
。k - 1
种,总的颜色数量为f(n - 1) * (k - 1)
。f(n) = f(n - 1) * (k - 1) + f(n - 2) * (k - 1)
。class Solution {
public:
int numWays(int n, int k) {
int prev, pprev, rs, i;
if (n <= 0 || k <= 0)
return 0;
if (n == 1)
return k;
pprev = k;
prev = k * k;
rs = prev;
for (i = 2; i < n; i++) {
rs = pprev * (k - 1) + prev * (k - 1);
pprev = prev;
prev = rs;
}
return rs;
}
};
方法二:动态规划
-
dp1 = prev_dp1
-
dp2 = (k – 1) * (dp1 + dp2)
k - 1
。class Solution {
public:
int numWays(int n, int k) {
int dp1, dp2, rs, i;
if (n <= 0 || k <= 0)
return 0;
if (n == 1)
return k;
dp1 = k;
dp2 = k * (k - 1);
for (i = 2; i < n; i++) {
rs = (dp1 + dp2) * (k - 1);
dp1 = dp2;
dp2 = rs;
}
return dp1 + dp2;
}
};
原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/11897.html