[IT技術30篇挑戰] 資料結構和演算法實作 DAY13 – 動態規劃 @地瓜大的飛翔旅程

章節連結

動態規劃

適用範圍

LeetCode 練習記錄
系列文章

這一篇動態規劃筆記相關內容，並沒有存在於原先參照的這本書內，而是取自於 Hiskio 上的課程 – 從 LeetCode 學演算法。

動態規劃

動態規劃本身是比較不容易看出關聯性的。若有一個最一開始的結果可以直接找到，且第 n 步的結果可以用前面的結果來表達，那就屬於動態規劃的範疇。另外，解法並不限定你要選用遞迴還是迭代的方式來得出解答。

適用範圍

當目標問題可以拆成重複的不只一個的子問題，且每個子問題的答案必須是定值和可被儲存下來。

LeetCode 練習記錄

經典的路徑規劃題目，在高中數學的排列組合中，有類似的東西。
/*62. Unique Paths*/
var uniquePaths = function(m, n) {
    let target = []
    /*initialize the first row and first column, which are 1 or 0*/
    for(let i=0;i<m;i++){
        target[i] = []
        for(let j=0;j<n;j++){
            if(i===0 || j===0){
                target[i][j] = 1
            }else{
                target[i][j] = 0
            }
        }
    }
    /*the other cells*/
    for(let i=1;i<m;i++){
        for(let j=1;j<n;j++){
            target[i][j] = target[i-1][j]+target[i][j-1]
        }
    }
    return target[m-1][n-1]
};