顺序 otto turn markdown using mov end ret 叠加
- Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
- For example, given the following triangle
- [
- [2],
- [3,4],
- [6,5,7],
- [4,1,8,3]
- ]
- The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).
- Note:
- Bonus point if you are able to do this using only O(n) extra space, where n is the total number of rows in the triangle.
- // Triangle
- class Solution_120 {
- public:
- // top-down
- int minimumTotal1(vector<vector<int>>& triangle) {
- vector<int> res(triangle.size(), triangle[0][0]);
- for (unsigned int i = 1; i < triangle.size(); i++)
- for (int j = i; j >= 0; j--) {
- if (j == 0)
- res[0] += triangle[i][j];
- else if (j == i)
- res[j] = triangle[i][j] + res[j - 1];
- else
- res[j] = triangle[i][j] + min(res[j - 1], res[j]);
- }
- return *min_element(res.begin(), res.end());
- }
- // bottom-up
- int minimumTotal2(vector<vector<int>>& triangle) {
- vector<int> res = triangle.back();
- for (int i = triangle.size() - 2; i >= 0; i--)
- for (unsigned int j = 0; j <= i; j++)
- res[j] = triangle[i][j] + min(res[j], res[j + 1]);
- return res[0];
- }
- int minimumTotal(vector<vector<int>>& triangle) {
- int row = triangle.size();
- if (row==0)
- {
- return 0;
- }
- if (row==1)
- {
- return triangle[0][0];
- }
- int ret = 0;
- vector<int> vec(triangle.size(), triangle[0][0]); //初始化
- for (int i = 1; i < row;i++) //当前行
- {
- for (int j = 0; j < triangle[i].size(); j++)
- {
- if (j==0)
- {
- vec[j] = vec[j] + triangle[i][j];
- }else if (j==triangle[i].size()-1)
- {
- vec[j] = vec[j-1] + triangle[i][j]; //bug 会叠加上一次改变的值 //变顺序啊!!!逆序
- }
- else
- {
- vec[j] = triangle[i][j] + min(vec[j - 1], vec[j]);
- }
- }
- }
- return *min_element(vec.begin(), vec.end());
- }
- };
来源: http://www.bubuko.com/infodetail-2451000.html