本文共 4906 字，大约阅读时间需要 16 分钟。

三角形最短路径问题

问题描述：给出如图所示的三角形，从顶点开始，求出从顶点开始到最下一层所经过的元素的最小路径和。

例如：

从顶点到底边的最小路径和为：17 (i.e., 7 + 3 + 1 + 4 + 2 = 11).

问题分析：

该问题可以考虑采用动态规划算法解决。 动态规划是针对一类求最优解的问题的算法， 其核心是将一个问题分解成为若干个子问题（这里对应下文的子问题使用条件）， 部分类似于分治的思想， 通过求每一次的最优决策， 来得到一个最优解。在这里最重要的就是子问题的思想。

最优子结构性质和子问题重叠性质是该问题可用动态规划算法求解的基本要素：

1、最优子结构

当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。

2、重叠子问题

可用动态规划算法求解的问题应具备的另一个基本要素是子问题的重叠性质。在用递归算法自顶向下求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要此子问题时，只要简单地用常数时间查看一下结果。通常，不同的子问题个数随问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。

算法设计：

定义：d[i][j]表示从a[0][0]到a[i][j]的最小路径和，其中j<=i

初始化：计算d[i][0] 递推表达式： 如果i=j，d[i][j]=a[i][j]+d[i-1][j-1] 否则d[i][j]=a[i][j]+MIN{d[i-1][j],d[i-1][j-1]}

public static int minTotalSolution5(List
   
    
     > triangle) {  		    if(triangle.size()==0||triangle.get(0).size()==0){  		        return 0;  		    }  		    int m=triangle.size()；		    int n=m;  		    int[][] d = new int[m][n];  		    int sum=0;  		    for(int i=0;i
    
   

除了上述算法之外，在给出几种不同的算法设计：

package com.bean.algorithmbasic;import java.util.ArrayList;import java.util.List;public class TriangleProblem {		/*	 * 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).	 * 	 * */		 /*	  * The idea is simple.	  * Go from bottom to top.	  * We start form the row above the bottom row [size()-2].	  * Each number add the smaller number of two numbers that below it.	  * And finally we get to the top we the smallest sum.	  * */	 public static int minimumTotal(List
   
    
     > triangle) {	        int len = triangle.size();	        for(int i=len-2; i>=0; i--){	            for(int j=0; j<=i; j++){	                triangle.get(i).set(j, triangle.get(i).get(j) + Math.min(triangle.get(i+1).get(j), triangle.get(i+1).get(j+1)));	            }	        }	        return triangle.get(0).get(0);	 }	 	 public static int minTotal(List
     
      
       > triangle) {		    int m = triangle.size();		    if (m == 0) return 0;		    int n = triangle.get(m - 1).size();		    if (n == 0) return 0;		    int[] dp = new int[m];		    dp[0] = triangle.get(0).get(0);		    for (int i = 1; i < m; i++) {		        int l = triangle.get(i).size();		        for (int k = l - 1; k >= 0; k--) {		            int curr = Math.min((k < l - 1 ? dp[k] : Integer.MAX_VALUE), 		                                (k >= 1 ? dp[k - 1]: Integer.MAX_VALUE)) + triangle.get(i).get(k);		            dp[k] = curr;		        }		    }		    int min = Integer.MAX_VALUE;		    for (int k = 0; k < n; k++) {		        min = Math.min(min, dp[k]);		    }		    return min;		}	 	 /*	  * 算法设计:	  * 	  * 	  * */	 public static int minTotalSolution(List
       
        
         > triangle) { int len = triangle.size(); //用dp数组来表示最优解，数组的最大长度与三角形的高度相等。 //因为每次从三角形的每行取一个值，能够取值的数量取决于三角形的行数（高度） int[] dp = new int[len]; for(int i = len-1;i >= 0; i--){ //对每一层来说 for(int j = 0; j <= i; j++){ //Check每个元素 //递推表达式 if(i == len-1) { dp[j]= triangle.get(i).get(j); //dp[j]用于表示最小路径和 }else{ //找到两个最小的值，将他们相加并赋值 dp[j] = Math.min(dp[j],dp[j+1])+triangle.get(i).get(j); } } } return dp[0]; } public static int minTotalSolution4(List
         
          
           > triangle) { int[] sum = new int[triangle.size()]; sum[0] = triangle.get(0).get(0); int min = Integer.MAX_VALUE; for (int i = 1; i < triangle.size(); i++) { List
           
             row = triangle.get(i); // iterate backwards so we don't write over our cache in the sum // array. If we start from the last we will never overwrite values // that we will need later. for (int j = i; j >= 0; j--) { int val = row.get(j); // if we are on the first column then the only adjacent // number is already stored in sum[j] from the previous row if (j == 0) { sum[j] += val; } // if we are on the last column then we are adding a new // value to the sum array since it increases by one each row. // Add the sum from the previous row which is located at sum[j-1] else if (j == i) { sum[j] = val + sum[j - 1]; } // we are in between and we need to take the min sum from the // adjacent cells in the previous row. else { sum[j] = Math.min(sum[j], sum[j-1]) + val; } } } for (int num: sum) { min = Math.min(num, min); } return min; } /* * 算法设计: * 定义: d[i][j]表示从a[0][0]到a[i][j]的最小路径和，其中j<=i * 初始化: 计算d[i][0] * 递推表达式: * 如果i=j，d[i][j]=a[i][j]+d[i-1][j-1] * 否则d[i][j]=a[i][j]+MIN{d[i-1][j],d[i-1][j-1]} * * */ public static int minTotalSolution5(List
            
             
              > triangle) { if(triangle.size()==0||triangle.get(0).size()==0){ return 0; } int m=triangle.size(),n=m; int[][] d=new int[m][n]; int sum=0; for(int i=0;i
              
               > list= new ArrayList
               
                
                 >(); for(int i=0; i
                 
                   listSub=new ArrayList
                  
                   ();//初始化一个ArrayList集合 for(int j=0; j
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

（完）