1 三角形数组最小路径和

问题描述

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

1
2
3
4
5
6
7
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

问题分析

策略选择

算法设计

  • 问题分解划分阶段：规模增长方向，从下到上（不用判断边界）。阶段n=n,n-1,…,1
  • 确定状态变量：k阶段的状态变量是数组X[n]内的前k项，组成的状态变量集合。
  • 状态转移方程。k阶段的状态变量X_k[n],分两种情况讨论。X_k[j]可能有两种情况，利用了上一阶段X_k-1[j]的长度。或者领了X_k-1[j+1]的长度。
    $$
    X_{k}[j]=min{X_{k-1}[j-1]+triangle[j],X_{k-1}[j+1]+triangle[j]}
    $$
  • 确定边界实现过程。初始值为0。从最后一层开始。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int n = triangle.size();
        vector<int> result(n+1,0);
        // cout<<result.size()<<endl;
        for(int i=n-1;i>=0;i--){
            for(int j=0;j<triangle[i].size();j++){
                result[j]=triangle[i][j]+min(result[j],result[j+1]);
            }
        }
        return result[0];
    }
};//拷贝初始化会拖慢速度