第三十一章:带通配符的字符串匹配问题 - Art Of Programming-July


https://github.com/tdoly/The-Art-Of-Programming-by-July/blob/master/ebook/zh/31.0.md
https://github.com/julycoding/The-Art-Of-Programming-By-July

Related: Wildcard Matching, Leetcode
字符串匹配问题,给定一串字符串,按照指定规则对其进行匹配,并将匹配的结果保存至output数组中,多个匹配项用空格间隔,最后一个不需要空格。
要求:
  1. 匹配规则中包含通配符?和*,其中?表示匹配任意一个字符,*表示匹配任意多个(>=0)字符。
  2. 匹配规则要求匹配最大的字符子串,例如a*d,匹配abbdd而非abbd,即最大匹配子串。
  3. 匹配后的输入串不再进行匹配,从当前匹配后的字符串重新匹配其他字符串。
请实现函数:
    char* my_find(char input[], char rule[])
举例说明:
31.1.jpg
注意事项:
1. 自行实现函数my_find,勿在my_find函数里夹杂输出,且不准用C、C++库,和Java的String对象;
2. 请注意代码的时间,空间复杂度,及可读性,简洁性;
3. input=aaa,rule=aa时,返回一个结果aa,即可。
1. 本题与上述第三十章的题不同,上题字符串转换成整数更多考察对思维的全面性和对细节的处理,本题则更多的是编程技巧。闲不多说,直接上代码:
//copyright@cao_peng 2013/4/23  
int str_len(char *a) {  //字符串长度  
    if (a == 0) {  
        return 0;  
    }  
    char *t = a;  
    for (;*t;++t)  
        ;  
    return (int) (t - a);  
}  

void str_copy(char *a,const char *b,int len) {  //拷贝字符串 a = b  
    for (;len > 0; --len, ++b,++a) {  
        *a = *b;  
    }  
    *a = 0;  
}  

char *str_join(char *a,const char *b,int lenb) { //连接字符串 第一个字符串被回收  
    char *t;  
    if (a == 0) {  
        t = (char *) malloc(sizeof(char) * (lenb + 1));   
        str_copy(t, b, lenb);  
        return t;  
    }  
    else {  
        int lena = str_len(a);  
        t = (char *) malloc(sizeof(char) * (lena + lenb + 2));  
        str_copy(t, a, lena);  
        *(t + lena) = ' ';  
        str_copy(t + lena + 1, b, lenb);  
        free(a);  
        return t;  
    }  
}  

int canMatch(char *input, char *rule) { // 返回最长匹配长度 -1表示不匹配   
    if (*rule == 0) { //已经到rule尾端  
        return 0;  
    }  
    int r = -1 ,may;  
    if (*rule == '*') {  
        r = canMatch(input, rule + 1);  // *匹配0个字符  
        if (*input) {  
            may = canMatch(input + 1, rule);  // *匹配非0个字符  
            if ((may >= 0) && (++may > r)) {  
                r = may;  
            }  
        }  
    }  
    if (*input == 0) {  //到尾端  
        return r;  
    }  
    if ((*rule == '?') || (*rule == *input)) {  
        may = canMatch(input + 1, rule + 1);  
        if ((may >= 0) && (++may > r)) {  
            r = may;  
        }  
    }  
    return r;  
}  

