http://www.1point3acres.com/bbs/thread-147010-1-1.html
2. 这道题说起来比较复杂。假设你有一张表，这个表是每个字母在其他字母后面出现的概率。然后这个概率是根据一些东西算出来的，比如说一本字典。
假设字典是 ["cat", "cap"]
那表格就会是
a c p t.
a 0 0.5 0 0
c 0 0 0 0
p 0.25 0 0 0
t 0.25 0 0 0
ok，不知道格式会不会坏><，总之就是你有这样一个表格，然后他们的概率加起来是1嘛，但你不用担心这个表格是怎么来的。
然后如果你有这本字典，让你返回长度是4的最可能出现的单词（保证只有一个）.
follow up是如果没有这本字典，你如何算长度是4的最可能出现的单词（保证只有一个）
再follow up是，假设你现在根据比如说google search query有一个，2014年最经常搜索的单词list，然后根据这个list算出一个概率表格以及最可能出现的单词，然后现在你知道2015年添加了一些单词，如何更efficient的算出新的概率表格以及最可能出现的单词。
有字典的我就说最简单暴力的方法说把字典遍历一遍所有单词的概率算一遍最后得出最可能的单词.
然后没有字典的，有点像trie tree的感觉，dfs算最可能的单词
维特比算法就是给你一个状态转移概率矩阵，求最大概率的路径
就是用trie树的概念，但是只是做dfs 比如 root
/ | | ...... \.
a
/ | |...\ .........../ | |...\-
a b c...z ⬅这里就是a后面出现a,b,c,...z的概率）
然后依次往下，就用最基本的dfs，每层的概率乘起来，到达第四层的时候就得到这条路径的概率，就是这个词的概率。然后再记一个maxProb和resWord，每次到leaf的时候看要不要更新。
遍历完就结束辣！这样time complexity 是O(26^4)，space是constant。
不过你可以看下面一个同学写的dp解，我觉得也是正确的，但他的应该更快
维特比算法就是给你一个状态转移概率矩阵，求最大概率的路径，可以用dp来做。
状态转移概率矩阵可以由lz这里的矩阵得到，它是每行概率和为1，即 sigma(j) a[i][j] = 1。a[i][j]表示从字母i转移到j的概率，这里对j遍历求和是1。.
f[k][i]表示长度为k的单词并且最后以第i个字母结尾的概率。 f[k][i] = max(f[k-1][j] * a[j][i]).
然后一般默认初始分布是个均匀分布，这样子就能把最大路径的概率求出来了，另外做dp的时候记得保存下路径，就能求出最大概率的那条路径了。
2. 这道题说起来比较复杂。假设你有一张表，这个表是每个字母在其他字母后面出现的概率。然后这个概率是根据一些东西算出来的，比如说一本字典。
假设字典是 ["cat", "cap"]
那表格就会是
a c p t.
a 0 0.5 0 0
c 0 0 0 0
p 0.25 0 0 0
t 0.25 0 0 0
ok，不知道格式会不会坏><，总之就是你有这样一个表格，然后他们的概率加起来是1嘛，但你不用担心这个表格是怎么来的。
然后如果你有这本字典，让你返回长度是4的最可能出现的单词（保证只有一个）.
follow up是如果没有这本字典，你如何算长度是4的最可能出现的单词（保证只有一个）
再follow up是，假设你现在根据比如说google search query有一个，2014年最经常搜索的单词list，然后根据这个list算出一个概率表格以及最可能出现的单词，然后现在你知道2015年添加了一些单词，如何更efficient的算出新的概率表格以及最可能出现的单词。
有字典的我就说最简单暴力的方法说把字典遍历一遍所有单词的概率算一遍最后得出最可能的单词.
然后没有字典的，有点像trie tree的感觉，dfs算最可能的单词
维特比算法就是给你一个状态转移概率矩阵，求最大概率的路径
就是用trie树的概念，但是只是做dfs 比如 root
/ | | ...... \.
a
/ | |...\ .........../ | |...\-
a b c...z ⬅这里就是a后面出现a,b,c,...z的概率）
然后依次往下，就用最基本的dfs，每层的概率乘起来，到达第四层的时候就得到这条路径的概率，就是这个词的概率。然后再记一个maxProb和resWord，每次到leaf的时候看要不要更新。
遍历完就结束辣！这样time complexity 是O(26^4)，space是constant。
不过你可以看下面一个同学写的dp解，我觉得也是正确的，但他的应该更快
维特比算法就是给你一个状态转移概率矩阵，求最大概率的路径，可以用dp来做。
状态转移概率矩阵可以由lz这里的矩阵得到，它是每行概率和为1，即 sigma(j) a[i][j] = 1。a[i][j]表示从字母i转移到j的概率，这里对j遍历求和是1。.
f[k][i]表示长度为k的单词并且最后以第i个字母结尾的概率。 f[k][i] = max(f[k-1][j] * a[j][i]).
然后一般默认初始分布是个均匀分布，这样子就能把最大路径的概率求出来了，另外做dp的时候记得保存下路径，就能求出最大概率的那条路径了。
