Posted on 2014-01-11 02:43
Uriel 閱讀(104)
評論(0) 編輯 收藏 引用 所屬分類:
LeetCode
給一個三角形陣列，從上到下一條path，求最大和，每次只能往左或者往右，POJ原題，DP最基礎的題不解釋
內存有限制，滾動數組之~
1 class Solution {
2 public:
3 int minimumTotal(vector<vector<int> > &triangle) {
4 int n = triangle.size();
5 int dp[2][1010], mx = 100000;
6 memset(dp, 0, sizeof(dp));
7 for(int i = 1; i <= n; ++i) {
8 for(int j = 1; j <= i; ++j) {
9 //cout << "i=" << i << "j=" << j << endl;
10 if(j == 1) dp[i & 1][j] = dp[(i - 1) & 1][j] + triangle[i - 1][j - 1];
11 else if(j == i) dp[i & 1][j] = dp[(i - 1) & 1][j - 1] + triangle[i - 1][j - 1];
12 else
13 dp[i & 1][j] = min(dp[(i - 1) & 1][j - 1] + triangle[i - 1][j - 1], dp[(i - 1) & 1][j] + triangle[i - 1][j - 1]);
14 if(i == n && dp[i & 1][j] < mx) {
15 mx = dp[i & 1][j];
16 }
17 }
18 }
19 return mx;
20 }
21 };