最短路徑問題是 動态規劃的一個執行個體。
1.最短路徑問題的描述
2.舉個例子來說明：
求從 S 到 T 的最短路徑。
3.思考方式
4.利用動态規劃求解問題
依次 考慮從 C 到 T 的最短距離。
考慮從 B 到 C 的最短距離
考慮從 A 到 B 的最短距離
考慮從 T 到 A 的最短距離
每次都是最短距離。
在整個過程中，我們把 我們的目标問題轉化成了一個個的子問題，在子問題 求 最小值，最後解決了這個問題。
4.子問題的界定
5.最短路程之間的依賴關系
每一次計算的時候都是依據前一個子問題。不需要一個一個計算。每次計算都可以直接利用前一個問題的解。
6.子問題的優化原則
6.利用動态規劃求解是需要條件的，一個反例告訴你，動态規劃求解的條件
分析： 假如從S 到 T 經過的節點依次是 A B C ，從C 到 T ，模10，我們選擇 上面的2 . 從 B 到 C，我們的兩條路分别是 4 和 7 ，模10，我們選擇 上面的 4 ，那麼，從B到T的最短距離就是 6； 從 A 到 B ，我們的兩條路分别是 6 和 9，模10，我們選擇上面的路。
從 S 到 A ，兩條路分别是 8 和 11， 此時 ，模10，我們選擇下面的 路。這時，路徑就如上圖中藍色的路徑了。
但是，這是最優的路徑嗎？顯然不是，紅色的路線才是最優的路徑。因為模10後，得到的結果為0，比 1 小。
為什麼是錯誤的？
因為 破壞了動态規劃的優化原則，它的問題和它的子問題的優化函數之間沒有依賴關系。比如，我們考慮最後一段 即 C 到 T的距離，
顯然， 2是最優解，而不是 5 。是以，破壞了優化原則的問題不能使用 動态規劃。
7.動态規劃 小結
可以用于求解組合優化問題。注意 動态規劃的 最優化的原則。
8.代碼
這個問題的簡化版本，編碼實作：從矩陣的(0,0)位置到矩陣的(array.length-1,array[0].length-1)的位置的最小值。