char * my_find(char input[], char rule[]) {  
    int len = str_len(input);  
    int *match = (int *) malloc(sizeof(int) * len);  //input第i位最多能匹配多少位 匹配不上是-1  
    int i,max_pos = - 1;  
    char *output = 0;  

    for (i = 0; i < len; ++i) {  
        match[i] = canMatch(input + i, rule);  
        if ((max_pos < 0) || (match[i] > match[max_pos])) {  
            max_pos = i;  
        }  
    }  
    if ((max_pos < 0) || (match[max_pos] <= 0)) {  //不匹配  
        output = (char *) malloc(sizeof(char));  
        *output = 0;   // \0  
        return output;  
    }  
    for (i = 0; i < len;) {  
        if (match[i] == match[max_pos]) { //找到匹配  
            output = str_join(output, input + i, match[i]);  
            i += match[i];  
        }  
        else {  
            ++i;  
        }  
    }  
    free(match);  
    return output;  
}  
2. 本题也可以直接写出DP(Dynamic Programming, 动态规划)方程,如下代码所示:
//copyright@chpeih 2013/4/23  
char* my_find(char input[], char rule[])  
{  
    //write your code here  
    int len1, len2;  
    for(len1 = 0; input[len1]; len1++);  
    for(len2 = 0; rule[len2]; len2++);  
    int MAXN = len1 > len2 ? (len1+1) : (len2+1);  
    int  **dp;  

    //dp[i][j]表示字符串1和字符串2分别以i j结尾匹配的最大长度  
    //记录dp[i][j]是由之前那个节点推算过来  i*MAXN+j  
    dp = new int *[len1+1];  
    for (int i = 0;i<=len1;i++)  
    {  
        dp[i] = new int[len2+1];  

    }  

    dp[0][0] = 0;  
    for(int i = 1; i <= len2; i++)  
        dp[0][i] = -1;  
    for(int i = 1; i <= len1; i++)  
        dp[i][0] = 0;  

    for (int i = 1; i <= len1; i++)  
    {  
        for (int j = 1; j <= len2; j++)  
        {  
            if(rule[j-1] == '*'){  
                dp[i][j] = -1;  
                if (dp[i-1][j-1] != -1)  
                {  
                    dp[i][j] = dp[i-1][j-1] + 1;  

                }  
                if (dp[i-1][j] != -1 && dp[i][j] < dp[i-1][j] + 1)  
                {  
                    dp[i][j] = dp[i-1][j] + 1;  

                }  
            }else if (rule[j-1] == '?')  
            {  
                if(dp[i-1][j-1] != -1){  
                    dp[i][j] = dp[i-1][j-1] + 1;  

                }else dp[i][j] = -1;  
            }   
            else  
            {  
                if(dp[i-1][j-1] != -1 && input[i-1] == rule[j-1]){  
                    dp[i][j] = dp[i-1][j-1] + 1;  
                }else dp[i][j] = -1;  
            }  
        }  
    }  

    int m = -1;//记录最大字符串长度  
    int *ans = new int[len1];  
    int count_ans = 0;//记录答案个数  
    char *returnans = new char[len1+1];  
    int count = 0;  
    for(int i = 1; i <= len1; i++)  
        if (dp[i][len2] > m){  
            m = dp[i][len2];  
            count_ans = 0;  
            ans[count_ans++] = i-m;  
        }else if(dp[i][len2] != -1 && dp[i][len2] == m){  
            ans[count_ans++] = i-m;  
        }  

        if (count_ans!=0)  
        {      
            int len = ans[0];  
            for (int i = 0;i < m;i++)  
            {  
                printf("%c",input[i+ans[0]]);  
                returnans[count++] = input[i+ans[0]];  
            }  
            for (int j = 1;j<count_ans;j++)  
            {  
                printf(" ");  
                returnans[count++] = ' ';  
                len = ans[j];  
                for (int i = 0;i<m;i++)  
                {  
                    printf("%c",input[i+ans[j]]);  
                    returnans[count++] = input[i+ans[j]];  
                }  
            }  
            printf("\n");  
            returnans[count++] = '\0';  
        }  

        return returnans;  
}  

第三十三章:木块砌墙 - Art Of Programming-July


https://github.com/tdoly/The-Art-Of-Programming-by-July/blob/master/ebook/zh/33.0.md


