Java solution with comments


  • 0
    W
    // 思路: 动态规划,从底往上选择相邻的较小值累计,最后的A[0]是最小和
    public static int minimumTotal(List<List<Integer>> M) {
    	int length = M.get(M.size() - 1).size(); // 最后一行长度
    	int[] A = new int[length + 1]; // 辅助数组,保存每次的动态结果
    	for (int i = length - 1; i >= 0; i--) { // 从底往上
    		for (int j = 0; j < M.get(i).size(); j++) {
    			// 选择当前行元素和 下一层中相邻的较小元素相加
    			// 因为j++的缘故,所以下次开始时A[j]并没有被覆盖!
    			A[j] = M.get(i).get(j) + Math.min(A[j], A[j + 1]);
    		}
    	}
    	return A[0];
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.