120.三角形最小路径和

￡神魔★判官ぃ 2021-06-22 15:38 402阅读 0赞

//给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。  
// 相邻的结点 在这里指的是 下标 与 上一层结点下标 相同或者等于 上一层结点下标 + 1 的两个结点。  
//  
// 例如，给定三角形：  
//  
// \[  
// \[2\],  
// \[3,4\],  
// \[6,5,7\],  
// \[4,1,8,3\]  
// \]  
//  
// 自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。  
//  
// 说明：  
// 如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。  
// Related Topics 数组 动态规划  
//思路：  
// 定义状态：定义dp\[i\]\[j\] 表示从底到（i，j）点的路径最小值  
// 递推方程：dp\[i\]\[j\] = min(dp\[i+1\]\[j\],dp\[i+1\]\[j+1\])

/** * 解法1 二维数组进行求解 * @param triangle * @return */
    class Solution { 
    	public int minimumTotal(List<List<Integer>> triangle) { 
    		if (triangle == null || triangle.size() == 0) { 
    			return 0;
    		}
    		// 加1可以不用初始化最后一层
    		int[][] dp = new int[triangle.size() + 1][triangle.size() + 1];
    
    		// 从底层开始遍历
    		for (int i = triangle.size() - 1; i >= 0; i--) { 
    			List<Integer> curTr = triangle.get(i); //获取第i层
    			for (int j = 0; j < curTr.size(); j++) {  //计算i,j到底部的最短路径和，利用前面的递推公式dp[i][j] = min(dp[i+1][j],dp[i+1][j+1])
    				dp[i][j] = Math.min(dp[i + 1][j], dp[i + 1][j + 1]) + curTr.get(j);
    			}
    		}
    		return dp[0][0];
    	}
    }

/** * 解法2 一维数组进行求解 * @param triangle * @return */
    class Solution { 
    	public int minimumTotal(List<List<Integer>> triangle) { 
    		if (triangle == null || triangle.size() == 0) { 
    			return 0;
    		}
    		// 只需要记录每一层的最小值即可
    		int[] dp = new int[triangle.size() + 1];
    
    		for (int i = triangle.size() - 1; i >= 0; i--) { 
    			List<Integer> curTr = triangle.get(i);
    			for (int j = 0; j < curTr.size(); j++) { 
    				//这里的dp[j] 使用的时候默认是上一层的，赋值之后变成当前层
    				dp[j] = Math.min(dp[j], dp[j + 1]) + curTr.get(j);
    			}
    		}
    		return dp[0];
    	}
    }