1、简介
动态规划（Dynamic Programming，DP）是求解决策过程最优化的过程，把原始问题划分成一系列子问题，以分治的方法找出最优解。
如果没有最优子结构，就等同于回溯，比如斐波拉契数列；
如果局部最优解就是全局最优解，就等同于贪心算法，
比如钱币的问题，如何用最少张纸币匹配出某个数字？
如果用 10/5/1 这三种面额配 16 元，贪心算法用 10+5+1 凑出来是可以的；
但是如果用10/8/1 这三种面额匹配16元，贪心算法只能用 10+1+1+1+1+1+1，而显然最优解是 8+8，此时只能用动态规划，而贪心法比较有局限性。
2、题目
（1）给出一个三角形（用二维数组表示），找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上（a[i][j] 的下一层相邻结点有 a[i][j] 和 a[i][j+1] ）。
可以先用一个二维数组存储中间结果，从最下面一层开始，逐步往上递推：
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 ) )
}
上面申请了一个二维的切片存储子结构的结果，但是实际上只需要保存最近的一组数据，历史值已经使用过不用再保存，所以只需要复用一个一维切片即可，可以减少存储空间：
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）给出一个一维整型数组，找出数组中乘积最大的连续子数组(子数组至少包含一个数字)，返回乘积。
前面几个元素的最大乘积记为 max ，当前元素记为 nums[i]：
如果 max > 0 && nums[i] > 0 ，则 max = max * nums[i] ，
如果 max <=0 0 && nums[i] > 0，则 max = nums[i]，
这里虽然是求最大乘积，但是考虑到负数，需要把最小乘积 min 也保存下来，所以这一题比上一题难的地方在于需要多保存一种状态：
如果 max > 0 && min <= 0 && nums[i] < 0，负负得正，则 max = min * nums[i]。
如果 max <= 0 && min <= 0 && nums[i] < 0，由于 min 的绝对值比较大，则 max = min * nums[i]。
简单的说就是每一轮循环都从 max * nums[i] 、min * nums[i] 和 nums[i] 这三个值种找出最大值和最小值保存起来。
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} ) )
}
这里实际上只需要存储当前轮和前一轮的最大值、最小值即可，min 和 max 只需要定义为长度为 2 的数组（或者直接用 2 个整型变量表示，比较具有可读性）：
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）最长上升子序列
注意：子序列并不要求连续。
这里会有一个误区是：直接用一层循环，如果 nums[i] > nums[i-1] 就 dp[i] = dp[i-1] + 1,这样计算是错误的，例如数组是1,3,1,2,3，后面的三个元素都没能大于第二个元素3，会得到 2 这个错误的答案。
所以状态应该定义成：dp[i] 表示以 nums[i] 结尾的上升子序列的长度，用两层循环，计算 dp[i]时，要把下标 [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）零钱问题
给定不同面额的硬币（用整型数组表示） 和目标金额。
计算凑成目标金额所需最少的硬币数。无解时返回 -1。
假设有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
}
这种写法有大量重复计算，速度非常慢，计算coin( []int{1, 2, 5}, n) 当n=30还好，当n=40时已经有明显卡顿，当n=45时大约需要一分钟。
下面改为非递归写法：
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 个单词，只能用 insert、delete、replace 三种操作，每次只能操作 1 个字符，目标是使得 2 个单词内容相同，返回最少操作步数。
分析：设状态为 dp[i][j] 表示单词1 的前 i 个字符，最少花费多少步可以得到单词2 的前 j 个字符。
如果 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]
}
网友评论