关于拆点法和DP
博客专区 > m2012 的博客 > 博客详情
关于拆点法和DP
m2012 发表于6年前
关于拆点法和DP
  • 发表于 6年前
  • 阅读 89
  • 收藏 0
  • 点赞 0
  • 评论 0

【腾讯云】买域名送云解析+SSL证书+建站!>>>   

拆点法和DP增加维数,动机是一样的,就是状态表示太粗糙,以至于无法转移或者求出问题的答案,所以要将一个状态拆成多个更细更具体的状态,一般的做法是,缺啥就添啥,也就是说,如果你发现:“咦,由于我不知道因素x的情况,所以我没办法转移。”ok,那你就可以尝试把因素x作为一维加到状态的表示里去。  

DP可以简单分成两种,最优化DP 和 可行性DP。有时候,如果我们没办法使用最优化DP来解决问题,那就只能通过可行性DP将可行解算出来,最后再筛选出最优解。最优化DP退化成可行性DP的时候,状态表示一般要添加新的维度。如果可以用最优化dp解决的话,尽量用最优化dp,因为最优化dp的计算过程本身就包括了可行性dp。

联想一下编译原理里面,实现一个正规表达式的状态机的时候,里面提到的概念。

 

  • 打赏
  • 点赞
  • 收藏
  • 分享
共有 人打赏支持
粉丝 16
博文 128
码字总数 52548
×
m2012
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: