Ali VO 面试真题解析：最佳汇率换算（多次兑换与图最短路径）

Problem Description

We have a currency exchange requirement. Now we need to convert CNY to USD and hope to get as much USD as possible. Multiple exchanges are allowed, and only the optimal exchange rate matters.

For example, if CNY can first be converted to EUR and then converted to USD to get a better exchange rate, we need to find the optimal rate.

Example

Case 1

input = [{"src":"CNY","tar":"USD","rate":"0.16"},
         {"src":"CNY","tar":"EUR","rate":"0.14"},
         {"src":"EUR","tar":"USD","rate":"1.09"},
         {"src":"EUR","tar":"JPY","rate":"136.54"},
         {"src":"JPY","tar":"MYR","rate":"0.008"}]

output = 0.16

这道题本质上是一个有向加权图上的最优路径问题：每种货币是图中的节点，每一条汇率是从源币种到目标币种的一条边，边权表示兑换倍率。题目要求从 CNY 换到 USD 时获得尽可能多的 USD，并且允许经过中间货币多次转换，因此不能只看直接汇率，而要比较所有可达路径的乘积。常见做法是用 DFS/BFS 枚举可达路径并记录当前累计汇率，或把乘法转化为对数后用最短路径思路处理。示例中虽然存在 CNY -> EUR -> USD 的路径，但直接 CNY -> USD 的汇率 0.16 已经是最优，因此答案为 0.16。