学习笔记

• 动态递推
• 以递推的方式分解子问题
• 分治+最优子结构
• 找到重复子问题

1. 定义重复性(分治)
2. 定义状态数组
3. DP方程

• 共性：重复子问题
• 最优子结构、中途可以淘汰次优解

1. opt[i, j] = opt[i + 1, j] + opt[i, j + 1]; if a[i, j] = '空' opt[i, j] = opt[i + 1, j] + opt[i, j + 1]; else opt[i, j] = 0

1. 最优子结构 opt = best_of(opt[n - 1], opt[n - 2], ...)
2. 储存中间状态 opt[i]
3. 递推公式

• Fib： opt[n] = opt[n - 1] + opt[n - 2]
• 二维路径： opt[i, j] = opt[i + 1, j] + opt[i, j + 1]（且判断是否为空地）