1、簡(jiǎn)介
動(dòng)態(tài)規(guī)劃（Dynamic Programming，DP）是求解決策過程最優(yōu)化的過程，把原始問題劃分成一系列子問題，以分治的方法找出最優(yōu)解。

如果沒有最優(yōu)子結(jié)構(gòu)，就等同于回溯，比如斐波拉契數(shù)列；

如果局部最優(yōu)解就是全局最優(yōu)解，就等同于貪心算法，
比如錢幣的問題，如何用最少張紙幣匹配出某個(gè)數(shù)字？
如果用 10/5/1 這三種面額配 16 元，貪心算法用 10+5+1 湊出來是可以的；
但是如果用10/8/1 這三種面額匹配16元，貪心算法只能用 10+1+1+1+1+1+1，而顯然最優(yōu)解是 8+8，此時(shí)只能用動(dòng)態(tài)規(guī)劃，而貪心法比較有局限性。

2、題目
（1）給出一個(gè)三角形（用二維數(shù)組表示），找出自頂向下的最小路徑和。每一步只能移動(dòng)到下一行中相鄰的結(jié)點(diǎn)上（a[i][j] 的下一層相鄰結(jié)點(diǎn)有 a[i][j] 和 a[i][j+1] ）。
可以先用一個(gè)二維數(shù)組存儲(chǔ)中間結(jié)果，從最下面一層開始，逐步往上遞推：

package main
import "fmt"
func minimumTotal(triangle [][]int) int {
    x := len (triangle)
    m := make([][]int , x, x)

    for i:=0; i < x; i++ {
        m[i] = make([]int, len(triangle[i]), len(triangle[i]))
    }

    for i:=0; i < x; i++ {
        m[x-1][i] = triangle[x-1][i]
    }

    for i:= x - 2 ; i >= 0; i-- {
        for j:=0; j < len (triangle[i]) ; j++ {
            min := m[i+1][j]
            if m[i+1][j+1] < m[i+1][j] {
                min = m[i+1][j+1]
            }
            m[i][j] = triangle[i][j] + min
        }
    }
    return m[0][0]
}

func main() {
    triangle := [][]int {
        {2},
        {3, 4},
        {6, 5, 7},
        {4, 1, 8, 3} }
    fmt.Println(  minimumTotal( triangle )  )
}

上面申請(qǐng)了一個(gè)二維的切片存儲(chǔ)子結(jié)構(gòu)的結(jié)果，但是實(shí)際上只需要保存最近的一組數(shù)據(jù)，歷史值已經(jīng)使用過不用再保存，所以只需要復(fù)用一個(gè)一維切片即可，可以減少存儲(chǔ)空間：

func minimumTotal(triangle [][]int) int {
    x := len (triangle)
    m := make([]int , x, x)

    for i:=0; i < x; i++ {
        m[i] = triangle[x-1][i]
    }

    for i:= x - 2 ; i >= 0; i-- {
        for j:=0; j < len (triangle[i]) ; j++ {
            min := m[j]
            if m[j+1] < m[j] {
                min = m[j+1]
            }
            m[j] = triangle[i][j] + min
        }
    }
    return m[0]
}

（2）給出一個(gè)一維整型數(shù)組，找出數(shù)組中乘積最大的連續(xù)子數(shù)組(子數(shù)組至少包含一個(gè)數(shù)字)，返回乘積。
前面幾個(gè)元素的最大乘積記為 max ，當(dāng)前元素記為 nums[i]：
如果 max > 0 && nums[i] > 0 ，則 max = max * nums[i] ，
如果 max <=0 0 && nums[i] > 0，則 max = nums[i]，
這里雖然是求最大乘積，但是考慮到負(fù)數(shù)，需要把最小乘積 min 也保存下來，所以這一題比上一題難的地方在于需要多保存一種狀態(tài)：
如果 max > 0 && min <= 0 && nums[i] < 0，負(fù)負(fù)得正，則 max = min * nums[i]。
如果 max <= 0 && min <= 0 && nums[i] < 0，由于 min 的絕對(duì)值比較大，則 max = min * nums[i]。
簡(jiǎn)單的說就是每一輪循環(huán)都從 max * nums[i] 、min * nums[i] 和 nums[i] 這三個(gè)值種找出最大值和最小值保存起來。

package main
import "fmt"

func maxMin(a int, b int, c int) (int,int) {
    var max, min int
    if a > b {
        max = a
        min = b
    } else {
        max = b
        min = a
    }
    if c > max {
        max = c
    } else if c < min {
        min = c
    }
    return max, min
}

func maxProduct(nums []int) int {
    n := len (nums)
    max := make([]int , n, n)
    min := make([]int , n, n)
    max[0], min[0] = nums[0], nums[0]
    result := nums[0]
    for i:=1; i < n; i++ {
        max[i], min[i] = maxMin(nums[i] * max[i-1], nums[i] * min[i-1], nums[i])
        if max[i] > result {
            result = max[i]
        }
    }
    return result
}

func main() {
    fmt.Println(  maxProduct( []int { -2, 3, -2 ,3} )  )
    fmt.Println(  maxProduct( []int { -2, 1, 2 ,3} )  )
    fmt.Println(  maxProduct( []int { -2, 0, -1} )  )
    fmt.Println(  maxProduct( []int { 0, 2} )  )
}

這里實(shí)際上只需要存儲(chǔ)當(dāng)前輪和前一輪的最大值、最小值即可，min 和 max 只需要定義為長(zhǎng)度為 2 的數(shù)組（或者直接用 2 個(gè)整型變量表示，比較具有可讀性）：

