[LeetCode]Pyramid Transition Matrix

这道题首先我们第一反应是考虑BFS或者DFS，但仔细考虑过后BFS事实上是做不了的，比如对于ABC和{ABD, ABE, BCK}，在AB的时候我们有两种选择，而我们BFS只能取一个。所以我们需要用DFS来遍历所有的可能，从最底层开始直到最顶层。对于每个合法的block，我们可以用bit来存，因为只会用到7个字符，比如我们用map[a][c]表示AC后面能够接的字符，每一位代表从a到g的每个字符。时间复杂度O(N^k)，N为最底层的长度，k为所用的字符数量。代码如下：