动态规划问题的分类
-
求最大最小值
- 从左上角走到右下角路径的最大数字和
- 最长上升子序列长度
-
计数
- 有多少种方式...
- 有多少种方法选出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]
}