题目:用 1×1×1, 1× 2×1以及2×1×1的三种木块(横绿竖蓝,且绿蓝长度均为2),
搭建高长宽分别为K × 2^N × 1的墙,不能翻转、旋转(其中,0<=N<=1024,1<=K<=4)
有多少种方案,输出结果
对1000000007取模。
举个例子如给定高度和长度:N=1 K=2,则答案是7,即有7种搭法,如下图所示:
详解:此题很有意思,涉及的知识点也比较多,包括动态规划,快速矩阵幂,状态压缩,排列组合等等都一一考察了个遍。而且跟一个比较经典的矩阵乘法问题类似:即用1 x 2的多米诺骨牌填满M x N的矩形有多少种方案,M<=5,N<2^31,输出答案mod p的结果
OK,回到正题。下文使用的图示说明(所有看到的都是横切面):
首先说明“?方块”的作用
“?方块”,表示这个位置是空位置,可以任意摆放。
上图的意思就是,当右上角被绿色木块占用,此位置固定不变,其他位置任意摆放,在这种情况下的堆放方案数。

解法一、穷举遍历

初看此题,你可能最先想到的思路便是穷举:用二维数组模拟墙,从左下角开始摆放,从左往右,从下往上,最后一个格子是右上角那个位置;每个格子把每种可以摆放木块都摆放一次,每堆满一次算一种用摆放方法。为了便于描述,为木块的每个格子进行编号:
下面演示当n=1,k=2的算法过程(7种情况):
穷举遍历在数据规模比较小的情况下还撑得住,但在0<=N<=1024这样的数据规模下,此方法则立刻变得有心无力,因此我们得寻找更优化的解法。

解法二、递归分解

递归求解就是把一个大问题,分解成小问题,逐个求解,然后再解决大问题。

2.1、算法演示

假如有墙规模为(n,k),如果从中间切开,被分为规模问(n-1,k)的两堵墙,那么被分开的墙和原墙有什么关系呢?我们首先来看一下几组演示。
2.1.1、n=1,k=2的情况
首先演示,n=1,k=2时的情况,如下图2-1:
图 2-1
上图2-1中:
 表示,左边墙的所有堆放方案数 * 右边墙所有堆放方案数 = 2 * 2 = 4
 表示,当切开处有一个横条的时候,空位置存在的堆放方案数。左边右边 = 11 = 2;剩余两组以此类推。
这个是排列组合的知识。
2.1.2、n=2,k=3的情况
其次,我们再来演示下面更具一般性的计算分解,即当n=2,k=3的情况,如下图2-2:
图 2-2
再从分解的结果中,挑选一组进行分解演示:
图 2-3
通过图2-2和图2-3的分解演示,可以说明,最终都是分解成一列求解。在逐级向上汇总。
2.1.3、n=4,k=3的情况
我们再假设一堵墙n=4,k=3,也就是说,宽度是16,高度是3时,会有以下分解:
图2-4
根据上面的分解的一个中间结果,再进行分解,如下:
图2-5
通过上面图2-1~图2-5的演示可以明确如下几点:
1.假设f(n)用于计算问题,那么f(n)依赖于f(n-1)的多种情况。
2.切开处有什么特殊的地方呢?通过上面的演示,我们得知被切开的两堵墙从没有互相嵌入的木块(绿色木块)到全是互相连接的木块,相当于切口绿色木块的全排列(即有绿色或者没有绿色的所有排列),即有2^k种状态(比如k=2,且有绿色用1表示,没有绿色用0表示,那么就有00、01、10、11这4种状态)。根据排列组合的性质,把每一种状态下左右木墙堆放方案数相乘,再把所有乘积求和,就得到木墙的堆放结果数。以此类推,将问题逐步往下分解即可。
3.此外,从图2-5中可以看出,除了需要考虑切口绿色木块的状态,还需要考虑最左边一列和最右边一列的绿色木块状态。我们把这两种边界状态称为左边界状态和右边界状态,分别用leftState和rightState表示。
且在观察图2-5被切分后,所有左边的墙,他们的左边界ls状态始终保持不变,右边界rs状态从0~maxState, maxState = 2^k-1(有绿色方块表示1,没有表示0;ls表示左边界状态,rs表示右边状态):
图2-6
同样可以看出右边的墙的右边界状态保持不变,而左边界状态从0~maxState。要堆砌的木墙可以看做是左边界状态=0,和右边界状态=0的一堵墙。
有一点可能要特别说明下,即上文中说,有绿色方块的状态表示标为1,无绿色方块的状态表示标为0,特意又拿上图2-6标记了一些数字,以让绝大部分读者能看得一目了然,如下所示:
图2-7
这下,你应该很清楚的看到,在上图中,左边木块的状态表示一律为010,右边木块的状态表示则是000~111(即从下至上开始计数,右边木块rs的状态用二进制表示为:000 001 010 011 100 101 110 111,它们各自分别对应整数则是:0 1 2 3 4 5 6 7)。

