假定你希望兑换外汇，你意识到与其直接兑换，不如进行多种外币的

假定你希望兑换外汇，你意识到与其直接兑换，不如进行多种外币的一系列兑换，最后兑换到你想要的那种外币，可能会获得更大收益。假定你可以交易n种不同的货币，编号为1,2,...,n，兑换从1号货币开始，最终兑换为n货币。对每两种货币i和j，给定汇率r_ij。意味着你如果有d个单位的货币i，可以兑换dr_ij个单位的货币j。进行一系列的交易需要支付一定的佣金，金额取决于交易的次数。令c_k表示k次交易需要支付的佣金。证明：如果对所有k=1,2,...,n,c_k=0，那么寻找最优兑换序列的问题具有最优子结构。然后请证明：如果佣金c_k为任意值，那么问题不一定具有最优子结构。