动态规划算法最常见的递归coding方式

动态规划算法最常见的递归coding方式是使用一个递归函数来计算解决问题所需的最优解。该递归函数将问题划分为更小的子问题，然后将这些子问题的最优解组合起来得到原问题的最优解。具体而言，递归函数通常具有以下形式：

def dp(i, j): if (i, j) in memo: return memo[(i, j)] # 计算子问题的最优解 ans = ... memo[(i, j)] = ans return ans

其中，i和j表示原问题的规模，memo是一个字典，用于记录已经计算过的子问题的最优解。在函数中，首先会检查当前的子问题是否已经计算过，如果是，则直接返回计算过的最优解。否则，计算子问题的最优解，并将其记录在memo中，最后返回该最优解。

在实际应用中，由于递归函数可能会重复计算一些子问题，因此可以使用备忘录技术或者自底向上的迭代方式来优化动态规划算法的效率。