訓練數學感 94／演算法訓練 12 ─ 撿拾硬幣

http://4rdp.blogspot.com/2016/04/94-12.html?m=0

圖片引用 芭蕉葉上聽雨聲部落格

看到網友 Pizg 貼文：如何撿拾最多的硬幣，覺得這是一個非常不錯的演算法訓練的題目，因而收錄。

有一個矩形區域，格線中放有硬幣（圖中紅色的點）。
機器人開始是在區域的左下角落，他的任務是在穿越到右上角落的過程中盡可能撿起最多的硬幣。
然而，在每一個步驟中，限制機器人不能退後，只能往右或往上移動。
圖中藍線表示的最佳路徑，也就是機器人可以拾取最大數目的硬幣。

請試寫一程式求解某已知圖案之最佳路徑。


對計算格子有幾種走法有興趣的朋友，可以參考訓練數學感 52 ─ 最短路徑有幾種？一文。另外，覺得這題不太一樣的地方是在格子上放了許多已知位置的硬幣，我們只能走一次取得最多硬幣，好像機器人電量有限，每次只能走有限里程，要盡量一趟取得最多硬幣。

基本題，請計算 6 x 10 格有幾種走法？

加分題，現在每個格子都放一枚硬幣，從左下角往右上角只能往右往上走，然後機器人更換充飽後的電池，再從右上角往左下角走但只能往左及往下撿拾硬幣，請問來回要走幾趟才能把所有硬幣都撿完。

未來希望成為程式設計高手的人，應該試著寫程式看看。