动态规划

通过缓存子问题的结果来递推解决目标问题的解决方案

判断是否为动态规划问题的依据

  • 是否存在子问题的局部最优解为全局最优解的局部解
  • 是否可以找到状态（子问题与目标问题的规模n这个变量）
  • 是否存在状态转移方程（递推公式，即子问题规模从n到n+1，最优解的关系，例如f(n+1)=f(n)+2）
1
2
class A(object):
    ...