Chris

单调队列 POJ2823

chris — Fri, 08 Jul 2011 15:04:25 +0800

看这个问题：An array of size n ≤ 10⁶ is given to you. There is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves rightwards by one position.Your task is to determine the maximum and minimum values in the sliding window at each position.

也就是有一个数列a，要求你求数列b和c，b[i]是a[i]…a[i+w-1]中的最小值，c[i]是最大值。如果a是1,3,-1,-3,5,3,6,7，则b为-1,-3,-3,-3,3,3，c为3,3,5,5,6,7。

这个问题相当于一个数据流（数列a）在不断地到来，而数据是不断过期的，相当于我们只能保存有限的数据（sliding window中的数据，此题中就是窗口的宽度w），对于到来的查询（此题中查询是每时刻都有的），我们要返回当前滑动窗口中的最大值\最小值。注意，元素是不断过期的。

解决这个问题可以使用一种叫做单调队列的数据结构，它维护这样一种队列：

a)从队头到队尾，元素在我们所关注的指标下是递减的（严格递减，而不是非递增），比如查询如果每次问的是窗口内的最小值，那么队列中元素从左至右就应该递增，如果每次问的是窗口内的最大值，则应该递减，依此类推。这是为了保证每次查询只需要取队头元素。

b)从队头到队尾，元素对应的时刻（此题中是该元素在数列a中的下标）是递增的，但不要求连续，这是为了保证最左面的元素总是最先过期，且每当有新元素来临的时候一定是插入队尾。

满足以上两点的队列就是单调队列，首先，只有第一个元素的序列一定是单调队列。

那么怎么维护这个单调队列呢？无非是处理插入和查询两个操作。

对于插入，由于性质b，因此来的新元素插入到队列的最后就能维持b)继续成立。但是为了维护a)的成立，即元素在我们关注的指标下递减，从队尾插入新元素的时候可能要删除队尾的一些元素，具体说来就是，找到第一个大于（在所关注指标下）新元素的元素，删除其后所有元素，并将新元素插于其后。因为所有被删除的元素都比新元素要小，而且比新元素要旧，因此在以后的任何查询中都不可能成为答案，所以可以放心删除。

对于查询，由于性质b，因此所有该时刻过期的元素一定都集中在队头，因此利用查询的时机删除队头所有过期的元素，在不含过期元素后，队头得元素就是查询的答案（性质a），将其返回即可。

由于每个元素都进队出队一次，因此摊销复杂度为O(n)。

POJ2823就是上面描述的那道题。

下面是代码，很无聊的是这道题竟然卡scanf和printf，如果用cin,cout就会超时，觉得有点无聊。

   1:  #include <iostream>

   2:  #include <vector>

3:

   4:  using namespace std;

5:

   6:  struct elem

   7:  {

   8:      int v;

   9:      int p;

  10:  };

11:

  12:  int main()

  13:  {

  14:      int l,w;

  15:      cin>>l>>w;

16:

  17:      elem* q1 = new elem[l+w];

  18:      elem* q2 = new elem[l+w];

19:

  20:      int num,max;

21:

  22:      int head1 = 0,tail1 = 0;

  23:      int head2 = 0,tail2 = 0;

  24:      cin>>num;

  25:      q1[tail1].v = num;

  26:      q1[tail1].p = 0;

27:

  28:      q2[tail2].v = num;

  29:      q2[tail2].p = 0;

30:

  31:      vector<int> ans1,ans2;

32:

  33:      for (int t = 1;t < w;t++)

  34:      {

  35:          scanf("%d",&num);

36:

  37:          while (head1 <= tail1 && q1[tail1].v >= num)

  38:              --tail1;

  39:          q1[++tail1].v = num;

  40:          q1[tail1].p = t;

41:

  42:          while (head2 <= tail2 && q2[tail2].v <= num)

  43:              --tail2;

  44:          q2[++tail2].v = num;

  45:          q2[tail2].p = t;

  46:      }

47:

  48:      ans1.push_back(q1[head1].v);

  49:      ans2.push_back(q2[head2].v);

50:

  51:      for (int t = w;t < l;t++)

  52:      {

  53:          scanf("%d",&num);

54:

  55:          {

56:

  57:              while (head1 <= tail1 && q1[tail1].v >= num)

  58:                  --tail1;

  59:              q1[++tail1].v = num;

  60:              q1[tail1].p = t;

61:

  62:              while (t - q1[head1].p >= w)

  63:                  ++head1;

64:

  65:              ans1.push_back(q1[head1].v);

  66:          }

67:

  68:          {

  69:              while (head2 <= tail2 && q2[tail2].v <= num)

  70:                  --tail2;

  71:              q2[++tail2].v = num;

  72:              q2[tail2].p = t;

73:

  74:              while (t - q2[head2].p >= w)

  75:                  ++head2;

76:

  77:              ans2.push_back(q2[head2].v);

  78:          }

  79:      }

80:

  81:      delete []q1;

  82:      delete []q2;

83:

  84:      for (vector<int>::iterator it = ans1.begin();it != ans1.end();it++)

  85:      {

  86:          printf("%d",*it);

  87:          if (it != ans1.end()-1)

  88:              printf(" ");

  89:          else

  90:              printf("\n");

  91:      }

92:

  93:      for (vector<int>::iterator it = ans2.begin();it != ans2.end();it++)

  94:      {

  95:          printf("%d",*it);

  96:          if (it != ans2.end()-1)

  97:              printf(" ");

  98:          else

  99:              printf("\n");

 100:      }

 101:  }

Windows和Linux下进程、线程理解

chris — Mon, 20 Jun 2011 14:03:05 +0800

对于windows来说，进程和线程的概念都是有着明确定义的，进程的概念对应于一个程序的运行实例(instance)，而线程则是程序代码执行的最小单元。也就是说windows对于进程和线程的定义是与经典OS课程中所教授的进程、线程概念相一致的。

