Pascal's Triangle II

来自 lettcode

给出一个数字，然后计算那一层的数字。

Input: 3
Output: [1,3,3,1]

看讨论求，用 Python 求解，巧妙的利用了 zip 这个特性：

def getRow(rowIndex):
    row = [1]
    for _ in range(rowIndex):
        row = [x+y for x, y in zip([0] + row, row+[0])]
    return row

当前数字等于上一层当前位置的数字加之前一个数字。
使用 C++ 来写更容易明白一些：

vector<int> getRow(int rowIndex) {
        vector<int> vi(rowIndex+1);
        vi[0] = 1;
        for(int i = 0; i <= rowIndex; ++i)
        {
            for(int j = i; j > 0; --j){
                vi[j] = vi[j] + vi[j-1];
            }
        }
        return vi;
    }

构造 Triangle

与上面不同的是，这个问题是需要构造完整的 Triangle

def generate(numRows):
    pascal = [[1] *(i+1) for i in range(numRows)]
    for i in range(numRows):
        for j in range(1, i):
            pascal[i][j] = pascal[i-1][j-1] + pascal[i-1][j]
    return pascal

Triangle 找出一条最小的路径

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
最小路径是 2 + 3 + 5 + 1 = 11.

首先可以构造一个一模一样的数组：

def minimumTotal(triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    构造一个一模一样的数组
    """
    if not triangle:
        return 
    res = [[0 for i in range(len(row))] for row in triangle]
    res[0][0] = triangle[0][0]
    for i in range(1, len(triangle)):
        for j in range(len(triangle[i])):
            if j == 0:
                res[i][j] = res[i-1][j] + triangle[i][j]
            elif j == len(triangle[i])-1:
                res[i][j] = res[i-1][j-1] + triangle[i][j]
            else:
                res[i][j] = min(res[i-1][j-1], res[i-1][j]) + triangle[i][j]
    return min(res[-1])

不用构造数组，直接修改原数组：

def minum(traingle):
    # 从上往下
    if not traingle:
        return
    for i in range(1, len(traingle)):
        for j in range(len(traingle[i])):
            if j ==0:
                traingle[i][j] += traingle[i-1][j]
            elif j == len(traingle[i])-1:
                traingle[i][j] += traingle[i-1][j-1]
            else:
                traingle[i][j] += min(traingle[i-1][j], traingle[i-1][j-1])
    return min(traingle[-1])

由底向上计算：

def minimumTotal(triangle):
    """
    :type triangle: List[List[int]]
    :rtype: int
    """
    if not triangle:
        return 
    res = triangle[-1]
    for i in range(len(triangle)-2, -1, -1):
        for j in range(len(triangle[i])):
            res[j] = min(res[j], res[j+1]) + triangle[i][j]
    return res[0]