## Leetcode: Yang Hui triangle (Python)

A good function 2020-11-13 02:53:50
leetcode yang hui triangle python

## 1. Title Description

Given a nonnegative index k, among k ≤ 33, Go back to the third part of Yanghui triangle k That's ok .

In Yanghui triangle , Each number is the sum of the numbers at the top left and right of it .
Example :

Input : 3
Output : [1,3,3,1]
The space complexity is o(k)

## 2. Ideas

Or use dynamic programming . Set a length to k+1（ When k by 0 when , Back to the first line ……） Of dp Array .
And then start with the first floor , Start updating array . If the current layer is level i layer , So before the array i-1 The three elements are Yang Hui's triangle i-1 Elements of layers , because dp[j] = dp[j] + dp[j-1], Every time you update an element, use the previous element , If each layer modifies array elements from front to back dp[j] What is added is the modified dp[j-1], Not the first. i-1 Layer of the first j Elements , This will lead to errors . So for each layer , You need to modify the elements from the back to the front .
Pay attention to the problem of boundaries

### 2.1 python Code

``````class Solution:
def getRow(self, rowIndex: int) -> List[int]:
result = [0 for i in range(rowIndex+1)]
result[0] = 1
for i in range(1,rowIndex+1):
for j in range(i,0,-1):
result[j] += result[j-1]
return result
``````