提供API，CreateThread()用于建立一个新的线程，传递线程函数的入口地址和调用参数给新建的线程，然后新线程就开始执行了。

windows下，一个典型的线程拥有自己的堆栈、寄存器（包括程序计数器PC，用于指向下一条应该执行的指令在内存中的位置），而代码段、数据段、打开文件这些进程级资源是同一进程内多个线程所共享的。因此同一进程的不同线程可以很方便的通过全局变量（数据段）进行通信，大家都可以对数据段进行读写，这很方便，也被在安全性方面诟病，因为它要求程序员时刻意识到这些数据不是线程独立的。

对于linux来说，则没有很明确的进程、线程概念。首先linux只有进程而没有线程，然而它的进程又可以表现得像windows下的线程。linux利用fork()和exec函数族来操作多线程。fork()函数可以在进程执行的任何阶段被调用，一旦调用，当前进程就被分叉成两个进程——父进程和子进程，两者拥有相同的代码段和暂时相同的数据段（虽然暂时相同，但从分叉开的时刻就是逻辑上的两个数据段了，之所以说是逻辑上的，是因为这里是“写时复制”机制，也就是，除非万不得已有一个进程对数据段进行了写操作，否则系统不去复制数据段，这样达到了负担最小），两者的区别在于fork()函数返回值，对于子进程来说返回为0，对于父进程来说返回的是子进程id，因此可以通过if(fork()==0)…else…来让父子进程执行不同的代码段，从而实现“分叉”。

exec函数族的函数的作用则是启动另一个程序的新进程，然后完全用那个进程来代替自己（代码段被替换，数据段和堆栈被废弃，只保留原有进程id）。这样，如果在fork()之后，在子进程代码段里用exec启动另一个进程，就相当于windows下的CreateThread()的用处了，所以说linux下的进程可以表现得像windows下的线程。

然而linux下的进程不能像windows下线程那样方便地通信，因为他们没有共享数据段、地址空间等。它们之间的通信是通过所谓IPC(InterProcess Communication)来进行的。具体有管道（无名管道用于父子进程间通信，命名管道可以用于任意两个进程间的通信）、共享内存（一个进程向系统申请一块可以被共享的内存，其它进程通过标识符取得这块内存，并将其连接到自己的地址空间中，效果上类似于windows下的多线程间的共享数据段），信号量，套接字。

=================================分割线==================================

顺便谈一下自己对于linux文化的一点小感受。据我不多的了解来说，感觉linux在很多实现的风格上过于trick，它确实总让我们有“原来还可以这样！”、“真的很巧妙啊！”的惊叹，但是其实相同的问题还可以有更加一般化、更加经典、也更加容易理解的解决方案。fork()和CreateThread()的区别就很好地体现了这点。也许是因为linux总是把效率放在第一位吧。我猜，正是因为如此，正是因为linux下的这种富tricks的风格，才让linux粉们那么容易产生优越感吧，不过这一点却不怎么吸引我，因为我觉得这些实现方法上的小trick小差异并不是我们面对的问题的实质。

编程之美 3.8 求二叉树中节点的最大距离 3.9 重建二叉树

chris — Sat, 11 Jun 2011 21:14:32 +0800

3.8 题意为：将一棵二叉树看成一个图，求树上两点之间的距离。距离定义为两点之间边的条数，如下图的二叉树中，节点8和5之间的距离为3。

3.9题意为已知二叉树的前序遍历结果和中序遍历结果，要求重建二叉树。之所以在这里说3.9，是因为解第八题的时候为了处理输入建成二叉树，实现了一个重建二叉树的函数。

代码如下（六个参数分别为前序遍历结果数组，其起点和终点；中序遍历结果数组，其起点和终点）：

node* buildTree(int* nodesPre,int s1,int e1,int* nodesIn,int s2,int e2)
{
    if (s1 > e1)
    {
        return NULL;
    }
    if (s2 > e2)
    {
        return NULL;
    }

    node* root = new node;
    root->data = nodesPre[s1];

    int lenOfLeft = 0;
    for (;s2 + lenOfLeft <= e2;lenOfLeft++)
    {
        if (nodesPre[s1] == nodesIn[s2 + lenOfLeft])
            break;
    }

    root->left = buildTree(nodesPre,s1+1,s1+lenOfLeft,nodesIn,s2,s2+lenOfLeft-1);
    root->right = buildTree(nodesPre,s1+lenOfLeft+1,e1,nodesIn,s2+lenOfLeft+1,e2);

    return root;
}

回到3.8，遍历树中的所有节点，为每个节点生成由0和1组成的串作为ID，递归定义，节点a的左孩子ID为ID(a).push_back(1)，右孩子ID为ID(a).push_back(0)。即根的ID为空串，在遍历过程中，每向左走一次，就在其父节点ID后添加一个1作为其ID，若向右则添加一个0。如图中的节点8，ID为111，即因为它可以通过从根节点连续三次向左走来到达。

有了这个ID，就可以很容易地计算两个节点之间的距离了。先给出递归遍历所有节点并计算ID的函数：

void buildMap(node* root,map<int,vector<int>>& nodesInfo)
{
    if (root->left)
    {
        vector<int> lstr = nodesInfo[root->data];
        lstr.push_back(1);
        nodesInfo[root->left->data] = lstr;
        buildMap(root->left,nodesInfo);
    }

    if (root->right)
    {
        vector<int> rstr = nodesInfo[root->data];
        rstr.push_back(0);
        nodesInfo[root->right->data] = rstr;
        buildMap(root->right,nodesInfo);
    }
}

