119. Pascal's Triangle II

Loading...LeetCode

一看图就是dp啦

其实如果top-down的话比较省空间，可以只维护一行的数值，懒得写了

class Solution:
    def getRow(self, rowIndex: int) -> List[int]:
        res = [0 for _ in range(rowIndex+1)]
        memo = dict()
        
        def getValue(row, idx):
            if idx == 0 or idx ==row: return 1
            elif idx == 1 or idx ==row-1: return row
            else:
                left = memo[(row-1, idx-1)] if (row-1, idx-1) in memo.keys() else getValue(row-1, idx-1)
                right = memo[(row-1, idx)] if (row-1, idx) in memo.keys() else getValue(row-1, idx)
                value = left + right
                memo[(row, idx)] = value
                return value
            
            
        for n in range(len(res)):
            res[n] = getValue(rowIndex, n)
        
        return res