POJ.1163 The Triangle

Problem:
http://poj.org/problem?id=1163

Idea:
Using dp method, like at every point, choice the max ancestor's path.

Source:

 
 int n;  
 int g[111][111];  
 int main()  
 {  
      cin >> n;  
      for (int i = 0; i < n; i++) {  
           for (int j = 1; j <= i + 1; j++) {  
                cin >> g[i][j];  
           }  
      }  
      for (int i = 1; i < n; i++) {  
           for (int j = 1; j <= i + 1; j++) {  
                g[i][j] += max(g[i - 1][j - 1], g[i - 1][j]);  
           }  
      }  
      int ans = 0;  
      for (int j = 0; j < n + 2; j++) ans = max(ans, g[n-1][j]);  
      cout << ans << endl;  
      return 0;  
 }