2.2、计算公式

通过图2-4、图2-5、图2-6的分解过程,我们可以总结出下面公式(leftState=最左边边界状态,rightState=最右边边界状态):
即:
接下来,分3点解释下上述公式:
1、上述函数返回结果是当左边状态为=leftState,右边状态=rightState时木墙的堆砌方案数,相当于直接分解的左右状态都为0的情况,即直接分解f(n,k,0,0)即可。看到这,读者可能便有疑问了,既然直接分解f(n,k,0,0)即可,为何还要加leftstate和leftstate两个变量呢?回顾下2.1.3节中n=4,k=3的演示例子,即当n=4,k=3时,其分解过程即如下图(上文2.1.3节中的图2-4)
也就是说,刚开始直接分解f(4,3,0,0),即n=4,k=3,leftstate=0,rightstate=0,但分解过程中leftstate和rightstate皆从0变化到了maxstate,故才让函数的第3和第4个参数采用leftstate和rightstate这两个变量的形式,公式也就理所当然的写成了f(n,k,leftstate,rightstate)。
2、然后我们再看下当n=4,k=3分解的一个中间结果,即给定如上图最下面部分中红色框框所框住的木块时:
它用方程表示即为 f(2,3,2,5),怎么得来的呢?其实还是又回到了上文2.1.3节中,当n=2,k=3 时(下图即为上文2.1.3节中的图2-5和图2-6)
左边界ls状态始终保持不变时,右边界rs状态从0~maxState;右边界状态保持不变时,而左边界状态从0~maxState。
故上述分解过程用方程式可表示为:
f(2,3,2,5) = f(1,3,2,0) * f(1,3,0,5)
+ f(1,3,2,1) * f(1,3,1,5)
+ f(1,3,2,2) * f(1,3,2,5)
+ f(1,3,2,3) * f(1,3,3,5)
+ f(1,3,2,4) * f(1,3,4,5)
+ f(1,3,2,5) * f(1,3,5,5)
+ f(1,3,2,6) * f(1,3,6,5)
+ f(1,3,2,7) * f(1,3,7,5)
说白了,我们曾在2.1节中从图2-2到图2-6正推推导出了公式,然上述过程中,则又再倒推推了一遍公式进行了说明。
3、最后,作者是怎么想到引入 leftstate 和rightstate 这两个变量的呢?如红色标记所说:"因为切开后,发现绿色条,在分开出不断的变化,当时也进入了死胡同,我就在想,蓝色的怎么办。后来才想明白,与蓝色无关。每一种变化就是一种状态,所以就想到了引入leftstate 和rightstate这两个变量。"

2.3、参考代码

下面代码就是根据上面函数原理编写的。最终执行效率,n=1024,k=4 时,用时0.2800160秒(之前代码用的是字典作为缓存,用时在1.3秒左右,后来改为数组结果,性能大增)。""
//copyright@红色标记 12/8/2013    
//updated@July 13/8/2013  
using System;    
using System.Collections.Generic;    
using System.Text;    
using System.Collections;    

