C/C++算法：计算长江游艇租赁最低费用

本实验报告研究了在C/C++语言下解决租用游艇问题的算法设计。问题背景是长江游艇俱乐部设有n个游艇出租站，游客可以从任意一个出租站租赁游艇并返回下游的任何站点。租金r(i, j)表示从出租站i到出租站j的费用，且1≤i<j≤n。目标是计算从出租站1到出租站n的最低总租金。 实验的核心是寻找从起点1到终点n的最短路径，这可以通过动态规划的方法实现。关键在于使用备忘录（记忆化搜索）技术，避免重复计算。备忘录表w[i]存储了从1到i位置的最短路径成本，通过迭代过程更新每个节点的最短路径。在`solve()`函数中，从出租站h开始，遍历其后所有的节点k，将当前出租站到k的成本加上k到n的最短路径成本取最小值，作为新的最短路径。当h等于n-1时，到达终点，返回此时的最短路径。 输入部分提供了包含出租站数量和对应租金的文件input.txt，例如： - 第一行是一个正整数n（最多200个站点）。 - 接下来的n-1行分别给出两个站点之间的租金r(i, j)。 输出文件output.txt会显示从1到n的最低总租金。例如，输入文件`input.txt`中的数据，经过算法计算后，输出可能为`output.txt`中的12，表示从1到n的最低总租金为12。 整个实验的重点是设计并实现一个高效的算法，通过递推和数据结构优化来求解这个问题，最终在C/C++代码中体现出来。通过这个过程，学生不仅锻炼了算法设计能力，也提升了程序编程和数据结构的理解。