2.第一题用到了最长公共子序列的方法:
第二题:
定义f[i][j]为站点i到站点j的最少租金:
f[i][j] = min { f[i][k] + f[k][j] }
其中 i<k<j, 0<=i,j<=n-1
则最少租金为 f[0][n-1]
3.编程期间,没有遇到什么很大的问题,就是解题第一步需要想出递归方程,然后代码实现就简单很多了,不过第二题游艇问题,要得到最低开销,就得从最底层开始,逐渐向上计算每两个站之间最低开销,并记录在预先设定的数组中,两个站可能是相邻的,也可能是不相邻的。
原文:https://www.cnblogs.com/idjy/p/9903976.html