一个点的ID表示了从根节点需要经过怎样的路径能到达它。于是，若两个点的ID开头有相同的部分，说明它们在一开始路径是一直的，即没有分离，这段路径不会增加两者的距离。忽略掉开头的相同部分后，两者ID中剩下的部分就代表了两者完全不同的路径了，将两者ID剩余部分的长度相加即得到了两者的距离。如图中的节点8和节点5，ID分别是111和10，忽略掉开头的一个1后，两者的剩余部分分别是11和0，则distance(8,5)=length(11)+length(0)=2+1=3。

计算两个节点距离的函数如下：

int findDistance(map<int,vector<int>>& nodesInfo,int i,int j)
{
    vector<int> v1 = nodesInfo[i];
    vector<int> v2 = nodesInfo[j];

    while (!v1.empty() && !v2.empty() && v1[0] == v2[0])
    {
        v1.erase(v1.begin());
        v2.erase(v2.begin());
    }

    return v1.size() + v2.size();
}

编程之美 2.4 “1”的数目

chris — Fri, 10 Jun 2011 18:17:23 +0800

题目是这样的：给定一个正整数N，从1到N一共出现过多少个1？

如N=12，则f(12)=5，因为1,2,3,4,5,6,7,8,9,10,11,12共出现5次“1”。

当年第一次看这个题的时候觉得无从下手，这次到迅速有了思路，还是有进步的嘛。

思路就是分别统计个位、十位、百位…上的1的数目。先考虑个位上的1的数目，个位上的1是每10个数中会出现1次的，即1-10出现一次，11-20出现一次…因此可以计算N/10，对于N%10的部分，只要N%10>=1，就有一个1，也只能有一个1。同理再考虑十位上的1，十位上的1是每100个数字中会出现10次，如1-100出现10次（10-19），101-200出现10次（110-119）…因此可以计算N/100*10，对于N%100的部分，只有在10-19之间会出现1，因此可以分情况讨论。百位上、千位上的情况依此类推，再举一例，说一下千位上的情况吧，对于千位上的1，是每10000个数里出现1000次，例如1-10000里出现1000次（1000-1999），10001-20000里出现1000次（11000-11999）…因此可以计算N/10000*1000，对于N%10000的部分，只有在1000-1999之间会出现千位上的1，同样分情况讨论之。

代码如下：

   1:  __int64 func(__int64 N)

   2:  {

   3:      __int64 onesCount = 0;

   4:      __int64 factor = 10;

   5:      __int64 a,b,c;

   6:      do

   7:      {

   8:          a = N/factor;

   9:          b = N%factor;

  10:          c = a*(factor/10);

11:

  12:          onesCount += c;

13:

  14:          if (b >= factor/10)

  15:          {

  16:              if (b > 2*(factor/10) - 1)

  17:              {

  18:                  onesCount += factor/10;

  19:              }

  20:              else

  21:              {

  22:                  onesCount += b - (factor/10) + 1;

  23:              }

  24:          }

  25:          factor *= 10;

  26:      } while (a != 0);

27:

  28:      return onesCount;

  29:  }

有一个有意思的现象是，对于N=111…110这样的数，即a个1加一个0组成的数，其f(N)恰好等于连续a个(a+1)，如f(1110)=444，f(11111110)=8888888。以f(1110)=444为例，一共有四位，每一位上的一都是111个，因此f(1110)=444。

扩展问题问到了对于2进制的情况该怎么解答，例如f(11)=100，因为“0,10,11”中共出现了四个1。其实思路是一样的，也是分别考察右侧第一位上出现1的次数、右侧第二位上出现1的次数…以此类推。比如考虑f(11)=f(1011),

1,10,11,100,101,110,111,1000,1001,1010,1011

先考虑第一位上的1（第几位一律从右侧数起），第一位上的1是每两个数出现一次，因此可以先计算11/2=5，然后对于11%2=1的部分，由于等于1，因此出现了一次1，因此第一位上共出现了6次1；再考虑第二位，这一位上是每4个数出现2次1，先计算11/4*2=4，对于11%4=3部分，只有在10-11之间会出现2次1，因此第二位上出现6次1；第三位，(11/8*4)+0=4次，第四位，0+(11-7)=4。因此f(1011)=10100=20。代码就不写了吧。

编程之美2.21 什么样的数不能写成连续N个自然数之和

chris — Thu, 09 Jun 2011 16:59:37 +0800

有些数可以写成连续N（>1）个自然数之和，比如14=2+3+4+5；有些不能，比如8.那么如何判断一个数是否可以写成连续N个自然数之和呢？这是这一节的基本问题。

一个数M若可以写成以a开头的连续n个自然数之和，则M=a+(a+1)+(a+2)+…+(a+n-1)=n*a+n*(n-1)/2，要求a!=0，否则就是以a+1开头的连续n-1个整数了，也就是要求(M-(n+n*(n-1)/2))%n==0，即(M-(n*(n+1)/2))%n==0，这样就很容易判断一个数可不可以写成连续n个自然数的形式了，遍历n=2…sqrt(M)*2，还可以输出所有解。

第二个问题是什么样的数可以写成连续n个自然数之和，什么样的数不能？

通过编程实验发现，除了2^n以外，其余所有数都可以写成该形式。下面说明为什么。

若数M符合条件，则有M=a+(a+1)+(a+2)+…+(a+n-1)=(2*a+n-1)*n/2，而2*a+n-1与n肯定一个为奇数一个为偶数，即M一定要有一个奇数因子，而所有2^n都没有奇数因子，因此肯定不符合条件。

再证明只有M有一个奇数因子，即M!=2^n，M就可以写成连续n个自然数之和。假设M有一个奇数因子a，则M=a*b。

1)若b也是奇数，只要b-(a-1)/2>0，M就可以写成以b-(a-1)/2开头的连续a个自然数；将这条结论里的a和b调换，仍然成立。15=3*5=1+2+3+4+5=4+5+6.

