Python 中动态规划与递推的比较
动态规划和递推都是求解最优子结构的算法，但两者之间有着一定的区别。
动态规划可以理解为将问题分成若干个子问题，然后分别求解，并将子问题的解合并起来得到原问题的解。动态规划使用一个二维数组来存储中间状态的结果，避免了重复计算的问题，因此时间复杂度常常比暴力算法优秀。动态规划常常需要另外一些策略来确定如何最优的划分成子问题、各个子问题的求解顺序等等。
递推则是直接根据当前的状态来计算下一个状态，省略了存储中间状态的数组，因此内存消耗较小。递推的优点在于代码实现简便、易于理解。
下面是一个使用动态规划求解最长公共子序列的例子，其中使用了一个二维数组来存储中间状态的结果。代码如下：
def LCS(str1, str2):
m = len(str1)
n = len(str2)
c = [[0 for j in range(n+1)] for i in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
if str1[i-1] == str2[j-1]:
c[i][j] = c[i-1][j-1] + 1
else:
c[i][j] = max(c[i][j-1], c[i-1][j])
return c[m][n]
而下面是一个使用递推求解斐波那契数列的例子，其中只需要两个变量来存储中间状态的结果。代码如下：
def fib(n):
a, b = 0, 1
for i in range(n):
a, b = b, a + b
return a
在这个例子中，我们只需要使用两个变量a和b来分别存储斐波那契数列中前两个数的值，然后使用这两个变量来循环计算后续的值，避免了存储中间状态的二维数组，因此内存消耗小。
相关文章