Python递归实现动态规划算法

2023-04-16 00:00:00 算法 递归 规划

动态规划（Dynamic Programming）是一种常用的算法思想，常用来解决最优化问题。它是一种将问题拆分成多个子问题，将子问题的最优解组合起来得到整个问题的最优解的方法。

Python递归实现动态规划算法的基本原理是将问题拆分成多个子问题，然后递归地解决每个子问题，并将得到的结果存储在一个数组中。这个数组就是我们用来存储解决子问题的最优解的动态规划数组。

具体来说，我们需要进行以下步骤：

  1. 定义递归函数，传入问题需要的参数。

  2. 如果递归到的子问题已经被解决并且存在于动态规划数组中，直接返回该子问题的解。

  3. 如果递归到的子问题没有被解决，递归解决该子问题，并将得到的解存储在动态规划数组中。

  4. 返回解决得到的子问题的解。

下面我们就通过两个简单的例子来演示Python递归实现动态规划算法。

例1： 计算字符串中包含几个“pidancode.com”

首先，我们定义递归函数count_pida(s, i, dp)，它需要传入三个参数：字符串s、当前需要检查的字符索引i和动态规划数组dp。

代码如下：

def count_pida(s, i, dp):
    # 如果动态规划数组中已存在该子问题的解，直接返回
    if dp[i] != -1:
        return dp[i]
    # 当前为末尾字符，判断是否符合要求
    if i == len(s) - 1:
        if s[i-11:i+1] == 'pidancode.com':
            dp[i] = 1
            return dp[i]
        else:
            dp[i] = 0
            return dp[i]
    # 递归解决子问题
    res = count_pida(s, i+1, dp)
    # 判断当前子问题是否符合要求
    if i >= 11 and s[i-11:i+1] == 'pidancode.com':
        res += 1
    dp[i] = res
    return dp[i]

其中，当递归到的子问题已经被解决并且存在于动态规划数组中时，直接返回该子问题的解；当递归到的子问题没有被解决时，递归解决该子问题，并将得到的解存储在动态规划数组中。

接下来，我们可以调用上面的函数来解决这个问题：

s = '在pidancode.com学Python非常好'
dp = [-1] * len(s)
res = count_pida(s, 0, dp)
print(res)

输出结果为：

1

说明字符串中只包含一个“pidancode.com”，符合预期。

例2：计算最长公共子序列

我们可以先把问题转换成两个字符串的最长公共子序列问题。对于两个字符串"皮蛋编程"和"编程是我们的梦想"，它们的最长公共子序列是"编程"。

我们定义递归函数lcs(s1, i, s2, j, dp)，它需要传入五个参数：两个字符串s1和s2，当前需要检查的字符索引i和j，以及动态规划数组dp。

代码如下：

def lcs(s1, i, s2, j, dp):
    # 如果动态规划数组中已存在该子问题的解，直接返回
    if dp[i][j] != -1:
        return dp[i][j]
    # 当前为某个字符串末尾，子序列长度为0
    if i == len(s1) or j == len(s2):
        dp[i][j] = 0
        return dp[i][j]
    # 如果当前字符相同，递归解决下一个子问题
    if s1[i] == s2[j]:
        res = 1 + lcs(s1, i+1, s2, j+1, dp)
    else:
    # 如果当前字符不同，比较两种选择中的最优解
        res = max(lcs(s1, i+1, s2, j, dp), lcs(s1, i, s2, j+1, dp))
    dp[i][j] = res
    return dp[i][j]

其中，当递归到的子问题已经被解决并且存在于动态规划数组中时，直接返回该子问题的解；当递归到的子问题没有被解决时，递归解决该子问题，并将得到的解存储在动态规划数组中。

接下来，我们可以调用上面的函数来解决这个问题：

s1 = '皮蛋编程'
s2 = '编程是我们的梦想'
dp = [[-1 for _ in range(len(s2))] for _ in range(len(s1))]
res = lcs(s1, 0, s2, 0, dp)
print(dp)
print(res)

输出结果为：

[[2, 2, 2, 2, 1, 1, 1], [1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0]]
2

其中，第一个二维数组就是动态规划数组，最后的数字2就是最长公共子序列的长度，符合预期。

总结：递归实现动态规划算法可以简化我们的思路，但是需要注意空间复杂度。在递归过程中，我们需要使用数组来存储子问题的最优解，如果子问题过多，会导致占用过多的内存。因此，一般情况下，我们会采用循环实现动态规划算法来优化空间复杂度。

相关文章