题目描述

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

算法1

DP $O(n)$

C++ 代码

    // 有n个fence post，k种color，最多连续2个post可以刷相同的颜色。问一共多少种刷法？

    // 考虑 n个post，最终只有2种情况，最后2个post刷相同颜色，或者刷不同颜色。
    // same = 最后2个刷相同颜色的刷法总数
    // diff = 最后2个刷不同颜色的刷法总数

    // 初始化，n=2时，same = k， diff = k*(k-1)
    // 假设 same_i, diff_i 是 刷到 post i的计数，求 i+1的情况：
    // 如果 i+1 与 i 刷相同颜色，则 i 必须与i-1不同色，所以 same_i+1 = diff_i
    // 如果 i+1 与 i 刷不同颜色，则 i 与 i-1 颜色相同或不同 都可以，且 i+1有 k-1种刷法，
    // 所以 diff_i+1 = (same_i + diff_i) * (k-1)

    int numWays(int n, int k) {
        if(n==0 || k==0) return 0;
        if(n==1) return k;

        // n==2
        int same = k, diff = k*(k-1);

        for(int i=3; i<=n; i++) {
            int new_same = diff;
            int new_diff = (same + diff) * (k-1);

            same = new_same;
            diff = new_diff;
        }

        return same+diff;
    }