租用游艇

租用游艇

题目描述

长江游艇俱乐部在长江上设置了 \(n\) 个游艇出租站 \(1,2,\cdots,n\)。游客可在这些游艇出租站租用游艇，并在下游的任何一个游艇出租站归还游艇。游艇出租站 \(i\) 到游艇出租站 \(j\) 之间的租金为 \(r(i,j)\)（\(1\le i\lt j\le n\)）。试设计一个算法，计算出从游艇出租站 \(1\) 到游艇出租站 \(n\) 所需的最少租金。
输入格式


第一行中有一个正整数 \(n\)，表示有 \(n\) 个游艇出租站。接下来的 \(n-1\) 行是一个半矩阵 \(r(i,j)\)（\(1\le i> n;        for(int i=1;i a[j];                        dp[j]=a[j];                        //建立一个初始最小租金                }        }        for(int i=1;i