一道google的面试题

   今天，同学拿来一道google面试题让我做，说实在的，很长时间没做ACM题了，心里还真是没底，还好结果还是解决了， 具体如下：

   给定一棵有N个结点的二叉树。求它的所有结点数为M的连通子图数目。

 

解决方法： （主要用到DP算法）

设以n为根的结点数为m的连通子图数目 dp[n][m]

 

状态转移方程：

dp[n][m] =

dp[2n][m-1] //左孩子

+dp[2n+1][m-1] //右孩子

+SUM { dp[2n][i] * dp[2n+1][m-1-i]} //1<=i

 

初始化： dp[i][1] = 1; dp[i][0] = 0;
最终结果为：  SUM (dp[i][m]) //i=1...n

 

这是一个比较简单的DP， 好长时间没练习了， 都有点生疏了。

 

举个简单的例子：

阅读(651) | 评论(0) | 转发(0) |

0

上一篇：subversion 安装和配置步骤

下一篇：vfprint的用法