270. Closest Binary Search Tree Value 最接近的二叉搜索树值

• 作者： 负雪明烛
• id： fuxuemingzhu
• 个人博客：http://fuxuemingzhu.cn/

---

@TOC

题目地址：https://leetcode-cn.com/problems/paint-fence/

题目描述

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.

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 个栅栏柱的栅栏，每个栅栏柱可以用其中一种颜色进行上色。

你需要给所有栅栏柱上色，并且保证其中相邻的栅栏柱 最多连续两个颜色相同。然后，返回所有有效涂色的方案数。

解题方法

动态规划

假设当前的栅栏为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) 种，当前栅栏的涂色方式有 (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;
    }
};

参考资料：https://leetcode-cn.com/problems/paint-fence/solution/c-dp-zong-jie-yi-xia-liang-chong-si-lu-by-sheng-be/

日期

2019 年 9 月 17 日 —— 听了hulu宣讲会，觉得hulu的压力不大