二维动态规划

  1. 云栖社区>
  2. 博客>
  3. 正文

二维动态规划

云栖希望。 2017-12-17 23:29:00 浏览518
展开阅读全文

给定N个点,任意两个点之间都联通,找出两条路径(涵盖所有点),使他们的和最小

首先把点从左往右编号0-n-1
那么原题相当于找两条从左往右的不想交的路线 
dp[i]表示两条路走到了i和i-1最少的花费是多少 
答案是dp[n-1]+cost[n-2][n-1] 
dp[1]=cost[0][1] 
dp[i]=min(dp[i-1]+cost[i-2][i], dp[i-2]+cost[i-2][i-1]+cost[i-3][i], dp[i-2]+cost[i-3][i-1]+cost[i-2][i])

本文转自博客园知识天地的博客,原文链接:二维动态规划,如需转载请自行联系原博主。

网友评论

登录后评论
0/500
评论
云栖希望。
+ 关注