一、題目

有一個(gè)N x N的方格,每一個(gè)格子都有一些金幣,只要站在格子里就能拿到里面的金幣。你站在最左上角的格子里,每次可以從一個(gè)格子走到它右邊或下邊的格子里。請(qǐng)問如何走才能拿到最多的金幣。

第一行輸入一個(gè)正整數(shù)n。
以下n行描述該方格。金幣數(shù)保證是不超過(guò)1000的正整數(shù)。

輸出最多能拿金幣數(shù)量。

二、解題思路

開始想著從左上走到右下，可以用深度搜索試試。但是搜索出來(lái)的結(jié)果需要都記錄下來(lái)，還要再比較大小，可能用的時(shí)間會(huì)很長(zhǎng)，后來(lái)轉(zhuǎn)念一想，既然是求最大收益，不如用DP。

DP數(shù)組可以設(shè)置大一點(diǎn)，因?yàn)閿?shù)據(jù)約定n<=1000,所以直接設(shè)置DP[1000+10][1000+10]。這樣還需要轉(zhuǎn)移方程，DP[i][j]是經(jīng)過(guò)（i，j）時(shí)最大金幣數(shù)。而我們行進(jìn)是只可以向右和向下，所以本最大收益是有兩種情況，一種是從上邊下來(lái)得到的，另一種是從左邊過(guò)來(lái)得到的，所以最終轉(zhuǎn)移方程如下：

三、完整代碼