長江游艇俱樂部在長江上設(shè)置了n 個(gè)游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一個(gè)游艇出租站歸還游艇。游艇出租站i 到游艇出租站j 之間(1≤i＜j≤n)的租金為r(i,j)。 編程任務(wù)： 求從游艇出租站1 到游艇出租站n所需的最少租金。
第1 行中有1 個(gè)正整數(shù)n（n<=200），表示有n個(gè)游艇出租站。
接下來是n-1 行，每行表示游艇站i到i+1、i+2、.......、n的租金，即r(i,i+1)、r(i,i+2)、......、r(i,n)。
兩行
第1行為一個(gè)整數(shù)，表示從游艇出租站1 到游艇出租站n所需的最少租金
第2行輸出從游艇出租站1 到游艇出租站n的最少總租金的路徑上的各個(gè)?？空?，中間用"-->"連接，先輸出第1個(gè)?？空?即為1，最后輸出第一個(gè)?？空?，即為n。如果有多種方案達(dá)成最少租金，則只輸出這種方案：從起點(diǎn)起，盡可能選擇最近的出租站以歸還游艇并重新租借游艇。
例如：輸入數(shù)據(jù)為
3
5 12
7
則： 1-->2-->3和1-->3這兩種方案都可以達(dá)到最少租金，但此題要求只輸出1-->2-->3這種方案。
3 5 15 7
12 1-->2-->3
大家先把題目熟悉一下，這些題目都有一定難度，今天或明天晚上會作個(gè)動態(tài)規(guī)劃的講課和講解。
另外，要先把回溯法復(fù)習(xí)一下，因?yàn)槲业膭討B(tài)規(guī)劃講解，是基于對回溯法的優(yōu)化的角度來講的。