Massive Algorithms: LeetCode 276

LeetCode 276 - Fence Painter

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

https://baihuqian.github.io/2018-07-29-paint-fence/

If n == 1, there would be k-ways to paint.

if n == 2, there would be two situations:

2.1 You paint same color with the previous post: k*1 ways to paint, named it as same;
2.2 You paint differently with the previous post: k*(k-1) ways to paint this way, named it as diff.

So, you can think, if n >= 3, you can always maintain these two situations, You either paint the same color with the previous one, or differently.

Since there is a rule: “no more than two adjacent fence posts have the same color.”

We can further analyze:

from 2.1, since previous two are in the same color, next one you could only paint differently, and it would form one part of “paint differently” case in the n == 3 level, and the number of ways to paint this way would equal to same*(k-1).
from 2.2, since previous two are not the same, you can either paint the same color this time (diff*1) ways to do so, or stick to paint differently (diff*(k-1)) times.

Here you can conclude, when seeing back from the next level, ways to paint the same, or variable same would equal to diff*1 = diff, and ways to paint differently, variable diff, would equal to same * (k - 1) + diff * (k - 1) = (same + diff) * (k - 1).

    def numWays(self, n, k):
        if k == 0 or n == 0:
            return 0
        if n == 1:
            return k

        same = k
        diff = k * (k - 1)
        for _ in range(3, n + 1):
            same, diff = diff, (same + diff) * (k - 1)

        return same + diff

https://blog.csdn.net/qq508618087/article/details/50863010

所以在染一个柱子的时候, 要考虑是否和上一个柱子颜色相同.

如果和上一个相同的话那么上一个有多少种和上上次不同的染色方案, 那么当前柱子也有多少种染色方案.

如果和上一个不同的话那么染色方案就为(k-1)*(之前总共多少染色方案).

http://www.cnblogs.com/grandyang/p/5231220.html

这道题让我们粉刷篱笆，有n个部分需要刷，有k种颜色的油漆，规定了不能有超过两个的相同颜色涂的部分，问我们总共有多少种刷法。那么我们首先来分析一下，如果n=0的话，说明没有需要刷的部分，直接返回0即可，如果n为1的话，那么有几种颜色，就有几种刷法，所以应该返回k，当n=2时，k=2时，我们可以分两种情况来统计，一种是相邻部分没有相同的，一种相同部分有相同的颜色，那么对于没有相同的，对于第一个格子，我们有k种填法，对于下一个相邻的格子，由于不能相同，所以我们只有k-1种填法。而有相同部分颜色的刷法和上一个格子的不同颜色刷法相同，因为我们下一格的颜色和之前那个格子颜色刷成一样的即可，最后总共的刷法就是把不同和相同两个刷法加起来

    int numWays(int n, int k) {
        if (n == 0) return 0;
        int same = 0, diff = k;
        for (int i = 2; i <= n; ++i) {
            int t = diff;
            diff = (same + diff) * (k - 1);
            same = t;
        }
        return same + diff;
    }

https://blog.csdn.net/starstar1992/article/details/56286264

这种给定一个规则，计算有多少种结果的题目一般都是动态规划，因为我们可以从这个规则中得到递推式。根据题意，不能有超过连续两根柱子是一个颜色，也就意味着第三根柱子要么根第一个柱子不是一个颜色，要么跟第二根柱子不是一个颜色。如果不是同一个颜色，计算可能性的时候就要去掉之前的颜色，也就是k-1种可能性。假设dp[1]是第一根柱子及之前涂色的可能性数量，dp[2]是第二根柱子及之前涂色的可能性数量，则dp[3]=(k-1)*dp[1] + (k-1)*dp[2]。

递推式有了，下面再讨论下base情况，所有柱子中第一根涂色的方式有k中，第二根涂色的方式则是k*k，因为第二根柱子可以和第一根一样。

复杂度

时间 O(N) 空间 O(1)

另一种解释：

分析：

由题目可以知道，最多有两个相邻的栅栏可以涂相同的颜色。

