#include <algorithm> #include <iostream> #include <string> #include <vector> using namespace std; int main(void) { int arr[1000][1000] = {0}, dp[1000][1000] = {0}; int n; while (cin >> n && n != 0) { for (int i = 0; i < n; i++) { for (int j = 0; j <= i; j++) { cin >> arr[i][j]; if (i == n - 1) dp[i][j] = arr[i][j]; } } for (int i = n - 1; i > 0; i--) { for (int j = 0; j < i; j++) { dp[i - 1][j] = min(dp[i][j] + arr[i - 1][j], dp[i][j + 1] + arr[i - 1][j]); } } cout << dp[0][0] << endl; } } |
Double click to view unformatted code.