动态规划

动态规划题目特点

1. 计数

• 有多少种方式走到右下角
• 有多少种方法选出k个数使得和是sum

2.求最大最小值

• 从左上角走到右下角路径的最大数字和
• 最长上升子序列长度

3.求存在性

• 取石子游戏，先手是否必胜
• 能不能选出k个数使得和是sum

动态规划四个组成部分：

• 确定状态
  • 研究最优策略的最后一步
  • 化为子问题
• 转移方程
  • 根据子问题定义直接得到
• 初始条件和边界情况
• 计算顺序
  • 利用之前的计算结果

最值型动态规划

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

动态规划组成部分一：确定状态

• 状态是动态规划的核心
• 解动态规划时需要定义一个数组，数组的每一个元素f[i]或者f[j][j]代表什么
• 确定状态需要两个意识：
  • 最后一步
  • 子问题

最后一步
1-不知道最优策略，但最优策略肯定是K枚硬币面值加起来是27
2-所以肯定有一枚最后的硬币：
  关键点1：不关心前面k-1枚硬币如何拼出，甚至不知道，但是确定了前面的硬币拼出了
  关键点2：因为是最优策略，所以拼出的硬币数一定要最少，否则矛盾。
子问题
1 - 需要求出最少用多少枚硬币可以拼出
2 - 原问题是最少用多少枚硬币拼出27
3 - 原问题转化成了一个规模更小的子问题：
4 - 设状态
最后一枚硬币只可能是2，5或7
若，应该是(加上最后的一枚硬币2)
若，应该是(加上最后的一枚硬币5)
若，应该是(加上最后的一枚硬币7)
要求最少的硬币数：

动态规划组成部分二：转移方程

• 设状态 最少用多少枚硬币拼出
• 对于任意，

动态规划组成部分三：初始条件和边界情况

• 时，
• 初始条件：

动态规划组成部分三：计算顺序

• 初始条件：
• 然后计算
• 大多数情况都是从小到大地算，这样当算时，前面的都已经算过了。

求最值型动态规划小结

• 1.确定状态
  • 最后一步（最优策略中使用的最后一枚硬币）
  • 化成子问题（最少的硬币拼出更小的面值
• 2.转移方程
  • 
• 3.初始条件和边界情况
  • ，如果不能拼出，
• 4.计算顺序
  • 

计数型动态规划

Unique Paths

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

动态规划组成部分一：确定状态

• 最后一步：机器人走到右下角之前的最后一步：向右或者向下
  
• 右下角坐标为(m - 1, n - 1)，那么前一步机器人一定是在(m - 2, n - 1)或者(m - 1, n - 2)
• 子问题 ——从左上角走到(m - 2, n - 1)和从左上角走到(m - 1, n - 2)；假设从左上角走到(m - 2, n - 1)有种方式，从左上角走到(m - 1, n - 2)有种方式，那么走到(m - 1, n - 1)就有种方式。
  问题转化为机器人有多少种方式从左上角走到(m - 2, n - 1)和(m - 1, n - 2)
• 状态：设为机器人有多少种方式从左上角走到

动态规划组成部分二：转移方程

• 对于任意坐标，

动态规划组成部分三：初始条件和边界情况

• 初始条件：，机器人只有一种方式到左上角
• 边界情况：，则前一步只能有一个方向过来

动态规划组成部分四：计算顺序

• 
• 计算第0行：
• 计算第1行：
• 
• 计算第m-1行：
• 答案是
  时间复杂度和空间复杂度都是

存在性型动态规划

有块石头分别在x轴的位置，一只青蛙在石头，想跳到石头，如果青蛙在第块石头上，它最多可以向右跳距离，问青蛙能否跳到石头。

动态规划组成部分一：确定状态

• 最后一步：如果青蛙能跳到最后一块石头，考虑它跳的最后一步是从石头跳过来的，
• 需要满足两个条件：1. 青蛙可以跳到石头 2.最后一步不超过跳跃的最大距离：
• 子问题——青蛙能不能跳到石头
• 状态：设表示青蛙能不能跳到石头

动态规划组成部分二：转移方程

• 设表示青蛙能不能跳到石头，

动态规划组成部分三：初始条件和边界情况

• 设表示青蛙能不能跳到石头
• 初始条件：，青蛙一开始就在石头

动态规划组成部分四：计算顺序

• 初始化
• 计算
• 答案是
  时间复杂度：，空间复杂度：