2)若b是偶数，则我们有一个奇数a和一个偶数b。

2.1)若b-(a-1)/2>0，M就可以写成以b-(a-1)/2开头的连续a个自然数。24=3*8=7+8+9.

2.2)若(a+1)/2-b>0，M就可以写成以(a+1)/2-b开头的连续2*b个自然数。38=19*2=8+9+10+11.

上述两个不等式必然至少有一个成立，所以可以证明，只要M有一个奇数因子，就一定可以写成连续n个自然数之和。

第三个问题是，在64位整数范围内，能写成最多种连续n个自然数之和的数是哪个？

对于数M，考察其所有奇数因子，是否满足上述的三个不等式，每满足一个不等式，就可以有一种用连续n个自然数相加将其表示的方法，当然不可能三个都满足，因为b不可能同时为奇数和偶数。

卡特兰数

chris — Sat, 01 Jan 2011 21:31:29 +0800

算法课最后一节讲到了卡特兰数，总结和学到了很多以前不知道的东西。

卡特兰数的递推公式是F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}
一般性公式为F(n)=C(2n,n)/(n+1)

可以描述的问题有
1、n个元素的二叉查找树有多少种。
2、n*n棋盘从左下角走到右上角而不穿过主对角线的走法。
3、2n个人排队买票问题，票价50，n个人拿50元，n个人拿100元，售票处无零钱，能顺利卖票的所有排队方式。
4、n个元素全部入栈并且全部出栈的所有可能顺序。

这些问题的答案都是卡特兰数F(n)。但是很明显可以看出后三个问题是同质的。
都可以抽象成2n个操作组成的操作链，其中A操作和B操作各n个，且要求截断到操作链的任何位置都有：A操作（向右走一步、收到50元、元素入栈）的个数不少于B操作（向上走一步、收到100元找出50元、元素出栈）的个数。故问题2、3、4其实是同一个问题。

下面先证明问题2、3、4和问题1同解，再证明问题2、3、4的解是F(n)=C(2n,n)/(n+1)，从而证明问题1的解也是F(n)=C(2n,n)/(n+1)。

1、问题2、3、4和问题1同解
问题1的解是F(n)=∑(k=0…n-1){F(k)*F(n-1-k)}，因为一棵n个结点的二叉排序树的根可以是1到n的任意结点，设为k，则其左子树结点个数为k，左子树的种类一共有F(k-1)种，右子树结点个数为n-k，右子树的种类一共有F(n-k)。而究竟哪一点为根可以有1到n共n个选择，故k取遍1到n——F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k)*F(n-k-1)}。

如果我们能证明问题2的解也可表示为F(n)=∑(k=0…n-1){F(k)*F(n-1-k)}，就完成了证明。

考虑n*n棋盘，记主对角线为L。从左下角走到右上角不穿过对角线L的所有路径，不算起点，一定有第一次接触到L的位置（可能是终点），设此位置为M，坐标为(x,x)——设第一个数为横轴坐标。该路径一定从下方的(x,x-1)而来，而起点处第一步也一定是走向(1,0)，两者理由相同——否则就穿过了主对角线。考虑从(1,0)到(x,x-1)的(x-1)*(x-1)的小棋盘中，因为在此中路径一直没有接触过主对角线（M的选取），所以在此小棋盘中路径也一定没有穿过从(1,0)到(x,x-1)的小棋盘的对角线L1。这样在这个区域中的满足条件的路径数量就是一个同构的子问题，解应该是F(x-1)，而从M到右上角终点的路径数量也是一个同构的子问题，解应该是F(n-x)，而第一次接触到主对角线的点可以从(1,1)取到(n,n)，这样就有F(n)=∑(k=1…n){F(k-1)*F(n-k)}=∑(k=0…n-1){F(k-1)*F(n-k)}。证毕。

2、问题2的解为F(n)=C(2n,n)/(n+1)
思路是先求所有从(0,0)到(n,n)的路径数X，再求所有穿过主对角线L的从(0,0)到(n,n)的路径数Y，用前者减去后者得到所求。
从(0,0)到(n,n)的路径数显然是C(2n,n)，一共要走2n步到达右上角，其中向右和向上各n步，总走法是C(2n,n)。
考虑一个新增的位置(n-1,n+1)，它位于终点的左上角一个格处，设所有从(0,0)到(n-1,n+1)的路径数为Z，下面要证明Y和Z相等，从而通过求Z来求Y。
考虑从(0,1)到(n-1,n)的对角线L2，对于所有穿过L而到达终点的路径，一定会接触到L2，找出某路径第一次接触到L2的位置M1，将从M1到终点的路径沿L2做对折一定会得到一条从M1到(n-1,n+1)的路径，故每条穿过L到达终点的路径都对应一条到达(n-1,n+1)的路径，即有Y<=Z。

所有从起点到达(n-1,n+1)的路径都一定会穿过L2，找出某路径第一次穿过L2的位置M2，将M2到(n-1,n+1)的路径沿L2对折，就得到一条M2到(n,n)的路径，且该条路径一定穿过L，故每条到达(n-1,n+1)的路径都对应一条穿过L到达终点的路径，即有Z<=Y。
故Z==Y。
接下来通过求Z来求Y。Z是显然的从(0,0)到(n-1,n+1)共需走2n步，其中向右n-1步、向上n+1步，故Z=C(2n,n-1)。
由以上可知F(n)=X-Y=X-Z=C(2n,n)-C(2n,n-1)=C(2n,n)/(n+1)。证毕。

由以上可知问题1的解也是F(n)=C(2n,n)/(n+1)，故求和(k){F(k)*F(n-1-k)}=C(2n,n)/(n+1)。这个数称为卡特兰数，前几项为1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796。

除了上面描述的四个问题外，它对应的问题还有：
矩阵链所有乘法顺序问题（同问题1）。
凸多边形剖分成三角形的方法数（同问题1）。

