动态规划.md

• 鸣谢
  • lintcode-背包汇总
  • cuitianyi-背包九讲
  • 侯卫东-动态规划入门视频

why DP？

• 递归/回溯，有太多做了重复的计算，我们要避免这个问题
• 分治、动态规划的联系
  1. 动态规划和分治的相同点：都是将原问题分解为若干个规模较小的子问题，递归的求解这些子问题，然后合并子问题的解得到原问题的解。
  2. 不同点：分治一般用来解决子问题相互独立的问题。而动态规划用来解决子问题重叠的问题。所以，用动态规划能解决的问题分治策略肯定能解决，但是，运行时间更长。
• 贪心
  1. 贪心的典型应用有：Huffman编码、MST（如prim、kruskal）、单源最短路（如Dijkstra）
  2. 贪心的使用场景较小，是dp特例。所以，能用贪心来解的，也可以用dp来解。

三大DP题型、四个计算步骤

一、最值型

1. 换零钱：完全背包问题-求解最小的使用个数
   • 现有面值为2、5、7，最少用多少枚硬币，拼出27元？（力扣322）

• 计算步骤：4个组成部分

  1. 确定状态

     • 找最后一步
     • 子问题

  2. 转移方程

     • f[x]=min{ f[x-2]+1, f[x-5]+1, f[x-7]+1 }
     • f[x]表示，最少用多少枚硬币，拼出X元。1表示最后一枚硬币。

  3. 初始条件、边界情况

     1. 边界情况。如果f[x]下标为非法值，比如负数。就直接返回正无穷
        • f[x]= +∞ 表示，无法用硬币拼出X元。
     2. 初始值。这里，f[0]=0。为什么需要初始值？-----如果使用转移方程，那么f[0]=+∞。但是我们明明知道f[0]=0。所以，对于转移方程算不出来的、但是又需要的状态，就只能手工定义。（初始条件）

  4. 计算顺序

     • 初始条件f[0]=0
     • 计算f[0], f[1], ... , f[27] （这里是小->大）

  5. 时间复杂度 3*27.

二、计数型

1. 爬楼梯
2. 从左上角走到右下角，有多少种走法

三、存在性问题

1. 能否跳到数组最后一个位置

代码框架

# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)