問題描述

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

輸入格式

　　第一行輸入一個正整數n。
　　以下n行描述該方格。金幣數保證是不超過1000的正整數。

輸出格式

　　最多能拿金幣數量。

解題思路

因為要求最多能拿多少金幣，所以就想到了貪心，每次都從右邊或下邊選最大的那個，但這樣并不合理，可能會錯過最佳選擇；還有就是聯想到了AOE網，能不能倒著從終點往回找。最后的思路來自知乎用戶 一棵小樹，對每一個方格都考慮其上方和左邊哪個更大，把大的那個金額加到現在的這個方格，代碼如下。

滿分代碼

注意！！！我在之前就發現用變量定義的二維數組在初始化時必須使用雙層的for循環，這次也是一樣，而且必須全都初始化了結果才不會錯。

#include <stdio.h>int main(void){int n;scanf("%d",&n);int a[n+1][n+1];int i=0,j=0;for(i=0;i<=n;i++){for(j=0;j<=n;j++)a[i][j]=0;}for(i=1;i<=n;i++){for(j=1;j<=n;j++)scanf("%d",&a[i][j]);}for(i=1;i<=n;i++){for(j=1;j<=n;j++)a[i][j]+=  a[i][j-1]>a[i-1][j] ? a[i][j-1]:a[i-1][j];}printf("%d",a[n][n]);return 0;
}

最后，種一棵樹最好的時機是在十年前，第二好的時機是現在。?