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

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

• 取石子游戏，先手是否必胜
• 能不能选出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.最后一步不超过跳跃的最大距离：
• 子问题——青蛙能不能跳到石头
• 状态：设表示青蛙能不能跳到石头

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

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

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