namespace HeapBlock    
{    
    public class WoolWall    
    {            
        private int n;    
        private int height;    
        private int maxState;    
        private int[, ,] resultCache;   //结果缓存数组    

        public WoolWall(int n, int height)    
        {    
            this.n = n;    
            this.height = height;    
            maxState = (1 << height) - 1;    
            resultCache = new int[n + 1, maxState + 1, maxState + 1];   //构建缓存数组,每个值默认为0;    
        }    

        /// <summary>    
        /// 静态入口。计算堆放方案数。    
        /// </summary>    
        /// <param name="n"></param>    
        /// <param name="k"></param>    
        /// <returns></returns>    
        public static int Heap(int n, int k)    
        {    
            return new WoolWall(n, k).Heap();    
        }    

        /// <summary>    
        /// 计算堆放方案数。    
        /// </summary>    
        /// <returns></returns>    
        public int Heap()    
        {    
            return (int)Heap(n, 0, 0);    
        }    

        private long Heap(int n, int lState, int rState)    
        {    
            //如果缓存数组中的值不为0,则表示该结果已经存在缓存中。    
            //直接返回缓存结果。    
            if (resultCache[n, lState, rState] != 0)    
            {    
                return resultCache[n, lState, rState];    
            }    

            //在只有一列的情况,无法再进行切分    
            //根据列状态计算一列的堆放方案    
            if (n == 0)    
            {    
                return CalcOneColumnHeapCount(lState);    
            }    

            long result = 0;    
            for (int state = 0; state <= maxState; state++)    
            {    
                if (n == 1)    
                {    
                    //在只有两列的情况,判断当前状态在切分之后是否有效    
                    if (!StateIsAvailable(n, lState, rState, state))    
                    {    
                        continue;    
                    }    
                    result += Heap(n - 1, state | lState, state | lState)  //合并状态。因为只有一列,所以lState和rState相同。    
                        * Heap(n - 1, state | rState, state | rState);    
                }    
                else    
                {    
                    result += Heap(n - 1, lState, state) * Heap(n - 1, state, rState);     
                }    
                result %= 1000000007;//为了防止结果溢出,根据题目要求求模。    
            }    

            resultCache[n, lState, rState] = (int)result;   //将结果写入缓存数组中    
            resultCache[n, rState, lState] = (int)result;   //对称的墙结果相同,所以直接写入缓存。    
            return result;    
        }    

        /// <summary>    
        /// 根据一列的状态,计算列的堆放方案数。    
        /// </summary>    
        /// <param name="state">状态</param>    
        /// <returns></returns>    
        private int CalcOneColumnHeapCount(int state)    
        {    
            int sn = 0; //连续计数    
            int result = 1;    
            for (int i = 0; i < height; i++)    
            {    
                if ((state & 1) == 0)    
                {    
                    sn++;    
                }    
                else    
                {    
                    if (sn > 0)    
                    {    
                        result *= CalcAllState(sn);    
                    }    
                    sn = 0;    
                }    
                state >>= 1;    
            }    
            if (sn > 0)    
            {    
                result *= CalcAllState(sn);    
            }    

            return result;    
        }    

        /// <summary>    
        /// 类似于斐波那契序列。    
        /// f(1)=1    
        /// f(2)=2    
        /// f(n) = f(n-1)*f(n-2);    
        /// 只是初始值不同。    
        /// </summary>    
        /// <param name="k"></param>    
        /// <returns></returns>    
        private static int CalcAllState(int k)    
        {    
            return k <= 2 ? k : CalcAllState(k - 1) + CalcAllState(k - 2);    
        }    

