设为首页收藏本站
开启辅助访问 切换到窄版
搜索
第一问答网»论坛 › 中问网 › 问答 › ACM 游船费问题 关于动态规划的疑问

ACM 游船费问题 关于动态规划的疑问

[复制链接]
查看11 | 回复1 | 2013-3-25 08:07:53 | 显示全部楼层 |阅读模式
第二种做法完全正确。假设在“从i到j花费最少价钱的路线”中，j前的一站是k，那么这种做法就必然可以取到正确答案。因为在i到j的最优路线中，从i到k的路线选取也必然是最优的。另外必须理解的是，采取第二种做法后，当i!=0时，m[j]既不用求得，也不需要用它推导其它量，m[j]只有当i=0时才有用，所以m数组直接简化为一维就可以了，所以第二种方程的实质就是最好的方法。时间复杂度O(N^2)，不可能继续优化。是一道最简单的DP，没什么难的。。算法正确性可以严格证明，但在ACM里一般找找反例多想一想就行了...
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

千问

主题

0

回帖

4882万

积分

论坛元老

Rank: 8Rank: 8

积分
48824836
回复楼主 返回列表
热门排行