題目描述

輸入為 m×n 大小的的陣列，每一格是一個介於 0 與 10 之間的整數，表示經過這格可以累積的金幣數量。
你必須從最左上角的位置開始，走到最右下角的位置結束。
過程中每一步可以選擇「往右走」或「往下走」。
請你算出最多可以獲得的金幣總數。

輸入格式

第一行輸入兩個正整數 m,n(1≤m≤10,1≤n≤10), 數值之間用空格分隔。

接下來輸入 m 行，每行包含 n 個介於 0 與 10 之間整數, 數值之間用空格分隔。即第 i 行的第 j 個數字表示在 (i,j) 位置可以得到的金幣數量。

輸出格式

輸出最多可以獲得的金幣總數

Samples

["3 3\r\n5 0 4\r\n1 2 3\r\n5 0 2","6 6\r\n1 0 0 0 0 10\r\n1 0 0 0 0 0\r\n1 0 0 0 0 0\r\n1 0 0 0 0 0\r\n1 0 0 0 0 0\r\n1 1 1 1 1 1","2 4\r\n0 1 3 2\r\n3 2 5 0"]

["14","12","10"]

提示

import itertools

參考網址：https://ithelp.ithome.com.tw/articles/10221633

原始資料

• Zero1 題號：a561
• Hydro 題號：Z0561
• Locale：zh_TW
• Display：open