概念

• 每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

• 基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解

• 与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）

• 动态规划算法是通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或者说分治）的方式去解决。

• 动态规划算法的基本思想与分治法类似，也是将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。

• 与分治法不同的是，**适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。**若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。

• 动态规划实质上是一种以空间换时间的技术, 它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

应用场景

适用动态规划的问题必须满足最优化原理、无后效性和重叠性

1. 最优化原理（最优子结构性质） 最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。
2. 无后效性 将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。
3. 子问题的重叠性 动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。

示例

1. 台阶问题

• 问题：有n级台阶，一个人每次上一级或者两级，问有多少种走完n级台阶的方法？

• 分析：

  • 动态规划的实现的关键在于能不能准确合理的用动态规划表来抽象出 实际问题。在这个问题上，我们让f(n)表示走上n级台阶的方法数。
  • 那么当n为1时，f(n) = 1, n为2时，f(n) =2,就是说当台阶只有一级的时候，方法数是一种，台阶有两级的时候，方法数为2。
  • 那么当我们要走上n级台阶，必然是从n-1级台阶迈一步或者是从n-2级台阶迈两步，所以到达n级台阶的方法数必然是到达n-1级台阶的方法数加上到达n-2级台阶的方法数之和。即f(n) = f(n-1)+f(n-2)，我们用dp[n]来表示动态规划表，dp[i],i>0,i<=n,表示到达i级台阶的方法数。

• code

  package main
  import "fmt"
  func climbStairs(n int) int {
      if n == 1 {
          return 1
      }
      if n == 2 {
          return 2
      }
      dp := make([]int, n+1)
      dp[1] = 1
      dp[2] = 2
      for i := 3; i <= n; i++ {
          dp[i] = dp[i-1] + dp[i-2]
      }
      return dp[n]
  }
  func main() {
      n := 5
      fmt.Printf("There are %d ways to climb %d stairs.", climbStairs(n), n)
  }
  
  /*
  上面的示例代码中，我们首先判断n为1或2的情况，并返回相应的结果。然后，我们创建一个长度为n+1的dp数组，并将dp[1]和dp[2]初始化为1和2。接下来，我们使用状态转移方程dp[i] = dp[i-1] + dp[i-2]计算每个状态的值。最后，我们返回dp[n]，即为原问题的解。
  */
  

2. 最短路径

• 问题：给定一个矩阵m，从左上角开始每次只能向右走或者向下走，最后达到右下角的位置，路径中所有数字累加起来就是路径和，返回所有路径的最小路径和。如给定的m如下，那么路径1,3,1,0,6,1,0就是最小路径和，返回12.

  1 3 5 9
  
  8 1 3 4
  
  5 0 6 1
  
  8 8 4 0
  

• 分析：假设m是m行n列的矩阵，那么我们用dp[m][n]来抽象这个问题，dp[i][j]表示的是从原点到i,j位置的最短路径和。我们首先计算第一行和第一列，直接累加即可，那么对于其他位置，要么是从它左边的位置达到，要么是从上边的位置达到，我们取左边和上边的较小值，然后加上当前的路径值，就是达到当前点的最短路径。然后从左到右，从上到下依次计算即可。

• 代码：

  package main
  
  import (
  	"fmt"
  	"math"
  )
  
  func main() {
  	grid := [][]int{
  		{1, 1, 1, 1, 1, 0, 0, 0, 0, 0},
  		{0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
  		{0, 0, 0, 0, 1, 0, 0, 0, 0, 1},
  		{1, 0, 0, 0, 1, 0, 0, 0, 0, 0},
  		{0, 0, 0, 0, 1, 1, 1, 1, 1, 1},
  	}
  	ret := minPathSum(grid)
  	fmt.Println(ret)
  }
  
  func minPathSum(m [][]int) int {
  	row := len(m)
  	col := len(m[0])
  
  	dp := make([][]int, row)
  	for i := 0; i < row; i++ {
  		dp[i] = make([]int, col)
  	}
  	dp[0][0] = m[0][0]
  
  	// 给行初始化
  	for i := 1; i < row; i++ {
  		dp[i][0] = dp[i-1][0] + m[i][0]
  	}
  
  	// 给列初始化
  	for i := 1; i < col; i++ {
  		dp[0][i] = dp[0][i-1] + m[0][i]
  	}
  
  	// 给剩余元素初始化
  	for i := 1; i < row; i++ {
  		for j := 1; j < col; j++ {
  			dp[i][j] = int(math.Min(float64(dp[i-1][j]), float64(dp[i][j-1]))) + m[i][j]
  		}
  	}
  
  	return dp[row-1][col-1]
  }