        /// <summary>    
        /// 判断状态是否可用。    
        /// 当n=1时,分割之后,左墙和右边墙只有一列。    
        /// 所以state的状态码可能会覆盖原来的边缘状态。    
        /// 如果有覆盖,则该状态不可用;没有覆盖则可用。    
        /// 当n>1时,不存在这种情况,都返回状态可用。    
        /// </summary>    
        /// <param name="n"></param>    
        /// <param name="lState">左边界状态</param>    
        /// <param name="rState">右边界状态</param>    
        /// <param name="state">切开位置的当前状态</param>    
        /// <returns>状态有效返回 true,状态不可用返回 false</returns>    
        private bool StateIsAvailable(int n, int lState, int rState, int state)    
        {    
            return (n > 1) || ((lState | state) == lState + state && (rState | state) == rState + state);    
        }    
    }    
}    
上述程序中,
  • WoolWall.Heap(1024,4); //直接通过静态方法获得结果
  • new WoolWall(n, k).Heap();//通过构造对象获得结果
2.3.1、核心算法讲解
因为它最终都是分解成一列的情况进行处理,这就会导致很慢。为了提高速度,本文使用了缓存机制来提高性能。缓存原理就是,n,k,leftState,rightState相同的墙,返回的结果肯定相同。利用这个特性,每计算一种结果就放入到缓存中,如果下次计算直接从缓存取出。刚开始缓存用字典类实现,有网友给出了更好的缓存方法——数组。这样性能好了很多,也更加简单。程序结构如下图所示:
上图反应了Heep调用的主要方法调用,在循环中,result 累加 lResult 和 rResult。
①在实际代码中,首先是从缓存中读取结果,如果没有缓存中读取结果在进行计算。
分解法分解到一列时,不在分解,直接计算机过
if (n == 0)  
{  
     return CalcOneColumnHeap(lState);  
} 
②下面是整个程序的核心代码,通过for循环,求和state=0到state=2^k-1的两边木墙乘积:
for (int state = 0; state <= maxState; state++)  
{  
    if (n == 1)  
    {  
        if (!StateIsAvailable(n, lState, rState, state))  
        {  
            continue;  
        }  
        result += Heap(n - 1, state | lState, state | lState) *  
            Heap(n - 1, state | rState, state | rState);  
    }  
    else  
    {  
        result += Heap(n - 1, lState, state)  
            * Heap(n - 1, state, rState);  
    }  
    result %= 1000000007;  
}  
当n=1切分时,需要特殊考虑。如下图:
图2-8
看上图中,因为左边墙中间被绿色方块占用,所以在(1,0)-(1,1)这个位置(位置的标记方法同解法一)不能再放绿色方块。所以一些状态需要排除,如state=2需要排除。同时在还需要合并状态,如state=1时,左边墙的状态=3。
特别说明下:依据我们上文2.2节中的公式,如果第i行有这种木块,state对应2^(i-1),加上所有行的贡献就得到state(0就是没有这种横跨木块,2^k-1就是所有行都是横跨木块),然后遍历state,还记得上文中的图2-7么?
当第i行被这样的木块或这样的木块占据时,其各自对应的state值分别为:
1.当第1行被占据,state=1;
2.当第2行被占据,state=2;
3.当第1和第2行都被占据,state=3;
4.当第3行被占据,state=4;
5.当第1和第3行被占据,state=5;
6.当第2和第3行被占据,state=6;
7.当第1、2、3行全部都被占据,state=7。
至于原因,即如2.1.3节节末所说:二进制表示为:000 001 010 011 100 101 110 111,它们各自分别对应整数则是:0 1 2 3 4 5 6 7。
具体来说,下面图中所有框出来的位置,不能有绿色的:
③CalcOneColumnHeap(int state)函数用于计算一列时摆放方案数。
计算方法是, 求和被绿色木块分割开的每一段连续方格的摆放方案数。每一段连续的方格的摆放方案通过CalcAllState方法求得。经过分析,可以得知CalcAllState是类似斐波那契序列的函数。
举个例子如下(分步骤讲述):
1.令state = 4546(state=2^k-1,k最大为4,故本题中state最大在15,而这里取state=4546只是为了演示如何计算),二进制是:1000111000010。位置上为1,表示被绿色木块占用,0表示空着,可以自由摆放。
2.1000111000010 被分割后 1 000 111 0000 1 0, 那么就有 000=3个连续位置, 0000=4个连续位置 , 0=1个连续位置。
3.堆放结果=CalcAllState(3) + CalcAllState(4) + CalcAllState(1) = 3 + 5 + 1 = 9。

