|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
题目描述:
- 给定一个三角形,找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。
- 例如,给定三角形:
- [
- [2],
- [3,4],
- [6,5,7],
- [4,1,8,3]
- ]
- 自顶向下的最小路径和为 11(即,2 + 3 + 5 + 1 = 11)。
- 说明:
- 如果你可以只使用 O(n) 的额外空间(n 为三角形的总行数)来解决这个问题,那么你的算法会很加分。
- 来源:力扣(LeetCode)
- 链接:https://leetcode-cn.com/problems/triangle
- 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码
- int minimumTotal(vector<vector<int>>& input) {
- int len = input.size();
- int col = input[len-1].size();
- if(len == 1) return *min_element(input[0].begin(), input[0].end());
- vector<vector<int> > res(len, vector<int> (col, INT_MAX));
- res[0][0] = input[0][0];
- for(int i = 1; i < len; i++){
- res[i][0] = input[i][0] + res[i-1][0];
- }
-
- for(int i = 1; i < len; i++){
- for(int j = 1; j < input[i].size(); j++){
- res[i][j] = min(res[i-1][j-1], res[i-1][j]) + input[i][j];
-
- }
-
- }
- return *min_element(res[len-1].begin(), res[len-1].end());
- }
复制代码 |
|