一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 673|回复: 5
收起左侧

[动态规划] 用动态规划怎么做这道《The Cheapest Flight》

[复制链接] |只看干货 |动态规划, 刷题
我的人缘0

升级   49.71%


分享帖子到朋友圈
李浩泉 | 显示全部楼层 |阅读模式
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (1333)
 
 
7% (107)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x

谁可以讲讲,动DP怎么做这道题吗?

"We need to fly home as cheaply as possible so that more money is left for gifts. Aunt Lidia asked for different kinds of cheeses, and Vasya wanted a new toy car. I’ve been looking at the schedule for quite a while and I’m starting to think that some planes are flying in vain".

As the input you get the flight schedule as an array, each element of which is the price of a direct flight between 2 cities (an array of 3 elements - 2 city names as a string, and a flight price).

Planes fly in both directions and the price in both directions is the same. There is a possibility that there are no direct flights between cities.

Find the price of the cheapest flight between cities that are given as the 2nd and 3rd arguments.

Input: 3 arguments: the flight schedule as an array of arrays, city of departure and destination city.

Output: Int. The best price.

Example:

cheapest_flight([['A', 'C', 100],
  ['A', 'B', 20],
  ['B', 'C', 50]],
'A',
'C') == 70
cheapest_flight([['A', 'C', 100],
  ['A', 'B', 20],
  ['B', 'C', 50]],
'C',
'A') == 70

评分

参与人数 1大米 +2 收起 理由
14417335 + 2

查看全部评分


上一篇:面试比较难的公司需要准备什么程度的数据结构呢?
下一篇:3Sum With Multiplicity 解法的效率问题
我的人缘0

升级   21.57%

本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   96% (1396)
 
 
3% (55)    👎
这个题动态规划就是bellman-ford维护从src经过0-k条边到任意节点的最短路径,对经过的edge数目进行规划
回复

使用道具 举报

我的人缘0

升级   62.5%

SHALLWEFZUW 2020-8-16 12:37:26 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (75)
 
 
0% (0)    👎
典型的Dijistra 把。

你说的dp可能是Memo DFS的方法? (top down)
int dfs(start, end, graph, seen, cache)
回复

使用道具 举报

我的人缘0

升级   49.71%

 楼主| 李浩泉 2020-8-16 13:24:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (1333)
 
 
7% (107)    👎
SHALLWEFZUW 发表于 2020-8-16 12:37
典型的Dijistra 把。

你说的dp可能是Memo DFS的方法? (top down)


刚看完九章的侯卫东讲的动态规划,他说求最优解的时候要用动态规划。你说的dijkstra算法,如下:

[Python] 纯文本查看 复制代码
from collections import defaultdict
from math import inf

def cheapest_flight(costs, a, b):
    G = defaultdict(set)
    w, d = {}, {}
    for u, v, cost in costs:
        G[u].add(v)
        G[v].add(u)
        w[u,v] = w[v,u] = cost
        d[u] = d[v] = inf
    d[a] = 0
    while d:
        u = min(d, key=d.get)
        if u == b:
            return d[u]
        if d[u] == inf:
            return 0
        for v in G[u]:
            if v in d:
                d[v] = min(d[v], d[u] + w[u,v])
        del d[u]


回复

使用道具 举报

我的人缘0

升级   49.71%

 楼主| 李浩泉 2020-8-16 13:27:15 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   92% (1333)
 
 
7% (107)    👎
SHALLWEFZUW 发表于 2020-8-16 12:37
典型的Dijistra 把。

你说的dp可能是Memo DFS的方法? (top down)


刚看完侯卫东的讲座,他说求最优解要想到动态规划。这道求最优机票价格的题是旅游网站DE/SDE的通用考题。

你说的dijkstra算法,如下:

[Python] 纯文本查看 复制代码
from collections import defaultdict
from math import inf

def cheapest_flight(costs, a, b):
    G = defaultdict(set)
    w, d = {}, {}
    for u, v, cost in costs:
        G[u].add(v)
        G[v].add(u)
        w[u,v] = w[v,u] = cost
        d[u] = d[v] = inf
    d[a] = 0
    while d:
        u = min(d, key=d.get)
        if u == b:
            return d[u]
        if d[u] == inf:
            return 0
        for v in G[u]:
            if v in d:
                d[v] = min(d[v], d[u] + w[u,v])
        del d[u]


回复

使用道具 举报

我的人缘0

升级   18.5%

baonudesifeizha 2020-10-2 23:39:01 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   86% (236)
 
 
13% (38)    👎
最短路就是图上的动♂态♂规♂划        
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表