动态规划 - 涂栅栏算法

Question

有一个有着n个柱子的围墙，每个柱子可以涂上k种颜色之一。你需要将所有柱子都涂上颜色，以使得相邻的柱子最多只有两个颜色相同。返回您可以涂色的围栏的总方案数。

diff - 不同颜色的组合数，
same - 相同颜色的组合数，
n - 柱子数量，
k - 颜色数量。

当 n = 1 时：

diff = k;
same = 0;

当n = 2时：

diff = k * (k - 1);
same = k;

当 n = 3 时：

diff = (k + k * (k - 1)) * (k - 1);
same = k * (k - 1);

最终的公式是:

diff[i] = (diff[i - 1] + diff[i - 2]) * (k - 1);
same[i] =  diff[i - 1];

我知道如何找到same[i]，但是我不明白如何找到diff[i]。你能解释一下diff[i]的公式吗？

- Oleksandr Pyrohov

Answer 1

total[i] = diff[i] + same[i]   (definition)

diff[i] = (k - 1) * total[i-1]
        = (k - 1) * (diff[i-1] + same[i-1])
        = (k - 1) * (diff[i-1] + diff[i-2])

- Beta

Answer 2

这里是一个组合数学的证明。

令 diff[i, c] 为按照问题陈述的规则涂色，使得最后一个栅栏被涂成颜色 c 的i个柱子的涂色方案数。

我们有：

diff[i, c] = diff[i - 1, c'] + diff[i - 2, c''], c' != c OR c'' != c

对于我们用来涂色 i 的每个c，前一个可以以c' != c 结束（在这种情况下，我们不关心第二个上一个是什么），或者第二个上一个可以以c'' != c 结束（在这种情况下，我们不关心前一个是什么），或两个都是。

c'！= c有k-1 种可能性，c''！= c也有k-1 种可能性。因此，我们可以从递归中删除c并简单地编写：

diff[i] = (k - 1) * (diff[i - 1] + diff[i - 2])

这就是你所拥有的。

- IVlad

---

公式中有一个小错误，第二个 diff[i-1] 应该是 diff[i-2]。 - user908645

非常有教育意义的解释。如果我在面试中遇到这个问题，我可能会这样推理：1）最后两个帖子颜色相同，因此最后两个帖子不能与最后三个帖子相同。（k-1）* diff [n-2]2）最后两个帖子有不同的颜色。（k-1）* diff [n-1]它们一起构成（k-1）*（diff [n-2] + diff [n-1]） - user908645

Answer 3

该解决方案需要详细的解释，请查看。

public class PaintingFence {

  public static int paintFence(int n, int k) {
    //if there is 0 post then the ways to color it is 0.
    if(n == 0) return 0;

    //if there is one 1 post then the way to color it is k ways.
    if(n == 1) return k;

    /**
     * Consider the first two post.
     * case 1. When both post is of same color
     *    first post can be colored in k ways.
     *    second post has to be colored by same color.
     *    So the way in which the first post can be colored with same color is k * 1.
     *
     * case 2. When both post is of diff color
     *    first post can be colored in k ways.
     *    second post can be colored in k-1 ways.
     *    Hence the ways to color two post different is k * (k - 1)
     */
    int same = k * 1;
    int diff = k * (k -1);

    /**
     * As first 2 posts are already discussed, we will start with the third post.
     *
     * If the first two post are same then to make the third post different, we have
     * k-1 ways. Hence same * (k-1)
     * [same=k, so same * k-1 = k*(k-1) = diff => Remember this.]
     *
     * If the first two posts are different then to make the third different, we also have
     * k - 1 ways. Hence diff * (k-1)
     *
     * So to make third post different color, we have
     *  same * (k-1) + diff * (k-1)
     *  = (same + diff) * (k-1)
     *  = k-1 * (same + diff)
     */
    for(int i=3;i <=n; i++) {
      int prevDiff = diff;
      diff = (same + diff) * (k - 1); //as stated above

      /**
       * to make the third color same, we cannot do that because of constraint that only two
       * posts can be of same color. So in this case, we cannot have to same color so it has to be
       * diff.
       */
      same = prevDiff * 1;
    }

    return same + diff;
  }

  public static void main(String[] args) {
    System.out.println(paintFence(2, 4));
    System.out.println(paintFence(3, 2));
  }

}

- Juvenik