(28)Go記憶化搜索和動態(tài)規(guī)劃解決問題

問題1：求爬樓梯方法 //

結(jié)構(gòu)圖如下

根據(jù)上圖翼闽，可以推導(dǎo)出：
設(shè)c(n)為爬n階樓梯的方法總數(shù)
例1)每次可以爬 1 或 2 個臺階，則c(n)=c(n-1)+c(n-2)
例2)每次可以爬 1 或 2 或 3 個臺階撑毛，則c(n)=c(n-1)+c(n-2)+c(n-3)
理解好這點(diǎn)蹦疑，代碼就容易寫了

動態(tài)規(guī)劃實(shí)現(xiàn)
func climbStairs(n int) int {
    if n < 2 {
        return 1 // 無臺階可走算1種
    }

    memo := make([]int, n+1)
    memo[0] = 1
    memo[1] = 1
    for i := 2; i <= n; i++ {
        memo[i] = memo[i-1] + memo[i-2]
    }
    return memo[n]
}

提交leetcode，通過

問題2：求三角形最短路徑和 //

思路：先弄清該三角形的數(shù)學(xué)關(guān)系
第x行有x+1個點(diǎn)莺奸，x行y列點(diǎn)的下一行相鄰兩點(diǎn)坐標(biāo)是[x+1][y]，[x+1][y+1]
理解好這點(diǎn)览妖，之后寫代碼較容易

// 解法1:動態(tài)規(guī)劃1--二維空間存儲 （理解好解法1有助于理解解法2）
// 定義(n+1)*(n+1)的二維數(shù)組minDis[][]int
// minDis[i][j]代表triangle[i][j]到達(dá)底部的最短距離,最底層最短距離為本身的值
// minDis[0][0]代表從頂層到最底層的最短距離
// 空間復(fù)雜度為O(n^2)
func minimumTotal(triangle [][]int) int {
    n := len(triangle)
    if n == 0 {
        return 0
    }

    // (n+1)*(n+1)二維數(shù)組
    // n+1層是為了統(tǒng)一邏輯好寫代碼
    minDis := make([][]int, n+1)
    for i := 0; i < n+1; i++ {
        minDis[i] = make([]int, n+1)
    }

    // 底層開始遍歷
    for i := n - 1; i >= 0; i-- {
        for j, v := range triangle[i] {
            // 相鄰的兩個點(diǎn)是下一層的j,j+1
            // 默認(rèn)值均為0,第一層循環(huán)結(jié)束后,n-1(底層)層存儲的是自身的值
            minDis[i][j] = v + min(minDis[i+1][j], minDis[i+1][j+1])
        }
    }
    return minDis[0][0]
}

解法1提交leetcode恢准，通過

由解法1可以看出，triangle[i][j]的最短距離依賴i+1層的正下方和右邊果正，
因此點(diǎn)[i+1][j]前面的值更新為i行的數(shù)據(jù)，并不會影響i行后續(xù)最短距離的更新
triangle[i][j]最短距離的更新可以寫成minDis[j] = triangle + min(minDis[j], minDis[j+1])

// 解法2:動態(tài)規(guī)劃2--一維空間存儲
// 空間復(fù)雜度為O(n)
func minimumTotal2(triangle [][]int) int {
    n := len(triangle)
    if n == 0 {
        return 0
    }

    // (n+1)一維數(shù)組
    //+1是為了統(tǒng)一邏輯好寫代碼
    // minDis[0]為頂層到底層的最短距離
    minDis := make([]int, n+1)

    // 底層開始遍歷
    // 第一次循環(huán)后,minDis的值即為底層本身的值(距離)
    for i := n - 1; i >= 0; i-- {
        for j, v := range triangle[i] {
            // j更新前為上一層的j位置的最短距離,更新后j為本層最短距離,
            // 而j+1不被改變,在下一次循環(huán)中可用來做比較和更新
            minDis[j] = v + min(minDis[j], minDis[j+1])
        }
    }
    return minDis[0]
}

提交leetcode，通過

問題3：打家劫舍 //

展開圖如下：