理解动态规划

chris — Sat, 25 Dec 2010 16:09:27 +0800

看了《算法导论》上对动态规划的讲解，觉得自己对动态规划的理解又进了一步，之前在读到《算法之道》相关章节时就有这感觉，但是仍然不敢说自己已经完全掌握了动态规划，只是比以前又透彻了一些，说说自己新的理解，其实就是复述一下算法导论上的内容而已。

0.两个例子

装配线调度问题

一个产品要经过N道工序，有两条装配链提供着N道工序，在任何一道工序i时产品都可以选择在两条线上的一条进行加工，在装配线1上加工工序i的时间为a[i][1]，装配线2上类似。在同一条装配线上前进不花时间，跳转到另一条装配线上需要一定的时间t[1][i]（从装配线1的工序i跳转到装配线 2的工序i+1所花费的时间）和t[2][i]（类似）。

问题是求解一个产品最快完成所有工序所需的时间。

动态规划解法：

我们用dp[i][j]存放在第j条装配线完成第i到工序所用的最少时间，其中i=1…N,j=1,2。因为要么是从同条装配线的上一道工序而来，要么是从另一条装配线的上一道工序跳转而来，而最少时间应该是这两种情况里较少的那种。注意应该认为dp[i-1][1]和dp[i-1][2]已经求解完毕，或者说不要关心它们，只要认为它们存放的是正确答案就可以了，为何可以如此，见后面。则有：

dp[i][1] = min(dp[i-1][1]+a[i][1],dp[i-1][2]+t[i-1][2]+a[i][1])

dp[i][2] = min(dp[i-1][1]+t[i-1][1]+a[i][2],dp[i-1][2]+a[i][2])

这样min(dp[N][1],dp[N][2])就是想要的答案。

矩阵链乘法问题

两个矩阵A(lxm)*B(mxn)相乘所需要的代价是O(lmn)，而相乘得到的矩阵式C(lxn)型的，l和n作为矩阵的行列数量仍然保存在了矩阵链中，因此对于一个矩阵链的乘法来说，做乘法的顺序不同，所花费的时间就可能相差很多，矩阵链乘法问题就是对于一个给定的矩阵链相乘，求解最少的计算时间（如何安排乘法的计算顺序）。

动态规划解法：

我们用dp[i][j]表示矩阵链中从第i个乘到第j个所需的最少时间，用r[i]和c[i]分别表示第i个矩阵的行数和列数。有：

dp[i][j]=min(k)(dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j])

注意c[k]==r[k+1]

即，i到j这一部分矩阵链的最优计算一定是在某处k（i<=k<j）将矩阵链分成两部分，通过先计算i到k和k+1到j这两条矩阵链再将这两个矩阵相乘得到的。

1.什么是动态规划

dynamic programming这里的programming指的是查表，表里存放的是之前求解过的子问题的解。动态规划就是动态查表，即在求解的过程中的每一步都需要查表来得到对当前子问题求解所需的信息。如在装配线问题上dp[i][1]就分别查表找到了dp[i-1][1]和dp[i-1][2]；矩阵乘法链问题上dp[i][j]的求解查表找到了对应于不同k值的dp[i][k]和dp[k+1][j]。

正因为存放在了表里，所以不用再次求解，才达到了较高的效率，将传统回溯解法指数的复杂度降低为多项式程度，关于复杂度后面还会说到。

2.最优子结构

一个问题要想用动态规划的方法来解决，必须具有最优子结构，至于为什么具有最优子结构的问题就可以用动态规划来解决，后面说。现在说说什么叫最优子结构。

最优子结构是指一个问题的解是一个选择过程，可能是二选一（装配线问题选择从前一道工序的哪条线上过来）、可能是多选一（矩阵链决定从哪里断开，即先做哪一处乘法）。假设作出了正确的选择后（这其实是需要子问题信息来做选择依据的），原问题就退化成一个或多个子问题（在装配线问题中，退化成所选择的那条装配线上完成第i-1道工序需要的最少时间，这是一个子问题；在矩阵乘法链问题中，退化成两条矩阵链i到k和k+1到j的最优求解问题，这是两个子问题），所谓子问题指的是与原问题同构但规模较小的问题。

光有这个性质还不叫具有最优子结构，最优子结构的另一个要求是原问题的最优解必须包含子问题的最优解。在验证这一点时，可以通过剪贴+反证法的思路，即如果该解法用到的子问题的解不是最优的，那么以最优的解代替之一定可以得到该问题的一个更好的解。还是通过例子说，装配线问题中，不管加工工序i的最优选择是从哪条线过来，所用到的在该线上加工工序i-1的时间一定需要是最优的，否则用最优的替换之可得到对于工序i的一个更优的解。

有了这两条性质——1.做选择后问题退化为一个或几个子问题、2.问题的最优解包含子问题的最优解，一个问题就具备了最优子结构。

3.为什么高效、如何求解

如果一个问题具有最优子结构的第一条性质，就可以使用分而治之的思想求解，比如递归。通常做法是将问题分解，然后对于分解出现的各个子问题分别递归求解，如果这种分解是多分枝的，那么复杂度应该是指数级的。

同递归思想一样，动态规划也需要对所有子问题都全部求解才能得到最终的答案，但是动态规划不愿意单纯地像递归那样做，而希望能够通过一些手段只做必要的工作，多余的一点都不想做。

动态规划是基于如下两点观察：

1）某个子问题的求解只和规模更小的子问题求解有关，而与与其同规模或者更大规模的子问题求解无关。

2）某个子问题的求解只用到其子问题的最优解，也就是说对于一个子问题来说，只有其最优解是有价值的。

