Posted on 2014-01-11 02:43
Uriel 阅读(92)
评论(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 };