题目地址：https://leetcode-cn.com/problems/sum-of-digits-in-the-minimum-number/
题目描述
There is a fence with n posts, each post can be painted with one of the k colors.
Youhave 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.
Example:
Input: n = 3, k = 2
Output: 6
Explanation: Take c1 as color 1, c2 as color 2. All possible ways are:
post1 post2 post3
----- ----- ----- -----
1 c1 c1 c2
2 c1 c2 c1
3 c1 c2 c2
4 c2 c1 c1
5 c2 c1 c2
6 c2 c2 c1
题目大意
有k种颜色的涂料和一个包含 n 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。 你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱最多连续两个颜色相同。然后，返回所有有效涂色的方案数。
解题方法
动态规划
设F[n]为到第n个栅栏总的配色方案数，设当前的栅栏为cur，前面一个栅栏为prev，更前面的一个栅栏为pprev.
当前栅栏cur的涂色方案有两种：
1、 和prev相同，此时说明prev的颜色应与pprev的颜色不同，pprev的涂色方法有F(n-2)种，prev的涂色方式有(k-1)种，所以此时情况应为F(n-2)*(k-1)；
2、 和prev不同，prev的涂色方法有F(n-1)种，cur的涂色方式有(k-1)种，此时情况应为F(n-1)*(k-1)；
所以递推公式应为 F(n) = F(n - 2) * (k - 1) + F(n - 1) * (k - 1)
C++代码如下：
class Solution {
public:
int numWays(int n, int k) {
if (n == 0) return 0;
if (n == 1) return k;
int pprev = k;
int prev = k * k;
int cur = k * k;
for (int i = 2; i < n; ++i) {
cur = pprev * (k - 1) + prev * (k - 1);
pprev = prev;
prev = cur;
}
return cur;
}
};
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
参考资料：https://leetcode-cn.com/problems/paint-fence/solution/c-dp-zong-jie-yi-xia-liang-chong-si-lu-by-sheng-be/
2022
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发