LeetCode--杨辉三角（python版）

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        def list_func(n):
            if n==1:
                return [1]
            if n==2:
                return [1,1]
            return_list=[None]*n
            return_list[0]=1
            return_list[n-1]=1
            for i in range(1,n-1):
                return_list[i]=list_func(n-1)[i-1]+list_func(n-1)[i]
            return return_list
        list1=[]
        for i in range(numRows):
            list1.append(list_func(i+1))
        return list1

研究规律，使用递归方法计算出每一层的数组，但是时间复杂度太高，不满足需求，需要降低时间复杂度。
解决方法：保存每一级的结果，降低冗余计算。
优化解法：动态规划

class Solution(object):
    def generate(self, numRows):
        """
        :type numRows: int
        :rtype: List[List[int]]
        """
        r_list=[]
        for i in range(1,numRows+1):
            row=[None]*i
            row[0]=1
            row[-1]=1
            for j in range(1,i-1):
                row[j]=r_list[i-2][j-1]+r_list[i-2][j]
            r_list.append(row)
        return r_list

需要特别注意数组的index，踩了好几个坑，崩溃
附上官方解答：

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

        for row_num in range(num_rows):
            # The first and last row elements are always 1.
            row = [None for _ in range(row_num+1)]
            row[0], row[-1] = 1, 1

            # Each triangle element is equal to the sum of the elements
            # above-and-to-the-left and above-and-to-the-right.
            for j in range(1, len(row)-1):
                row[j] = triangle[row_num-1][j-1] + triangle[row_num-1][j]

            triangle.append(row)

        return triangle

变量使用更加统一清晰