常见算法思想8：动态规划法

动态规划问题的分类

求最大最小值
- 从左上角走到右下角路径的最大数字和
- 最长上升子序列长度
计数
- 有多少种方式…
- 有多少种方法选出k个数使得和是sum
求存在性
- 取石子游戏，先手是否必胜
- 能不能选出k个数使得和是sum

常见动态规划问题的类型

坐标型动态规划(20%) ：二维数组下标就是坐标，如机器人路线问题
序列型动态规划(20%) ：
划分型动态规划(20%) ：给一个字符串或数组让划分成若干段满足一些性质
区间型动态规划(15%) ：选择连续区间而符合一定条件，f(i,j)
背包型动态规划(10%) ：一定空间的背包最多带多少物品的问题
最长序列型动态规划(5%) ：最长上升子序列等类似问题
博弈型动态规划(5%) ：博弈算出一个人是否必胜还是必败或者胜率问题
综合性动态规划(5%) ：综合前面类型或和其他算法结合
动态规划空间优化问题，如数组降维
动态规划打印路径问题，打印解

动态规划问题解决步骤

0.为解题的每一步开辟一个等容量的数组存储每一步的结果
1.确定状态
- 最后一步：研究最优策略的最后一步；
- 子问题：转换成可不断缩小规模的子问题；
2.转移方程
- 根据可不断缩小规模的子问题直接得到；
  - 求最值用统计函数min，max等
  - 求计数用累加
  - 求可行性用or and布尔运算
3.初始条件和边界情况
- 细心考虑周全，某些初始条件可直接得到结果；
4.计算顺序
- 使用数组存储每一步的计算结果，并在每一步利用之前的计算结果。

例题解析

一、求最值问题：

你有三种硬币，面值分别为2，5，7，每种硬币都有足够多。现在你需要买一本书需要27元，如何用最少的硬币组合正好付清，不需要对方找钱？

1.确定状态

状态在动态规划中的作用属于定海神针
简单地说，解动态规划需要开一个数组，数组的每个元素f[i]或者f[i][j]代表什么？
- 类似于解数学题中，x，y，z代表什么？
确定状态需要两个意识
- 最后一步
  - 虽然不知道最优策略是什么，但是最优策略肯定是k枚硬币a1，a2，…,ak，面值加起来是x
  - 所以一定有一枚最后的硬币：ak
  - 除掉这枚硬币，前面硬币的面值加起来是27-ak
  - 关键点1：不关心签名的k-1枚是怎样拼出27-ak的，而且现在还不知道ak和k，但是确定签名的硬币拼出了27-ak
  - 关键点2：因为是最优策略，所以拼出27-ak的硬币一定要最少。
- 子问题
  - 所以我们就要去：最少用多少枚硬币可以拼出27-ak
  - 原问题是最少用多少枚硬币拼出27
  - 把原问题规模变小成为一个子问题
  - 为了简化定义，我们设状态f(x) = 最少用多少枚硬币拼出x
  - 首先确定最后那枚硬币ak是多少：
    - 可能性：2，5，7
      - 如果是2,最后枚数：f(27)= f(27-2) + 1
      - 如果是5,最后枚数：f(27)= f(27-5) + 1
      - 如果是7,最后枚数：f(27)= f(27-7) + 1
    - 即f(27) = min{ f(27-2)+1, f(27-5)+1, f(27-7)+1}

2.转移方程

设状态f[x] = 最少用多少枚硬币拼出x
对于任意x： f[x] = = min{f[x-2]+1, f[x-5]+1, f[x-7]+1 }

3.初始条件和边界情况

f[x] = = min{f[x-2]+1, f[x-5]+1, f[x-7]+1 }
两个问题： x-2,x-5,x-7小于0怎么办？什么时候停下来？
如果不能拼出y，则定义f[y]= 正无穷
- 例如f[-1]=f[-2]=…=正无穷
所以f[1] = min{f[-1]+1, f[-4]+1, f[-6]+1} = 正无穷，表示拼不出来1
初始条件：f[0] = 0

4.计算顺序

拼出x所需要的最少硬币数：f[x] = min{f[x-2]+1, f[x-5]+1, f[x-7]+1 }
初始条件：f[0] = 0
然后计算f[1],f[1],…f[27]
当我们计算到f[x]时，f[x-2], f[x-5], f[x-7]都已经得到结果了。

func CoinChange(coinList []int, total int) int {
	// 0,....,n : [n+1]
	// 0,....,n-1 : [n]
	stepList := make([]int, total+1) // 存储每1元需要多少枚硬币的结果
	coinNum := len(coinList)         // 硬币的类型数量

	// 初始条件
	stepList[0] = 0

	var i, j int
	for i = 1; i <= total; i++{

		// 每一元的情况需要多少枚硬币,默认设置无穷大
		stepList[i] = math.MaxInt64
		// 最后一枚硬币 stepList[j]
		// stepList[i]= math.Min(stepList[i-coinList[j]])+1,stepList[i])
		for j = 0; j < coinNum; j++ {
			// total需大于硬币面值
			if i >= coinList[j] && stepList[i-coinList[j]] != math.MaxInt64 {
				// 转移方程
				stepList[i] = int(math.Min(float64(stepList[i-coinList[j]])+1, float64(stepList[i])))
			}
		}
	}

	if stepList[total] == math.MaxInt64 {
		stepList[total] = -1
	}

	return stepList[total]

}