通过观察1）我们知道只要在求解所有子问题时控制子问题的求解顺序按照子问题规模递增来进行，就能保证求解任意子问题时，它所依赖的规模较小的子问题都已经求解完毕。

通过观察2）我们知道只有最优解是有意义的，因此我们将最优解存在表里以供后面用到时查找，就可以保证某个子问题只被求解一遍，而且有了上一个观察，在求解某个子问题时，可以保证它所需要的表格内容都已经准备好了。

所以动态规划的解法已经呼之欲出了。

首先证明一个问题具有最优子结构，然后发现描述该问题的子问题应该是什么形式的（装配线问题中的dp[i][1]、dp[i][2]和矩阵链乘法问题中的dp[i][j]），按照子问题规模递增的顺序求解所有子问题，最后得到整个问题的解。

而，这里的关键就是找出子问题的形式，和子问题在经过选择后如何向更小规模的子问题退化。

下面给出两个例子的伪代码

装配线问题

dp[1][1] = a[1][1];
dp[1][2] = a[1][2];
for (int i = 2;i <= n;i++)
{
	dp[i][1] = min(dp[i-1][1]+a[i][1],dp[i-1][2]+t[i-1][2]+a[i][1]);
	dp[i][2] = min(dp[i-1][1]+t[i-1][1]+a[i][2],dp[i-1][2]+a[i][2]);
}

矩阵链乘法

for (int i = 1;i <= n;i++)
{
	dp[i][i] = 0;
}
for (int l = 2;l <= n;l++)
{
	for (int i = 1;i <= n-l;i++)
	{
		int j = i+l-1;
		for (int k = i;k < j;k++)
		{
			dp[i][j] = min(dp[i][j],dp[i][k]+dp[k+1][j]+r[i]*c[k]*c[j]);
		}
	}
}

4.动态规划的时间复杂度由什么决定

动态规划的过程就是求解所有子问题的过程，因此首先复杂度由子问题的个数决定，而子问题的个数又有子问题的形式所决定。在装配线问题中子问题形式是 dp[i][1 or 2]，其中只有i是变化的，因此子问题个数为O(n)；在矩阵链乘法问题中，子问题形式是dp[i][j]，i和j都在变化，因此子问题个数是 O(n^2)。另外由于前面所提到的每一个子问题都是一个选择，可能是二选一，可能是多选一，而要解答此子问题就要考察所有的选项，因此每一个子问题的求解时间还和面临的选择个数有关，因此复杂度应该是子问题个数*每个子问题面临选择数。这样，装配线问题的时间复杂度O(n)，矩阵链乘法问题的时间复杂度为O(n^3)，正如代码中所示。

网络最大流、二分图最大匹配、POJ2536

chris — Tue, 14 Dec 2010 14:00:06 +0800

通常我们把一个有向无环图边上的权值看做两个节点之间的距离，在这个模型下的问题有各种最短路问题。如果将边上的权值不看做距离而看做两点间的容量（比如两个城市之间一天的运输能力），这样的有向无环图就叫做流网络，对应的问题就是求最大流——单位时间内通过网络的最大容量（比如工厂所在城市一天最多可以生产多少才能全部经过一个流网络运到仓库所在城市而不造成中途的淤积）。

流网络只有一个源点和一个汇点。关于定义就不说了，算法导论上很清楚。有一点要说的是，如果一个流网络有多个源点和多个汇点，可以通过增加一个到所有现有源点的容量都无穷的超级源点和一个所有汇点到其容量都无穷的超级汇点转化成只有一个源点和一个汇点的流网络。

求流网络的最大流算法是Ford-Fulkerson算法。首先定义一条边的残留容量是容量减去现有流，由残留容量标示的网络称为残留网络。再定义增广路径是残留网络中从源点s到汇点t的一条路径。Ford-Fulkerson算法是一个迭代过程。每次在残留网络中查找一条增广路径，然后把这条增广路径中最小的一段残留容量加到增广路径各条边的流上，更新残留网络继续迭代，直到找不到增广路径为止。此时退出迭代，现有流就是最大流。

二分图有两部分节点L和R，各部分内部节点之间没有边，即每条边的两个节点都一定分属这两部分，二分图的一个匹配是找到这样一组边，使得每个节点都只有至多一条边与其相连。

二分图的最大匹配问题可以转化为网络最大流问题。增加一个到所有L中顶点容量均为1的源点s和一个所有R中顶点到其容量均为1的汇点t，所有L到R中的边容量也设置为1，现在查找此网络流的最大流就等同于求此二分图的最大匹配。证明过程见算法导论。

POJ2536就是一道二分图最大匹配的应用。题目给出n个老鼠的坐标和m个鼠洞的坐标，如果一只老鼠能在一定时间内到达一个鼠洞，就能躲过老鹰。所以如果某个老鼠与某个鼠洞之间距离小于某值，它俩之间就存在一条边，否则不存在，这是一个明显的二分图。而要求有多少老鼠能躲过老鹰，自然是求此二分图的最大匹配。

代码如下：

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
 
using namespace std;
 
#define N 205
#define MAX 1000000
 
int capacity[N][N] = {0};
int r_capcity[N][N] = {0};
int fluid[N][N] = {0};
int flag_for_bfs[N][N] = {0};
int s,t;
 
int bfs_findP(vector<int>& p,int numV)
{
	p.clear();
	queue<int> q;
 
	//标记是否已经入过队
	int checked[N] = {0};
 
	q.push(s);
	checked[s] = 1;
 
	int pre[N];
	memset(pre,-1,sizeof(pre)/sizeof(int));
 
	int cur;
 
	//一个节点可以有多个后继，但是只能有一个前驱！因此用一个数组就可以记录找到的路径
	while (!q.empty())
	{
		cur = q.front();
		q.pop();
		if (cur == t)
		{
			break;
		}
 
		for (int i = 0;i < numV;i++)
		{
			if (checked[i] == 0 && cur != i && r_capcity[cur][i] > 0)
			{
				q.push(i);
				checked[i] = 1;
				pre[i] = cur;
 
				/*if (i == t)
				{
					goto outside;
				}*/
			}
		}
	}
 
	if (cur != t)
	{
		return -1;
	}
	int i = pre[cur];
	p.insert(p.begin(),cur);
	while (i != s)
	{
		p.insert(p.begin(),i);
		i = pre[i];
	}
 
	return 0;
}
 
