109.Triangle-数字三角形（容易题）

本文主要是介绍109.Triangle-数字三角形（容易题），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

数字三角形

1. 题目

   给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

   注意事项
   如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。

2. 样例

   比如，给出下列数字三角形：
   

3. 题解

DP问题
由于从上向下递推需要对每行中首末元素单独递推，稍显麻烦，顾在此采用从下向上递推的方式，状态转移方程是：triangle[i][j] = Math.min(triangle[i + 1][j],triangle[i + 1][j + 1]) + triangle[i][j];

public class Solution {/*** @param triangle: a list of lists of integers.* @return: An integer, minimum path sum.*/public int minimumTotal(int[][] triangle) {int n = triangle.length;for (int i = n-2; i >=0; i--) {for (int j = 0; j < triangle[i].length; j++) {triangle[i][j] = Math.min(triangle[i + 1][j],triangle[i + 1][j + 1]) + triangle[i][j];}}return triangle[0][0];}
}

Last Update 2016.9.5

这篇关于109.Triangle-数字三角形（容易题）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---