上上圖可知：//
設(shè)rob[0.n]為偷取[0..n]房子的最佳策略救欧，v[0...n]為房子?xùn)|西的價(jià)值
偷取[0...n]范圍的房子蹬刷，存在n種決策
rob[0...n] = max{v[0]+rob[2...n]，v[1]+rob[3...n]充活，v[2]+rob[4...n]映穗，...，v[n-2]+rob[n...n]幕随，v[n-1]蚁滋，v[n]}
所有策略中選擇價(jià)值最大的一種策略即為最優(yōu)策略

狀態(tài)的定義和狀態(tài)轉(zhuǎn)移方程如下圖：

func max(v1, v2 int) int {
    if v1 > v2 {
        return v1
    }
    return v2
}

// 方法1:記憶化搜索
func rob(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }
    
    // memo[i]表示偷取[i...n-1]所能獲得的最大價(jià)值
    // 初始值設(shè)為-1,表示沒有計(jì)算過偷取[i..n-1]的最大價(jià)值
    memo := make([]int, n)
    for i := 0; i < n; i++ {
        memo[i] = -1
    }
    return tryRob(nums, 0, n, memo)
}

// 考慮搶劫[index...n-1]區(qū)間的房子,所能獲得的最大收益
func tryRob(nums []int, index, n int, memo []int) int {
    
    // 遞歸終止條件
    if index >= n {
        return 0
    }
    
    // 遞歸過程
    if memo[index] != -1 {
        return memo[index]
    }
    
    res := 0 //偷取[index...n-1]的最大價(jià)值
    for i := index; i < n; i++ {
        res = max(res, nums[i]+tryRob(nums, i+2, n, memo))
    }
    memo[index] = res
    return res
}

動態(tài)規(guī)劃：
由狀態(tài)轉(zhuǎn)移方程可以看出rob[n-1...n]，依賴于rob[n...n]的答案，
rob[n-2...n]，依賴于rob[n-1...n]和rob[n...n]的答案岗钩，因此可以從尾部開始解答雹拄，
一步步擴(kuò)大區(qū)間荡陷，最終解[0...n]的問題

// 方法2 動態(tài)規(guī)劃
// 時間復(fù)雜度O(n^2)
func rob2(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

    // memo[i] 表示考慮搶劫nums[i...n-1]所能獲得的最大收益
    memo := make([]int, n)
    memo[n-1] = nums[n-1]

    // 反向遍歷,從小問題一步步求解,最后解出大問題
    for i := n - 2; i >= 0; i-- {
        for j := i; j < n; j++ {
            // j+2會越界,越界即沒有可以偷的房子,返回nums[j] + 0
            if j+2 >= n {
                memo[i] = max(memo[i], nums[j])
            } else {
                // 遍歷前面所有解,找出最優(yōu)策略
                memo[i] = max(memo[i], nums[j]+memo[j+2])
            }
        }
    }
    return memo[0]
}

TIM截圖20190515183828.jpg

提交leetcode，通過

不同的狀態(tài)定義，有不同的狀態(tài)轉(zhuǎn)移方程。
將問題3的狀態(tài)從考慮偷取[index...n-1]區(qū)間改成考慮偷取[0...index]區(qū)間
動態(tài)規(guī)劃實(shí)現(xiàn)則變成以下這樣
// 動態(tài)規(guī)劃2：考慮偷取[0...index]范圍里的房子
func rob3(nums []int) int {
    n := len(nums)
    if n == 0 {
        return 0
    }

    // memo[i] 表示考慮搶劫nums[i...i]所能獲得的最大收益
    // 這樣最大值就是memo[n-1]
    memo := make([]int, n)
    memo[0] = nums[0]

    // 正向遍歷,從小問題一步步求解,最后解出大問題
    for i := 1; i < n; i++ {
        for j := i; j >= 0; j-- {
            // j+2有會越界,越界即沒有可以偷的房子,返回nums[j] + 0
            if j-2 < 0 {
                memo[i] = max(memo[i], nums[j])
            } else {
                // 遍歷前面所有解,找出最優(yōu)策略
                memo[i] = max(memo[i], nums[j]+memo[j-2])
            }
        }
    }
    return memo[n-1]
}

提交leetcode蚣旱，通過

有bug歡迎指出