//0.首先设置所有的容量capacity[i][j]
//1.先将所有边的流都置为，
//2.然后迭代：
//更新r_capacity[i][j] = capacity[i][j] - fluid[i][j]
//每次找到一条增广路径，找增广路径使用BFS，增广路径是一条从源点S到汇点T的简单路径
 
//for each edge(u,v) in p 
//	do	f[u,v] <- f[u,v]+fmin
//		f[v,u] <- -f[u,v]
 
 
int max_fluid(int numV)
{
	for (int i = 0;i < numV;i++)
	{
		for (int j = 0;j < numV;j++)
		{
			fluid[i][j] = 0;
			r_capcity[i][j] = capacity[i][j] - fluid[i][j];
		}
	}
	//1 done!
 
	vector<int> p;
	int r_cap = MAX;
	int key_i = -1,key_j = -1;
	while (bfs_findP(p,numV) != -1)
	{
 
 
 
		//find fmin
		r_cap = r_capcity[s][p[0]];
 
		for (int i = 0;i < p.size()-1;i++)
		{
			if (r_capcity[p[i]][p[i+1]] < r_cap)
			{
				r_cap = r_capcity[p[i]][p[i+1]];
				key_i = p[i];
				key_j = p[i+1];
			}
		}
 
		fluid[s][p[0]] += r_cap;
		fluid[p[0]][s] = -fluid[s][p[0]];
 
		for (int i = 0;i < p.size()-1;i++)
		{
			fluid[p[i]][p[i+1]] = fluid[p[i]][p[i+1]] + r_cap;
			fluid[p[i+1]][p[i]] = -fluid[p[i]][p[i+1]];
		}
 
		for (int i = 0;i < numV;i++)
		{
			for (int j = 0;j < numV;j++)
			{
				r_capcity[i][j] = capacity[i][j] - fluid[i][j];
			}
		}
	}
	//2,3,4 done!
 
	int ans = 0;
	for (int i = 0;i < numV;i++)
	{
		if (s != i && fluid[s][i] > 0)
		{
			ans += fluid[s][i];
		}
	}
 
	return ans;
}
 
float distance(float x1,float y1,float x2,float y2)
{
	return sqrt((x1-x2)*(x1-x2) + (y1-y2)*(y1-y2));
}
 
int main()
{
	int n,m,S,V;
	float gophers[105][2],holes[105][2];
 
	while (cin>>n)
	{
		cin>>m>>S>>V;
		for (int i = 0;i < n;i++)
		{
			cin>>gophers[i][0]>>gophers[i][1];
		}
 
		for (int i = 0;i < m;i++)
		{
			cin>>holes[i][0]>>holes[i][1];
		}
 
		for (int i = 0;i < N;i++)
		{
			for (int j = 0;j < N;j++)
			{
				capacity[i][j] = 0;
			}
		}
 
		int numV = m + n + 2;
 
		s = 0;
		t = m + n + 1;
 
		for (int i = 1;i <= n;i++)
		{
			capacity[0][i] = 1;
		}
 
		for (int i = n+1;i <= n+m;i++)
		{
			capacity[i][t] = 1;
		}
 
		for (int i = 1;i <= n;i++)
		{
			for (int j = n+1;j <= n+m;j++)
			{
				if (distance(gophers[i-1][0],gophers[i-1][1],holes[j-n-1][0],holes[j-n-1][1]) <= V*S)
				{
					capacity[i][j] = 1;
				}
			}
		}
 
		cout<<n - max_fluid(numV)<<endl;
	}
}

一道面试题，关于在数组里找一些数

chris — Tue, 23 Nov 2010 17:15:10 +0800

在一个int数组里查找这样的数，它大于等于左侧所有数，小于等于右侧所有数。
直观想法是用两个数组a、b。a[i]、b[i]分别保存从前到i的最大的数和从后到i的最小的数，这需要两次遍历，然后再遍历一次原数组，将所有data[i]>=a[i-1]&&data[i]<=b[i]的data[i]找出即可。

给出这个解答后，面试官有要求只能用一个辅助数组，且要求少用一次遍历。想了半天没想出来，后来在面试官的提示下得出解，今天实现了一下。

见代码：

#include <iostream>
 
using namespace std;
 
#define max(a,b) a>b?a:b
#define min(a,b) a<b?a:b
 
void findNum(int data[],int len)
{
	int* a = new int[len];
	int* b = new int[len];
	a[len-1] = data[len-1];
	for (int i = len-2;i > 0;i--)
	{
		a[i] = min(data[i],a[i+1]);
	}
 
	if (data[0] <= a[1])
	{
		cout<<"0:"<<data[0]<<endl;
	}
 
	a[0] = data[0];
	if (data[1] >= a[0] && data[1] <= a[2])
	{
		cout<<"1:"<<data[1]<<endl;
	}
 
	for (int i = 1;i < len-2;i++)
	{
		a[i] = max(data[i],a[i-1]);
		if (data[i+1] >= a[i] && data[i+1] <= a[i+2])
		{
			cout<<i+1<<":"<<data[i+1]<<endl;
		}
	}
	a[len-2] = max(data[len-2],a[len-3]);
	if (data[len-1] >= a[len-2])
	{
		cout<<len-1<<":"<<data[len-1]<<endl;
	}
}
 
