0118._pascals_triangle.md

Navigation

• Navigation
• Links:
• Solution 1 动态规划

Links:

1. https://leetcode.com/problems/pascals-triangle/
2. https://leetcode-cn.com/problems/pascals-triangle/

Solution 1 动态规划

因为下一行要基于上一行来构造，所以使用动态规划。

class Solution:
    """
        时间复杂度：O(num_rows^2)
        空间复杂度：O(num_rows^2)
    """
    def generate(self, num_rows):
        triangle = []
        
        for row in range(num_rows):
            triangle.append([])
            
            for col in range(row+1):
                if col == 0 or col == row:
                    triangle[row].append(1)
                else:
                    triangle[row].append(triangle[row-1][col-1] + triangle[row-1][col])
        
        return triangle

---

class Solution:
    def generate(self, num_rows):
        triangle = []

        for row in range(num_rows):
            triangle.append([None for _ in range(row+1)])  # 一般动态规划是先初始化
            triangle[row][0], triangle[row][-1] = 1, 1

            for col in range(1, row):    # 因为第一个和最后一个位置已经初始化为1
                triangle[row][col] = triangle[row-1][col-1] + triangle[row-1][col]
            
        return triangle

---

class Solution:
    def generate(self, num_rows):
        triangle = []

        for i in range(num_rows):
            row = [None for _ in range(i+1)]
            row[0], row[-1] = 1, 1

            for j in range(1, len(row)-1):
                row[j] = triangle[i-1][j-1] + triangle[i-1][j]

            triangle.append(row)

        return triangle

---

class Solution(object):
    def generate(self, num_rows):
        if not num_rows:
            return []
        
        triangle = []
        res = [1]
        triangle.append(res)

        for i in range(1, num_rows):
            res = [1] + [res[x]+res[x+1] for x in range(len(res)-1)] + [1]
            triangle.append(res)
            
        return triangle

---

Go

func generate(numRows int) [][]int {
	result := make([][]int, numRows)
	for i := 0; i < numRows; i++ {
		result[i] = make([]int, i+1)
	}

	for row := 0; row < numRows; row++ {
		result[row][0] = 1
		result[row][row] = 1

		for col := 1; col < row; col++ {
			val := result[row-1][col-1] + result[row-1][col]
			result[row][col] = val
		}
	}

	return result
}

---

Go

func generate(numRows int) [][]int {
	result := make([][]int, numRows)

	for row := 0; row < numRows; row++ {
        result[row] = make([]int, row+1)

		result[row][0] = 1
		result[row][row] = 1

		for col := 1; col < row; col++ {
			val := result[row-1][col-1] + result[row-1][col]
			result[row][col] = val
		}
	}

	return result
}