func maxProduct(nums []int) int {
    var result, maxPre, minPre, maxCur, minCur int
    result, maxPre, minPre = nums[0], nums[0], nums[0]
    n := len (nums)
    for i:=1; i < n; i++ {
        maxCur, minCur = maxMin(nums[i] * maxPre, nums[i] * minPre, nums[i])
        minPre = minCur
        maxPre = maxCur
        if maxCur > result {
            result = maxCur
        }
    }
    return result
}

（3）最長(zhǎng)上升子序列
注意：子序列并不要求連續(xù)。
這里會(huì)有一個(gè)誤區(qū)是：直接用一層循環(huán)，如果 nums[i] > nums[i-1] 就 dp[i] = dp[i-1] + 1,這樣計(jì)算是錯(cuò)誤的，例如數(shù)組是1,3,1,2,3，后面的三個(gè)元素都沒能大于第二個(gè)元素3，會(huì)得到 2 這個(gè)錯(cuò)誤的答案。
所以狀態(tài)應(yīng)該定義成：dp[i] 表示以 nums[i] 結(jié)尾的上升子序列的長(zhǎng)度，用兩層循環(huán)，計(jì)算 dp[i]時(shí)，要把下標(biāo) [0] 到 [i] 都遍歷一遍；

package main
import "fmt"

func lengthOfLIS(nums []int) int {
    n := len(nums)
    if 0 == n {
        return 0
    }
    result := 1

    dp := make([]int, n, n)
    for i:=0; i < n; i++ {
        dp[i] = 1
    }

    for i:=0; i < n; i++ {
        for j:=0; j < i; j++ {
            if nums[j] < nums[i] {
                if dp[j] + 1 > dp[i] {
                    dp[i] = dp[j] + 1
                }
            }
        }
        if dp[i] > result {
            result = dp[i]
        }
    }
    return result
}

func main() {
    fmt.Println( lengthOfLIS( []int{}) )
    fmt.Println( lengthOfLIS( []int{1,2}) )
    fmt.Println( lengthOfLIS( []int{1,2,4,1,3,5}) )
    fmt.Println( lengthOfLIS( []int{2,1}) )
    fmt.Println( lengthOfLIS( []int{1,3,1,2,3}) )
}

（4）零錢問題
給定不同面額的硬幣（用整型數(shù)組表示） 和目標(biāo)金額。
計(jì)算湊成目標(biāo)金額所需最少的硬幣數(shù)。無解時(shí)返回 -1。
假設(shè)有1/2/5三種面額硬幣，則 f(n) = 1 + min{ f(n-1), f(n-2), f(n-5) }
遞歸寫法：

func coin(coins []int, amount int) int {
    if amount == 0 {
        return 0
    }
    if amount < 0 {
        return -1
    }

    min := -1
    for j := len(coins)-1; j >= 0; j-- {
        if amount == coins[j] {
            return 1
        }
        ret := coin(coins, amount-coins[j])
        if ret < min || min == -1 {
            min = ret
        }
    }
    if min == -1 {
        return -1
    }
    return min + 1
}

這種寫法有大量重復(fù)計(jì)算，速度非常慢，計(jì)算coin( []int{1, 2, 5}, n) 當(dāng)n=30還好，當(dāng)n=40時(shí)已經(jīng)有明顯卡頓，當(dāng)n=45時(shí)大約需要一分鐘。
下面改為非遞歸寫法：

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount+1)
    for i := 1; i <= amount; i++ {
        dp[i] = -1
        for j:=len(coins)-1; j >= 0; j-- {
            if coins[j] > i || dp[i-coins[j]] == -1 {
                continue
            }
            if dp[i-coins[j]] + 1 < dp[i] || -1 == dp[i]{
                dp[i] = dp[i-coins[j]] + 1
            }
        }
    }
    return dp[amount]
}

（5）編輯距離
給出 2 個(gè)單詞，只能用 insert、delete、replace 三種操作，每次只能操作 1 個(gè)字符，目標(biāo)是使得 2 個(gè)單詞內(nèi)容相同，返回最少操作步數(shù)。
分析：設(shè)狀態(tài)為 dp[i][j] 表示單詞1 的前 i 個(gè)字符，最少花費(fèi)多少步可以得到單詞2 的前 j 個(gè)字符。
如果 word1[i-1] == word2[j-1] 則 dp[i][j] = dp[i-1][j-1]
否則 為下列三者的最小值加一
dp[i][j] = min { insert, delete, replace } + 1：
insert = dp[i-1][j]
delete = dp[i][j-1]
replace = dp[i-1][j-1]

func minDistance(word1 string, word2 string) int {
    n := len(word1)
    m := len(word2)
    dp := make([][]int, n+1)
    
    for i:=0; i <= n; i++ {
        dp[i] = make([]int, m+1)
        dp[i][0] = i   // init the special case
    }
    for i:=0; i <= m; i++ {
        dp[0][i] = i
    }
    
    for i := 1; i <= n; i++ {
        for j := 1; j <= m; j++ {
            if word1[i-1] == word2[j-1] {
                dp[i][j] = dp[i-1][j-1]
            } else {
                min := dp[i-1][j-1] // replace
                if dp[i][j-1] < min { // delete
                    min = dp[i][j-1]
                }
                if dp[i-1][j] < min { // insert
                    min = dp[i-1][j]
                }
                dp[i][j] = min + 1
            }
        }
    }
    return dp[n][m]
}