1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int numWays(int n, int k) {
        return helper(0, 0, 0, n, k);
    }

    public int helper(int a, int b, int pos, int n, int k) {
        if (pos == n) {
            return 1;
        }
        int sum = 0;
        for (int i = 1; i <= k; i++) {
            if (a == b && a == i) {
                continue;
            } else {
                sum += helper(b, i, pos + 1, n, k);
            }
        }
        return sum;
    }
}

这个是我自己想的递归写法. 递归函数做的事情是给它一个位置(前面的位置都假设涂好了), 它能告诉你从该位置到后面n这里一共有多少种涂法. 进入递归函数, 自然而然就是第一个位置所有的可能都调用一遍这个递归函数, 然后加在一起就是答案. 然而如果在中间位置, 我们就需要知道前两个的颜色是什么. 这样能够避开三连色. 当我们走到最后一个位置的时候之后一个位置的时候, 我们发现所有的位置都被我们涂好了, 因此这就构成一种情况, 返回1即可. 这样写时间复杂度太大. 还是看第二种解法使用DP.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// DP解法
class Solution {
    public int numWays(int n, int k) {
        int one = k;
        int two = k * k;
        if (n == 1)
            return k;
        for (int i = 3; i <= n; i++) {
            int current = (one + two) * (k - 1);
            one = two;
            two = current;
        }
        return two;
    }
}

假设num_ways[i]是从0到第i个位置所有的涂法的组合个数. 那么我们可以这么想. 假设此时我们来到了i - 1这个位置, 那么到达这个位置的所有方法个数(涂栅栏方式个数)是num_ways[i - 1]. 想象一下分散的树状图, 最右侧从上到下排列着无数的选择, 从最左侧的一个点一直到最右侧的一个点代表着一种涂法. 此时我们要在最右的点上继续扩散, 不同的扩散方向代表着我们要在i处涂的不同的颜色. 那么这些方向可以分为两类, 一类是和i - 1处的颜色不同, 这很简单就是k - 1种, 此时一定不会出现三连色的情况. 一共有nums_way[i - 1]个点供我们扩散. 于是我们表示为: num_diff[i] = num_ways[i - 1] * (k - 1). 另一类则是和i - 1处的位置一样. 那么我们需要i - 2和i - 1的颜色不同. 那么有多少个最右侧点满足这样的条件呢? num_ways[i - 1]也是由i -1和i - 2不同色的情况以及i -1
和i - 2相同色情况组合而成. 不同色不就是num_diff[i - 1]嘛. 我们刚知道它的通项公式. 于是
num_same[i] = nums_diff[i - 1] = num_ways[i - 2] * (k - 1). 于是我们有:
num_ways[i] = num_diff[i] + num_same[i] = num_ways[i - 1] * (k - 1) +
nums_ways[i - 2] * (k - 1) 合并一下就是:
num_ways[i] = (num_ways[i - 1] + num_ways[i - 2]) * (k - 1)

因此通项公式就出来了.

两种不同的类我们想象成两个树状图. 两个树状图都是一样的, 画的是所有从0到i - 1的涂的方法. 从最左边找一点再从最右边找一点, 不同的点代表颜色的选择. 二者连接走过的线代表着一种涂法. 那么其中一颗树, 我们需要在最右端继续发散, 每一种情况都可以往外发散不同的方向, 到达不同的点, 被到达的点代表着在i这个位置的颜色的选择. 第一颗树代表发散向和i - 1不同颜色的树. 此时完成这个树后, i 和 i - 1的点颜色一定不同. 另一颗代表i和i - 1相同颜色的树. 此时有的i点可能发散不出东西因为i - 1和i - 2的颜色相同. 当然有的能发散出且只能发散出一条线,这条线就代表着和i - 1颜色相同的线. 两个树和在一起就是最终的结果. 这样就明显了. 第一颗树很简单, 每个i - 1点都能发散出k - 1个额外的路. 对于第二颗树, 那些i - 1和i - 2不同颜色的路线才能发散出额外的线. 于是回归到如何求i -
1时涂的可能路线. 也是包含从i - 2发散出的和i - 2相同颜色以及不同颜色的线. 于是也就很容易得到i - 1和i - 2不同的颜色的线有到达i - 2涂的方法乘上k - 1即可.

感觉这类问题就是树状图. 用树状图让自己有个直观感受. 每个点代表着自己此时的选择, 线连接了不同的选择, 从最左边点走到最右边点构成了一个完整的选择链,也就是一种所谓的排列组合. 一般都是让求一共有多少种. 我之前考虑这道题都是单门对一个点, 他会有多少种选择, 然后再一乘总的这种点的个数就完成了一次树状图的扩散. 这道题反而是把所有最右侧的点放在一起进行分类. 一类是看这类发散出去的有多少种, 另一类看自己发散出去的有多少种. 两类一加, 齐活. 其实我的想法感觉也行, 如果对于某个点, 它的前两个点相同, 那么它有k - 1种选择, 如果前两个点不同, 那么它有k种选择. 那么自己前两个点不同的情况有多少种呢? num_diff[i - 1], 前两个点相同的呢? num_same[i - 1]. 难是难在意识不到:
num_ways[i] = nums_diff[i - 1] + nums_same[i];
这又给我种感觉是写DP就要多使用未知数来表示一些值, 就比如这里的nums_diff和nums_same, 用这些未知数来去逐渐清晰地构成我们的通项公式. 最后让它们互相抵消, 只剩下一个未知数, 上面这个例子中就是让最后只剩下nums_way[i]也就是我们想要的答案.

时间复杂度: O(n)
空间复杂度: O(1)