題目描述 有一狹長的海島，島上交通線路只有一條公路，且公路上每隔一千米就有一個車站，每個車站都有同樣的乘車費用價目表（1~10 千米），且每一位乘客在任何一輛車上乘車不能超過 10 千米，但他途中可以換同方向的車多次。現有一乘客想乘車 n 千米，為使總費用最少，請你幫他求出最少的乘車費用 s。 注意：10 千米的費用比 1 千米少的情況是允許的。輸入 第一行共有 10 個不超過 200 的正整數，依次表示乘車 1～10 千米的費用，相鄰兩數間用一個空格隔開 第二行只有一個正整數：乘車的千米數 n輸出 只有一行且只有一個正整數：最少的乘車費用 s樣例輸入 12 21 31 40 49 58 69 79 90 101 15樣例輸出 147數據范圍限制 30% 的數據: 1 <= n <= 10 70% 的數據: 1 <= n <= 100 100% 的數據: 1 <= n <= 1 000提示 15 千米的路程，可以 5 千米、5 千米、5 千米分三次乘車；也可以 4 千米、5 千米、6 千米分三次乘車，其乘車的費用最少，s = 49+49+49 = 147 或 s = 40+49+58 = 147。

這一題，我看第一眼暴力枚舉？強行搜索?畢竟今天是來刷水題的，最后沒想到居然是用DP做出來了這題。

思路詳解

這題是一道十分簡單的一道DP題（反正我是用DP做的）。
f[i]表示行駛前i千米最少花的價格。
先枚舉1-n千米，再枚舉1-min（i，10）千米，表示走前面的j千米。
那么如果f[i-j]+a[j]<f[i]，也就是走前i-j千米加上走j千米的價格比之前算的走i千米的價格便宜，就把f[i]的值更新為f[i-j]+a[j]。
最后的答案就是f[n]。

核心代碼

if(f[i-j]+a[j]<f[i]) //如果走前i-j千米加上走j千米的價格比之前算的走i千米的價格便宜f[i]=f[i-j]+a[j]; //把f[i]的值更新為f[i-j]+a[j]

這題其實也是比較簡單的了。

代碼信息

時間復雜度總時間

Θ(n)	10n

總結

以上是生活随笔為你收集整理的乘车费用的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。