首页 > 代码库 > Triangle
Triangle
Important:
The hardest part is to define the state(here is f[x][y]) and its function(the relationship between them)
public class Solution { /** * @param triangle: a list of lists of integers. * @return: An integer, minimum path sum. */ public int minimumTotal(int[][] triangle) { // write your code here if (triangle == null || triangle.length == 0) { return 0; } if (triangle[0] == null || triangle[0].length == 0) { return 0; } int n = triangle.length; //initiallize //f[x][y]: minimum path value from (0,0) to (x, y) int[][] f = new int[n][n]; //top value f[0][0] = triangle[0][0]; //two sides for (int i = 1; i < n; i++) { f[i][0] = f[i - 1][0] + triangle[i][0]; f[i][i] = f[i - 1][i - 1] + triangle[i][i]; } //Top to bottom for(int i = 1; i < n; i++) { for(int j = 1; j < i; j++) { f[i][j] = Math.min(f[i - 1][j - 1], f[i - 1][j]) + triangle[i][j]; } } //find the minimum in the bottom int minimum = f[n - 1][0]; for(int i = 1; i < n; i++) { if (minimum > f[n - 1][i]) { minimum = f[n - 1][i]; } } return minimum; } }
Triangle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。