2.4、再次优化

上面程序因为调用性能的树形结构,形成了大量的函数调用和缓存查找,所以其性能不是很高。 为了得到更高的性能,可以让所有的运算直接依赖于上一次运算的结果,以防止更多的调用。即如果每次运算都算出所有边界状态的结果,那么就能为下一次运算提供足够的信息。后续优化请查阅此文第3节:http://blog.csdn.net/dw14132124/article/details/9038417#t2

解法三、动态规划

相信读到上文,不少读者都已经意识到这个问题其实就是一个动态规划问题,接下来咱们换一个角度来分析此问题。

3.1、暴力搜索不可行

首先,因为木块的宽度都是1,我们可以想成2维的问题。也就是说三种木板的规格分别为1* 1, 1 * 2, 2 * 1。
通过上文的解法一,我们已经知道这个问题最直接的想法就是暴力搜索,即对每个空格尝试放置哪种木板。但是看看数据规模就知道,这种思路是不可行的。因为有一条边范围长度高达21024,普通的电脑,230左右就到极限了。于是我们得想想别的方法。

3.2、另辟蹊径

为了方便,我们把墙看做有2n行,k列的矩形。这是因为虽然矩形木块不能翻转,但是我们同时拥有12和21的两种木块。
假设我们从上到下,从左到右考虑每个1*1的格子是如何被覆盖的。显然,我们每个格子都要被覆盖住。木块的特点决定了我们覆盖一个格子最多只会影响到下一行的格子。这就可以让我们暂时只考虑两行。
假设现我们已经完全覆盖了前(i– 1)行。那么由于覆盖前(i-1)行导致第i行也不“完整”了。如下图:
xxxxxxxxx
ooxooxoxo
我们用x表示已经覆盖的格子,o表示没覆盖的格子。为了方便,我们使用9列。
我们考虑第i行的状态,上图中,第1列我们可以用11的覆盖掉,也可以用12的覆盖前两列。第4、5列的覆盖方式和第1、2列是同样的情况。第7列需要覆盖也有两种方式,即用11的覆盖或者用21的覆盖,但是这样会导致第(i+1)行第7列也被覆盖。第9列和第7列的情况是一样的。这样把第i行覆盖满了之后,我们再根据第(i+1)行被影响的状态对下一行进行覆盖。
那么每行有多少种状态呢?显然有2k,由于k很小,我们只有大约16种状态。如果我们对于这些状态之间的转换制作一个矩阵,矩阵的第i行第j列的数表示的是我们第m行是状态i,我们把它完整覆盖掉,并且使得第(m + 1)行变成状态j的可能的方法数,这个矩阵我们可以暴力搜索出来,搜索的方式就是枚举第m行的状态,然后尝试放木板,用所有的方法把第m行覆盖掉之后,下一行的状态。当然,我们也可以认为只有两行,并且第一行是2k种状态的一种,第二行起初是空白的,求使得第一行完全覆盖掉,第二行的状态有多少种类型以及每种出现多少次。

3.3、动态规划

