P1359 Yacht Rental

The Yangtze River Yacht Club has set up $n$ yacht rental stations $1,2,\dots,n$ along the Yangtze River. Tourists can rent a yacht at any of these stations and return it at any downstream station. The rent between yacht rental station $i$ and yacht rental station $j$ is $r_{i,j}$ ($1\le i\lt j\le n$). Design an algorithm to compute the minimum total rent needed to travel from yacht rental station $1$ to yacht rental station $n$.

The first line contains a positive integer $n$, indicating there are $n$ yacht rental stations. The next $n-1$ lines give a half matrix $r_{i,j}$ ($1\le i

Output the minimum total rent required to travel from yacht rental station $1$ to yacht rental station $n$.

$1\le n\le 200$, and it is guaranteed that at any time during the computation, all numbers do not exceed $10^6$. Translated by ChatGPT 5