如何理解动态规划
动态规划比较合适的就是来求最优问题的，比如求最大值，最小值等等。它可以显著的降低时间复杂度。想要理解动态规划问题，还是需要先理解回溯。前面讲到了回溯的特点 就是高级了一丁点的穷举。
那么如何优化呢
回溯的传送门：回溯
在回溯的例子中提到了 0-1 背包问题，其实可以将 0-1 背包问题中的树分为一个二叉树，其实前面也已经讲过了。假设有一个物品列表 { 2 , 2 , 4 , 6 , 3 }, 这个树的每一个节点表示一种状态，用（i,cw）表示，其中 i 为当前要决策的物品下标，cw为当前的重量。比如（2，2）就表示当前要决策第2个物品要放入吗，当前的重量为2。
不难发现其实（2，2）和（3，4 ）都重复出现了，如果将已经计算过的状态都缓存起来，那么就能省去很多的计算。
动态规划的实质是将一个问题分解为多个阶段，每个阶段决策一个物品是否会放到一个背包之中，当然这个物品放与不放都会有十分多种可能的重量，比如上图的第2号物品，如果我选择的是放入,那么就整个重量就有4种可能了。如下图：
也就是有 3种可能，4，6，8 其中6状态重复了
接下来就是重复状态的合并，只记录不同的结果状态，也就是 4，6，8。去掉了重复的6。
重新理一遍
物品列表是 2 , 2 , 4 , 6 , 3
第0个物品的重量是2，要么装入背包要么不装入。分别用下面的方法计入
status [0,2] 和 status[0,0]
第1个物品的重量是2，要么装入背包要么不装入。重量可能是 0+0, 0+2, 2+0, 2+2 ，分别用下面的方法计入
status [1,0] status [1,2] status[1,4]
以此类推，那么直至所有的物品都被判断， 那么 status [x,y] y最大就是最多能装多重的物品（y为当前重量）
转化为下图为 (纵轴为当前的物品index，横轴为当前重量)
转化为代码就可以看到
type Knapsack struct {
MaxWeight int
Items []int
}
type ItemInKnapsack struct {
itemIndex int
itemCurWeight int
}
func (k *Knapsack) PutItemInKnapsack() {
status := make(map[ItemInKnapsack]bool,10)
if k.Items[0] <= k.MaxWeight { // 第一行比较特殊，因为它没有上一行，所以这里直接标记
status[ItemInKnapsack{0,k.Items[0]}] = true
}
for i := 1 ;i < len(k.Items);i++ {
for j := 0; j <= k.MaxWeight;j++ { // 第i个物品我不放
if _,ok := status[ItemInKnapsack{i-1,j}];ok { // 将上一行的内容都填入本行
status[ItemInKnapsack{i,j}] = status[ItemInKnapsack{i-1,j}]
}
}
for j := 0; j <= k.MaxWeight - k.Items[i];j++ { // 第i个物品能放入的情况下，我放入了
if _,ok := status[ItemInKnapsack{i-1,j}];ok { // 将上一行的内容加上第i件物品的重量放入到本行
status[ItemInKnapsack{i,j+k.Items[i]}] = true
}
}
}
max := 0
for k := range status {
if k.itemCurWeight >= max {
max = k.itemCurWeight
}
}
fmt.Printf("最大能放入 %d kg 的物品",max)
}
执行一下
func main() {
items := []int{2,2,4,6,3}
k := DynamicProgramming.Knapsack{MaxWeight:9,Items:items}
k.PutItemInKnapsack()
}
执行结果：
最大能放入 9 kg 的物品
下面以一个leetcode的题目为例。
如 53题 最大子序和
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray
利用动态规划来解决。
假设先将第一个元素加入观察，
f(0) = -2
f(1) = max( f(0) + 1 , 1 )
f(2) = max(f(1)+(-3) , (-3) )
以此类推，能得到 f(n) = max(f(n-1)+ nums[n] , nums[n]) , f(n) 表示当第n个元素被插入后，当前最大的子序和是多少。
f(n) 可以理解为 第n个元素加进来的话，是连着之前的子序列大，还是从头（从当前的n）重新计算的子序列大
那么既然我们都知道了 f(0), f(1), f(2), f(3) ... 那在这些里面挑出，看谁最大，不就得出子序和最大了的么。
func maxSubArray(nums []int) int {
MaxSum := nums[0] // 这个数组记录着历史上出现过的最大的字序和
curMaxSum := nums[0] // 当前这个数被插入时，最大的子序和
for i := 1; i < len(nums); i++ {
curMaxSum = int(math.Max(float64(curMaxSum+nums[i]),float64(nums[i]))) // 公式 f(n) = max(f(n-1)+ nums[n] , nums[n]) , f(n)
MaxSum = int(math.Max(float64(MaxSum),float64(curMaxSum))) // 在f(n) 中找到最大的
}
return MaxSum
}
如果不直观，还可以这么写(其实原理都是一样的)
func maxSubArray(nums []int) int {
curMaxSum := 0
allMaxSum := nums[0]
for _,v := range nums {
if curMaxSum < 0 {
curMaxSum = v // 小于0，直接设置为该值，意味着又需要重新计算了
}else {
curMaxSum = curMaxSum + v // 大于0，这个值是有利的，加到当前值中
}
allMaxSum = int(math.Max(float64(allMaxSum),float64(curMaxSum)))
}
return allMaxSum
}
那么再看一题目
198 题 打家劫舍
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例 1:
输入: [1,2,3,1]
输出: 4
解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。
示例 2:
输入: [2,7,9,3,1]
输出: 12
解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/house-robber
这道题变了一下不再是要求连着的数组，而是要求不能相连。那么按老套路推导出递推公式。在第n间房打劫的最大数要么是 n-1 间的最大值（当前间不打劫），要么是 n-2 间 加上当前间的 最大值。
举例： 1号房间的最大值为3,即 dp[1]=3。 2号房间的最大值为4 即 dp[2]=4。3号房间的自身价值是 2，即num=2. 那么dp[3] = MAX( dp[2], dp[1] + num ) = MAX(4, 3+2) = 5
动态规划方程 dp[n] = MAX( dp[n-1], dp[n-2] + nums[n-1] )
dp[n]的含义是打劫上一家(n-1)，当前的第n家不打劫了，或者打劫上上家(n-2)和当前家的第n家（中间空1个）
if len(nums) == 0 {
return 0
} else if len(nums) == 1 {
return nums[0]
}
dp := make([]int,len(nums))
dp[0] = nums[0] // 起始化的 dp[n-2]
dp[1] = int(math.Max(float64(nums[0]),float64(nums[1]))) // 起始化的 dp[n-1]
for i := 2;i < len(nums);i++ {
dp[i] = int(math.Max(float64(dp[i-2]+nums[i]),float64(dp[i-1]))) // 打劫上上家(n-2)和当前家的第n家（中间空1个）或者 打劫上一家(n-1)，当前的第n家不打劫
}
max := 0
for _,v := range dp {
if max < v {
max = v
}
}
return max
再来一道题
746 题 使用最小花费爬楼梯
数组的每个索引做为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。
每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。
您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。
示例 1:
输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
示例 2:
输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：
cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs
这道题的意思和打家劫舍有些类似，不过这里可以是相连的了，不相连的话也最多中间间隔一个，那么这个问题同样是写出递推公式，在第n个楼梯，是跳过不选呢，还是选择这个楼梯，即要么是 n-1 加上当前 ，要么是 n-2 加上当前，看谁小，也就是n-1和n-2 谁小。
由此得到递推公式 dp[n]=min(dp[n-1],dp[n-2]) + nums[n]
dp[n]表示当前第n个楼梯是肯定要爬的了，那爬这楼梯之前有可能是跨一阶，也有可能是跨两阶
func minCostClimbingStairs(cost []int) int {
dp := make([]int,len(cost))
if len(cost) < 2 {
return 0
}
dp[0] = cost[0]
dp[1] = cost[1]
for i := 2;i < len(cost); i ++ {
dp[i] = int(math.Min(float64(dp[i-1]),float64(dp[i-2]))) + cost[i]
}
return int(math.Min(float64(dp[len(dp)-1]),float64(dp[len(dp)-2])))
}
由以上的例子可以发现，动态规划分为了两种，一种是通过回溯演进而来。另一种是通过动态规划方程而来。
没错。动态规划的最关键的两点就是
1、状态转移表法
先回溯，再找规律，看是否能合并子问题，如上面的 0-1 背包问题。正确的解题思路就是先回溯，再加缓存解决。
2、状态转移方程法
找规律，这类问题通常就是其最优结构依赖于其最优的子结构。通过分析当前状态和其子结构的关系，得出动态规划方程，代入到方程式中。
动态规划问题的特点
1、最优子结构
可以通过子问题的最优解，推导出当前问题的最优解
2、无后效性
现在的最优解和以后要发生的事没有关系
3、重复子问题
每个问题的最优解反反复复都是同样的解法，就是找当前的最优子结构。
