Dynamic programming

28 Feb 2018

Model Definition

components

• 界定问题
• 子问题
• 递推公式
• 边界条件
• 复杂度

示例问题分析

n 阶台阶，每步 1或者2阶， 有多少种走法

这是一个 Fibonacci 问题

迭代公式: f(n) = f(n-1) + f(n-2)

边界条件: f(0) = 1 f(1) =1

字符串相似度(编辑距离)

二维 2D 动态规划