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.
public class Solution { // dp[i] = min(dp[i], dp[i - 1]) + num[i] public int minimumTotal(List<List<Integer>> triangle) { if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) return 0; int rows = triangle.size(); int cols = triangle.get(rows - 1).size(); int[] dp = new int[cols]; dp[0] = triangle.get(0).get(0); for (int i = 1; i < rows; i++) { int lastPos = triangle.get(i).size() - 1; dp[lastPos] = dp[lastPos - 1] + triangle.get(i).get(lastPos); for (int j = lastPos - 1; j > 0; j--) { dp[j] = Math.min(dp[j], dp[j - 1]) + triangle.get(i).get(j); } dp[0] += triangle.get(i).get(0); } int min = Integer.MAX_VALUE; for (int j = 0; j < cols; j++) { if (min > dp[j]) min = dp[j]; } return min; } // dp[i][j] = min(dp[i - 1][j], dp[i - 1][j - 1]) + num[i][j] /* public int minimumTotal(List<List<Integer>> triangle) { if (triangle == null || triangle.size() == 0 || triangle.get(0).size() == 0) return 0; int rows = triangle.size(); int cols = triangle.get(rows - 1).size(); int[][] dp = new int[rows][cols]; dp[0][0] = triangle.get(0).get(0); for (int i = 1; i < rows; i++) { for (int j = 0; j < triangle.get(i).size(); j++) { if (j > 0 && j < triangle.get(i).size() - 1) { dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i - 1][j]) + triangle.get(i).get(j); } else if (j == 0) { dp[i][j] = dp[i - 1][j] + triangle.get(i).get(j); } else if (j == triangle.get(i).size() - 1) { dp[i][j] = dp[i - 1][j - 1] + triangle.get(i).get(j); } } } int min = Integer.MAX_VALUE; for (int i = 0; i < cols; i++) { if (dp[rows - 1][i] < min) min = dp[rows - 1][i]; } return min; } */ }
相关推荐
《leetcode-solutions》,刷算法题,需要有一定的英文阅读能力。。。
Algorithm-LeetCode-Sol-Res.zip,干净,易懂的解决方案和资源,为leetcode在线判断算法问题。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
IDEA 插件,lettcode刷题,leetcode-editor7.4版本下载进行本地导入(直接将压缩包拖进IDEA即可)
Algorithm-leetcode-spider.zip,leetcode公司,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
在IDE中解决LeetCode问题,支持leetcode.com与leetcode-cn.com,满足基本的做题需求。 理论上支持: IntelliJ IDEA PhpStorm WebStorm PyCharm RubyMine AppCode CLion GoLand DataGrip Rider MPS Android Studio。
leetcode 答案解析 golang解答
leetcode-editor,在ide中做leetcode练习,支持leetcode.com和leetcode-cn.com,以满足练习的基本需求。理论上支持:intellij idea phpstorm webstorm pycharm rubymine appcode clion goland datagrip rider mps ...
leetcode-cli-plugins leetcode-cli 的第 3 方插件。 什么是 如何使用 如何使用 插件 名称 描述 增强的命令 按公司或标签过滤问题 list 不要在同一台计算机上使 Chrome 的会话过期 login 不要在同一台计算机上使 ...
解题思路思路和LeetCode-python 503.下一个更大元素 II一致,只是这里求的是下标的距离,而不是数值倒序搜索,用到栈,栈里存储索引情况1:若栈为
然后进入到LeetCode-Spider目录中修改config.json,其中outputDir需要填写该工程的/docs/views文件夹路径 { "username": "aaa", "password": "bbb", "outputDir": "/Users/liuyao/Downloads/LeetCode-Blog-Test/docs...
leetcode-helper-1.7.1
leetcode-tag-dynamic programming
leetcode-cheat 的发布 它是什么 ? 这是一个chrome 扩展,可以帮助您更高效地使用 leetcode。您可以从 重要: leetcode-cheat 现在只支持中文版。 也就是说不完全支持leetcode.com,但是你可以用leetcode-cn.com代替...
leetcode-tag-Tree
leetcode-tag-Stack
leetcode-tag-array
Algorithm-LeetCode-Solution-From-GuaZiDou.zip,Leetcode解决方案Gitbook,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
RandomPickWithWeight-LeetCode-528-源码.rar
~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/vsc-leetcode-cli/bin/leetcode /usr/local/bin/leetcode 修改模板 open ~/.vscode/extensions/leetcode.vscode-leetcode-0.17.0/node_modules/...