Blue Ocean: minimum path sum of a number triangle

Blue Ocean: minimum path sum of a number triangle

minimum path sum of a number triangle The key observation here is that viewing this triangle as a tree, for any given subtree, the minimum path sum is the minimum of all of its subtrees plus the number at the root. At the leaf level, the minimum path sum is the value at the leaves. If we use dynamic programming, keep track of the minimum path sum at lower level, and then going up to calculate the min path sum at higher level. public static int minPath(List input){ int levels = input.size(); //we start at the bottom //here the min path sum is the numbers at the bottom dp[levels-1] = input.get(levels-1); for(int l=levels-2; l>=0; l--){ for(int pos = 0; pos<=l; pos++){ } } } Further observation of the dynamic programming solution is that we don't need a 2D table, in stead we can use an array and keep on updating it when going up. public static int minPathBetter(List input){ int levels = input.size(); int[] dp = new int[levels];

Read full article from Blue Ocean: minimum path sum of a number triangle