动态规划算法

动态规划题目特点

1.计数

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

2.求最大最小值

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

3.求存在性

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

例题1：

动态规划四大步骤

1.确定状态

• 状态在动态规划中的作用属于定海神针

• 简单的说，解动态规划的时候需要开一个数组，数组的每个元素 f [i] 或者 f [i] [j] 代表什么

  • 类似数学题中，X , Y , Z代表什么

• 确定状态需要两个意识：

  • 最后一步
  • 子问题

例题1：最后一步的分析

例题：子问题的分析

2.转移方程

3.初始条件和边界情况

4.计算顺序

例题1_小结

例题2：Unique Paths

确定状态

转移方程

初始条件和边界情况

计算顺序