I'm new to dynamic programming. So, I'm suppose to find the max profit. I don't think what I'm doing is correct. I don't understand what the k conversions is for. In the given example there are given 3 currencies, so therefore there are 3 conversion. Can someone please give me more ideas about how to solve this?
首先，让我们考虑一下有多少种货币交易。如果您有三种货币（我们称它们为英镑、法郎和马克），您就有六种可能的货币交易类型：英镑兑马克、马克兑英镑、英镑兑法郎、法郎兑英镑、法郎兑马克和马克兑法郎。
但就你的问题而言，当他们说你有 k 种货币交易时，他们的意思是允许你从某种货币开始，进行一系列 k 种货币交易。你的工作是找出哪 k 笔交易会带来最大的利润。因此，例如，如果您有三种货币，但 k=1，并且您被告知以英镑开头，那么您的任务很简单：决定是英镑兑法郎更好，还是英镑兑马克更好。如果 k=2，你有更多的选择，等等。
将其视为加权有向图可能会有所帮助，其中货币是节点，弧线由汇率加权。然后，您可以从节点 i 开始寻找长度为 k 的图形中最有利可图的路径来思考问题。
以这种方式思考它也会向您展示您表达中的问题，它应该看起来像沿着图表的路径，而不是您拥有的。您可能还考虑使用对数的某些属性，将其从乘法问题转变为加法问题。
最后，图结构上的动态编程通常涉及从长度为 n 的解构建长度为 n+1 的解，因此您可能应该从考虑可能的最小问题开始，以及它与第二小的问题的关系等.