首页 > 代码库 > leetcode 120 Triangle ----- java
leetcode 120 Triangle ----- java
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 { public int minimumTotal(List<List<Integer>> triangle) {int len = triangle.size(); int result = triangle.get(0).get(0); result = getResult(result,0,0,triangle); return result; } public static int getResult(int result,int pos,int num,List<List<Integer>> triangle){ if( num == triangle.size()-1 ) return result; int num1 = triangle.get(num+1).get(pos); int ans = result; ans += num1; ans = getResult(ans,pos,num+1,triangle); num1 = triangle.get(num+1).get(pos+1); result += num1; result = getResult(result,pos+1,num+1,triangle); return ans>result?result:ans; } }
所以还是需要用DP。
比较简单的DP应用。
public class Solution { public int minimumTotal(List<List<Integer>> triangle) { int height = triangle.size(); int[] dp = new int[height]; dp[0] = dp[0]+triangle.get(0).get(0); for( int i = 1;i<height;i++){ int a = dp[0],b = dp[1]; dp[0] = dp[0]+triangle.get(i).get(0); for( int j = 1;j<i;j++){ dp[j] = Math.min(a,b)+triangle.get(i).get(j); a = b; b = dp[j+1]; } dp[i] = a+triangle.get(i).get(i); } int result = dp[0]; for( int i = 1;i<height;i++) result = Math.min(result,dp[i]); return result; } }
leetcode 120 Triangle ----- java
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。