则主要思想是，如果前两根栅栏颜色相同，则第三根栅栏的颜色不能跟前两根的栅栏颜色相同，若是前两根栅栏颜色不同，则第三根栅栏颜色随便涂。综合的思想就是，第三根栅栏或者与第一根栅栏的颜色不同，或者与第二根的栅栏颜色不同。（即，包括了，可以与前两个栅栏的颜色都不同，与第一根栅栏颜色不同时，可以与第二根相同，与第二根栅栏不同的时候可以与第一根相同）。

如果用num[0]表示第一根栅栏以及之前栅栏总共可以涂色的方法数量；（栅栏数量为i时的方法数量）

num[1]表示第二根栅栏以及之前栅栏总共可以涂色的方法数量；（栅栏数量为i+1时的方法数量）

num[ 2]表示第三根以及之前总共可以涂色的方法数量

num[3] = (k-1)*num[0] + (k-1)*num[1];

public int numWays(int n, int k) {

// 当n=0时返回0

int dp[] = {0, k, k * k, 0};

if (n <= 2) {

return dp[n];

}

for (int i = 2; i < n; i++) {

// 递推式：第三根柱子要么根第一个柱子不是一个颜色，要么跟第二根柱子不是一个颜色

dp[3] = (k - 1) * (dp[1] + dp[2]);

dp[1] = dp[2];

dp[2] = dp[3];

}

return dp[3];

}

因为题目要求是不超过两个相邻的栅栏有同样颜色，所以可以把题目分解一下：

设T(n)为符合要求的染色可能总数，S(n)为最后两个相邻元素为相同颜色的染色可能数，D(n)为最后两个相邻元素为不同颜色的染色可能数。
显然D(n) = (k - 1) * (S(n-1) + D(n-1))
S(n) = D(n-1)
T(n) = S(n) + D(n)
带入化简一下得出：
T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2

其实可以有更简单的方法，涂到第 n 个的可能总数为 ① 与 n-1 时的不同可能数，即(k-1)*T(n-1)；加上 ② 与 n-1 时的相同可能数，因为连续相同不能超过两个，第 n 和 n-1 个的颜色和第 n-2 个肯定不同，所以与 n-1 时的相同数必定等于 n-2 时的不同可能数，即(k-1)*T(n-2) ，于是有：

T(n) = (k - 1) * (T(n-1) + T(n-2)), n > 2

int num_colors(int n, int k) {
if(n<=0 || k<=0) return 0;
vector<int> f = {0, k, k*k};
f.resize(n+1);
for(int i=3; i<=n; i++) {
f[i] = (k-1) * (f[i-1] + f[i-2]);
}
return f[n];
}

http://www.fgdsb.com/2015/01/04/fence-painter/
http://www.cnblogs.com/jcliBlogger/p/4783051.html
https://leetcode.com/discuss/56146/dynamic-programming-c-o-n-time-o-1-space-0ms

Need two one-dimensional array dp1 and dp2, dp1[i] means the number of solutions when the color of last two fences (whose indexes are i-1,i-2) are same. dp2[i] means the number of solutions when the color of last two fences are different.

dp1[i]=dp2[i-1],

dp2[i]=(k-1)(dp1[i-1]+dp2[i-1]) =(k-1)(dp2[i-2]+dp2[i-1])

Final result is dp1[n-1]+dp2[n-1];

In the code, variable a,c mean the last two items of dp1, variable b,d mean the last two items of dp2, and c could be eliminated.

int numWays(int n, int k) { if(n<=1 || k==0)return n*k; int a=k,b=k*(k-1),c=0,d=0; for(int i=2;i<n;++i){ d=(k-1)*(a+b); a=b;b=d; } return a+b; }
http://shibaili.blogspot.com/2015/09/day-124-271-encode-and-decode-strings.html
在[i]点总paint的方法为在该点paint跟之前的同色 + 在该点paint跟之前的不同色
与之前的同色 = 在[i - 1]点的不同色的方法
与之前的不同色 = 在[i - 1]点的总paint方法 * (k - 1)

    int numWays(int n, int k) {

        if (n == 0) return 0;

        if (n == 1) return k;

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

        for (int i = 2; i < n; i++) {

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

            same = diff;

            diff = temp;

}

        return diff + same;

}

http://likemyblogger.blogspot.com/2015/09/leetcode-276-paint-fence.html
Read full article from Google Interview - Fence Painter - 我的博客 - ITeye技术网站

LeetCode 276 - Fence Painter

Labels

Popular Posts