python - 使用 python 进行动态编程的优化帕斯卡三角形

Question

def pascal(row, col):
    if col == 1 or col == row:
        return 1
    else:
        return pascal(row - 1, col) + pascal(row - 1, col - 1)

就时间复杂度而言，上述递归实现是指数级的。有了动态规划的知识，我们怎么写一个函数fast_pascal(row, col)？该函数应该接受一个整数行和一个整数 col 并返回 (row, col) 中的值。注意：row 和 col 从 1 开始。

这是我试过的，

def fast_pascal(row,col):
dynamic = [[1]+[1]*(col-1)for i in range(row)]
for row_ind in range(1,row):
    for col_ind in range(1,col):
        dynamic[row_ind][col_ind] = dynamic[row_ind-1][col_ind] + dynamic[row_ind-1][col_ind-1]
return dynamic[row-1][col-1]

该代码给出了错误的结果。它应该是，

fast_pascal(3,2) == 2
fast_pascal(4,3) == 3
fast_pascal(500,3) == 124251

标签： pythondynamicdynamic-programmingpascals-triangle

Answer 1

def fast_pascal(row,col):
    dynamic = [[1]+[0]*(col-1)for i in range(row)]
    for row_ind in range(1,row):
        for col_ind in range(1,col):
            dynamic[row_ind][col_ind] = dynamic[row_ind-1][col_ind] + dynamic[row_ind-1][col_ind-1]
    return dynamic[row-1][col-1]