算法导论上说过DP的两种形式
一种是我们常见的
一种就是以搜索的形式出现的

• 对，都是利用了最优子结构，但是....... (33) TN 2005-04-24 16:38:58
  • 我是觉得写成搜索的样子比较好写，不用考虑dp的顺序 (75) kicc 2005-04-24 16:43:38
    • 说错了，不是1054，是1038 (87) kicc 2005-04-24 16:44:37
      • 为什么会快呢？ (0) TN 2005-04-24 16:45:10
        • 直接DP的话，所有状态都要计算，但是可能有些状态最终是不用的，就是这个原因 (0) kicc 2005-04-24 16:46:38
          • 如果搜索的话应该也是每个状态都要计算的 (37) TN 2005-04-24 16:48:08
    • 1054其实是有严格的O(N^2)的算法的 (87) TN 2005-04-24 16:44:42