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 .
Input : 3
Output : [1,3,3,1]
The space complexity is o(k)
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
class Solution: def getRow(self, rowIndex: int) -> List[int]: result = [0 for i in range(rowIndex+1)] result = 1 for i in range(1,rowIndex+1): for j in range(i,0,-1): result[j] += result[j-1] return result