int main()
{
	int data[10] = {1,3,2,4,6,7,5,9,11,10};
	findNum(data,10);
}

二叉树先序、中序、后序遍历的非递归实现

chris — Tue, 23 Nov 2010 14:28:11 +0800

在网上看了一些用非递归实现先序中序后序遍历二叉树的代码，都很混乱，while、if各种组合嵌套使用，逻辑十分不清晰，把我也搞懵了。想了大半天，写了大半天，突然开了窍，实际上二叉树的这三种遍历在逻辑上是十分清晰的，所以才可以用递归实现的那么简洁。既然逻辑如此清晰，那么用非递归实现也应该是清晰的。

自认为自己的代码比网上搜到的那些都清晰得多，好理解得多。

稍微解释一下：

先序遍历。将根节点入栈，考察当前节点（即栈顶节点），先访问当前节点，然后将其出栈（已经访问过，不再需要保留），然后先将其右孩子入栈，再将其左孩子入栈（这个顺序是为了让左孩子位于右孩子上面，以便左孩子的访问先于右孩子；当然如果某个孩子为空，就不用入栈了）。如果栈非空就重复上述过程直到栈空为止，结束算法。

中序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过（有标记），则将其左孩子入栈，否则访问当前节点并将其出栈，再将右孩子入栈。如果栈非空就重复上述过程直到栈空为止，结束算法。

后序遍历。将根节点入栈，考察当前节点（即栈顶节点），如果其左孩子未被访问过，则将其左孩子入栈，否则如果其右孩子未被访问过，则将其右孩子入栈，如果都已经访问过，则访问其自身，并将其出栈。如果栈非空就重复上述过程直到栈空为止，结束算法。

其实，这只不过是保证了先序中序后序三种遍历的定义。对于先序，保证任意一个节点先于其左右孩子被访问，还要保证其左孩子先于右孩子被访问。对于中序，保证任意一个节点，其左孩子先于它被访问，右孩子晚于它被访问。对于后序，保证任意一个节点的左孩子右孩子都先于它被访问，其中左孩子先于右孩子被访问。如是而已。

代码里应该体现得比较清楚。这里不光给出了非递归版本，也给出了递归版本。

#include <iostream>
#include <stack>
 
using namespace std;
 
struct TreeNode 
{
	int data;
	TreeNode* left;
	TreeNode* right;
	int flag;
};
 
typedef TreeNode *TreePtr;
 
TreePtr CreateTree()
{
	TreePtr root = new TreeNode;
	cout<<"input the data :\n";
	int n;
	cin>>n;
	if (n == -1)
	{
		return NULL;
	} 
	else
	{
		root->data = n;
		root->flag = 0;
		root->left = CreateTree();
		root->right = CreateTree();
	}
	return root;
}
 
void PreOrderRecursion(TreePtr p)
{
	if (p == NULL)
	{
		return;
	}
	cout<<p->data<<" ";
	PreOrderRecursion(p->left);
	PreOrderRecursion(p->right);
}
 
void InOrderRecursion(TreePtr p)
{
	if (p == NULL)
	{
		return;
	}
	InOrderRecursion(p->left);
	cout<<p->data<<" ";
	InOrderRecursion(p->right);
}
 
void PostOrderRecursion(TreePtr p)
{
	if (p == NULL)
	{
		return;
	}
	PostOrderRecursion(p->left);
	PostOrderRecursion(p->right);
	cout<<p->data<<" ";
}
 
void PreOrderNoRecursion(TreePtr p)
{
	cout<<"PreOrderNoRecursion\n";
 
	stack<TreeNode> stk;
	TreeNode t = *p;
	stk.push(t);
 
	while (!stk.empty())
	{
		t = stk.top();
		stk.pop();
		cout<<t.data<<" ";
 
		if (t.right != NULL)
		{
			stk.push((*t.right));
		}
 
		if (t.left != NULL)
		{
			stk.push((*t.left));
		}
	}
}
 
void InOrderNoRecursion(TreePtr p)
{
	cout<<"InOrderNoRecursion\n";
 
	stack<TreeNode> stk;
	TreeNode t = *p;
	stk.push(t);
 
	while (!stk.empty())
	{
		if (stk.top().flag == 0)
		{
			stk.top().flag++;
			if (stk.top().left != NULL)
			{
				stk.push(*(stk.top().left));
			}
		}
		else
		{
			t = stk.top();
			stk.pop();
			cout<<t.data<<" ";
			if (t.right != NULL)
			{
				stk.push(*(t.right));
			}
		}
	}
}
 
void PostOrderNoRecursion(TreePtr p)
{
	cout<<"PostOrderNoRecursion\n";
 
	stack<TreeNode> stk;
	TreeNode t = *p;
	stk.push(t);
 
	while (!stk.empty())
	{
		if (stk.top().flag == 0)
		{
			stk.top().flag++;
			if (stk.top().left != NULL)
			{
				stk.push(*(stk.top().left));
			}
		} 
		else if (stk.top().flag == 1)
		{
			stk.top().flag++;
			if (stk.top().right != NULL)
			{
				stk.push(*(stk.top().right));
			}
		} 
		else
		{
			cout<<stk.top().data<<" ";
			stk.pop();
		}
	}
}
 
int main()
{
	TreePtr t = CreateTree();
 
	cout<<"PreOrderRecursion\n";
	PreOrderRecursion(t);
	cout<<"\n";
 
	cout<<"InOrderRecursion\n";
	InOrderRecursion(t);
	cout<<"\n";
 
	cout<<"PostOrderRecursion\n";
	PostOrderRecursion(t);
	cout<<"\n";
 
	PreOrderNoRecursion(t);
	cout<<"\n";
 
	InOrderNoRecursion(t);
	cout<<"\n";
 
	PostOrderNoRecursion(t);
	cout<<"\n";
}