526互联

动态规划的套路

发布时间 2023-04-09 18:53:35作者: 小张的练习室

动态规划的试用前提

1. 无后效性

  • 一旦f(i,j)确定，就不用关心如何计算f(i,j)
  • 想要确定f(i,j)，只需要知道f(i-1,j)和f(i,j-1)的值。而至于他们如何计算出来，对当前或之后的任何子问题都没有影响
  • 过去不依赖将来，将来不影响过去

2. 最优子结构

  • f(i,j)定义就已蕴含了最优
  • 大问题的最优解可以由若干个小问题的最优解推出。（max，min，sum...）

DP能适用的的问题：能将大问题拆解成几个小问题，且满足无后效性、最优子结构性质。