这个矩阵作用很大,其实我们覆盖的过程可以认为是这样:第一行是空的,我们看看把它覆盖了,第2行是什么样子的。根据第二行的状态,我们把它覆盖掉,看看第3行是什么样子的。
如果我们知道第i行的状态为s,怎么考虑第i行完全覆盖后,第(i+1)行的状态?那只要看那个矩阵的状态s对应的行就可以了。我们可以考虑一下,把两个这样的方阵相乘得到得结果是什么。这个方阵的第i行第j个元素是这样得到的,是第i行第k个元素与第k行第j个元素的对k的叠加。它的意义是上一行是第m行是状态i,把第m行和第(m+ 1)行同时覆盖住,第(m+2)行的状态是j的方法数。这是因为中间第(m+1)行的所有状态k,我们已经完全遍历了。
于是我们发现,每做一次方阵的乘法,我们相当于把状态推动了一行。那么我们要坐多少次方阵乘法呢?就是题目中墙的长度2n,这个数太大了。但是事实上,我们可以不断地平方n次。也就是说我们可以算出A2,A4, A8, A16……方法就是不断用结果和自己相乘,这样乘n次就可以了。
因此,我们最关键的问题就是建立矩阵A。我们可以这样表示一行的状态,从左到右分别叫做第0列,第1列……覆盖了我们认为是1,没覆盖我们认为是0,这样一行的状态可以表示维一个整数。某一列的状态我们可以用为运算来表示。例如,状态x第i列是否被覆盖,我们只需要判断x & (1 << i) 是否非0即可,或者判断(x >> i) & 1, 用右移位的目的是防止溢出,但是本题不需要考虑溢出,因为k很小。 接下来的任务就是递归尝试放置方案了

3.4、参考代码

最终结果,我们最初的行是空得,要求最后一行之后也不能被覆盖,所以最终结果是矩阵的第[0][0]位置的元素。另外,本题在乘法过程中会超出32位int的表示范围,需要临时用C/C++的long long,或者java的long。
参考代码如下:
//copyright@caopengcs 12/08/2013  
#ifdef WIN32  
#define ll __int64   
#else  
#define ll long long  
#endif  

// 1 covered 0 uncovered  

void cal(int a[6][32][32],int n,int col,int laststate,int nowstate) {  
    if (col >= n) {  
        ++a[n][laststate][nowstate];  
        return;  
    }  
    //不填 或者用1*1的填  
    cal(a,n, col + 1, laststate, nowstate);  
    if (((laststate >> col) & 1) == 0) {  
        cal(a,n, col + 1, laststate, nowstate | (1 << col));  
        if ((col + 1 < n) && (((laststate >> (col + 1)) & 1) == 0)) {  
            cal(a,n, col + 2, laststate, nowstate);  
        }  
    }  
}  

inline int mul(ll x, ll y) {  
    return x * y % 1000000007;  
}  

void multiply(int n,int a[][32],int b[][32]) { // b = a * a  
    int i,j, k;  
    for (i = 0; i < n; ++i) {  
        for (j = 0; j < n; ++j) {  
            for (k = b[i][j] = 0; k < n; ++k) {  
                if ((b[i][j] += mul(a[i][k],a[k][j])) >= 1000000007) {  
                    b[i][j] -= 1000000007;  
                }  
            }  
        }  
    }  
}  

int calculate(int n,int k) {  
    int i, j;  
    int a[6][32][32],mat[2][32][32];  
    memset(a,0,sizeof(a));  
    for (i = 1; i <= 5; ++i) {  
        for (j = (1 << i) - 1; j >= 0; --j) {  
            cal(a,i, 0, j, 0);  
        }  
    }  
    memcpy(mat[0], a[k],sizeof(mat[0]));  
    k = (1 << k);  
    for (i = 0; n; --n) {  
        multiply(k, mat[i], mat[i ^ 1]);  
        i ^= 1;  
    }  
    return mat[i][0][0];  
}  

参考链接及推荐阅读

  1. caopengcs,木块砌墙:http://blog.csdn.net/caopengcs/article/details/9928061
  2. 红色标记,木块砌墙:http://blog.csdn.net/dw14132124/article/details/9038417
  3. LoveHarvy,木块砌墙:http://blog.csdn.net/wangyan_boy/article/details/9131501
  4. 在线编译测试木块砌墙问题:http://hero.pongo.cn/Question/Details?ID=36&ExamID=36
  5. hero上木块砌墙一题:http://hero.pongo.cn/Question/Details?ExamID=36&ID=36&bsh_bid=273040296

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts