Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

[LeetCode]Triangle-2014.01.06

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

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理