二、求计数：

给定m行n列的网格，有一个机器人从左上角(0,0)出发，每一步可以向下或者向右走一步，问有多少种不同的方式走到右下角。

1.确定状态

最后一步：
- 无论机器人用何种方式到达右下角，总有最后挪动的一步：向右或向下；
- 右下角坐标设置为(m-1,n-1)
- 那么前一步机器人一定是在(m-2,n-1)或者(m-1,n-2)
子问题:
- 如果机器人有X种方式从左上角走到(m-2,n-1)，有Y种方式从左上角走到(m-1,n-2)，则机器人有X+Y种方式走到 - 如果机器人有X种方式从左上角走到(m-2,n-1)，有Y种方式从左上角走到(m-1,n-2)，则机器人有X+Y种方式走到(m-1,n-1)。 =》数学组合中的加法原理
- 问题转化为机器人有多少种方式从左上角走到(m-2,n-1)和(m-1,n-2)；
- 原题要求有多少种方式从左上角走到(m-1,n-1)。
- 转化子问题：状态：设f[i][j]为机器人有多少种方式从左上角走到(i,j)

2.转移方程

对于任一格子(i,j)：f[i][j] = f[i-1][j] + f[i][j-1]

3.初始条件和边界情况

初始条件：f[0][0] = 1，因为机器人只有一种方式到左上角
边界情况：i=0或j=0，则前一步只能由一个方向过滤：f[i][j] = 1

4.计算顺序

f[0][0] = 1
计算第0行：f[0][0]，f[0][1]，…,f[0][n-1]
计算第1行：f[1][0]，f[1][1]，…,f[1][n-1]
…
计算第m-1行：f[m-1][0]，f[m-1][1]，…,f[m-1][n-1]
答案是：f[m-1][n-1]
时间复杂度（计算步数）：O(MN)，空间复杂度（数组大小）：O(MN)

// 输入行列参数m,n
func UniquePaths(m, n int) int{
	// 开一个二维数组m行,存储走到当前每一格的可能性步数
	f := make([][]int, m, m)

	var i, j int
	for i = 0; i < m; i++ { // row:top to bottom
		// 每行开n列的数组
		f[i] = make([]int, n, n)
		for j = 0; j < n; j++ { // column:left to right
			if i == 0 || j == 0 {
				// 初始格为1
				f[i][j] = 1
			}else {
				// 转移方程:当前格 = 上一格往下的情况 + 上一格往右的情况
				f[i][j] = f[i-1][j] + f[i][j-1]
			}
		}
	}

	// 只需返回最后一格作为结果即可
	return f[m-1][n-1]
}

三、求可能性：

有n块石头分别在x轴的0,1,…,n-1位置，一只青蛙在石头0，想跳到石头n-1，如果青蛙在第i块石头上，它最多可以向右跳距离ai，问青蛙能否跳到石头n-1？例子：输入a=[2,3,1,1,4],输出true；输入a=[3,2,1,0,4],输出false;

1.确定状态

最后一步：
- 如果青蛙能跳到最后一块石头n-1，我们考虑它跳的最后一步
- 这一步从石头i跳过来，i<n-1
- 这需要两个条件同时满足：
  - 青蛙可以跳到石头i (不好判断)
  - 最后一步不超过跳跃的最大距离：n-1-i<=ai （好判断）
子问题:
- 我们需要知道青蛙能不能跳到石头i(i<n-1)
- 而我们原来要求青蛙能不能跳到石头n-1
- 状态：设f[j]表示青蛙能不能跳到石头j

2.转移方程

设f[j]表示青蛙能不能跳到石头j
f[j] = OR(f[i] AND i + a[i] >= j) (0<=i<j)
- f[j] : 表示青蛙能不能跳到石头j；
- 0<=i<j ：表示枚举上一个跳到的石头i；
- f[i] AND i ：表示青蛙能不能跳到石头i；
- a[i] >= j ：表示最后一步的距离不能超过ai

3.初始条件和边界情况

初始条件:设f[i]表示青蛙能不能跳到石头i
边界条件：f[0] = true，因为青蛙一开始就在石头0

4.计算顺序

设f[i]表示青蛙能不能跳到石头i
f[j] = OR(f[i] AND i + a[i] >= j) (0<=i<j)
f[0] = true
计算f[1],f[1],…f[n-1]
答案是f[n-1]
时间复杂度：O(N²)，空间复杂度（数组大小）：O(N)

func CanJump(list []int) bool {
	// 石头块数
	n := len(list)

	// 开辟数组,存储跳到每个石头的可能性
	canList := make([]bool, n, n)
	canList[0] = true // 初始位置0石头肯定可以

	// 从位置1开始
	for j := 1; j < n; j++ {
		canList[j] = false // 假设不可行

		// 从当前石头i开始
		// 最后一跳是i到j,j必须在i后面
		for i := 0; i < j; i++ {
			// 转移方程
			if canList[i] && i+list[i] >= j {
				canList[j] = true
				break
			}
		}
	}

	return canList[n-1]
}