問題
漢尼撥博士越獄了贫母，他會在各個村子里逃跑，采取的策略是每天都會隨機逃到鄰近（有路通）的下一個村子，那么N天后悼粮，博士在某個村子Q的概率是多少。
問題的輸入：
- 一共有n個村子
- adj(i)表示與i村子鄰接的村子的集合曾棕。|adj(i)|表示這些村子的個數(shù)扣猫。
- 監(jiān)獄所有的村子
。
- N天后翘地，求博士在
的概率申尤。
解法1
暴力最愛癌幕，把從一開始的所有有效路徑（長度為N）算出來，挑出最后一個是Q的百分比昧穿，就是博士在Q村的概率序芦。
這個算法還可以稍稍改良一下。不是計算出現(xiàn)的次數(shù)的概率粤咪，而是最后一個是Q的 概率谚中，這需要記住到達Q的線路，然后計算出整條線路概率
path是記錄到的一條線路寥枝，path[i]是第i天出現(xiàn)的村莊編號宪塔，把所有以Q結束的線路的幾率加起來，就是博士在那里的概率了囊拜。
為了能夠使用制表技術某筐，需要對的輸入進行簡化，對于子問題（遞歸的那一部分）真正需要的信息是path的最后一個節(jié)點編號冠跷，還有已經過了多少天南誊，在這樣的情況下，
解法2
我們可以大開始的時候計算蜜托，然后根據概率算出每一天在所有的位置的概率抄囚，以p[n-1][q]用來存儲第q天博士每一個村子出現(xiàn)的概率，那么
解法3：反著來
反著來的算法與算法1中的那個相似橄务，
理論背景
馬爾可夫鏈幔托，由前一個結點往下一個節(jié)點轉換，只跟當前節(jié)點相關蜂挪。
