动态规划法和递推法有什么区别

发布网友发布时间：2024-01-03 04:09

共1个回答

热心网友时间：2024-11-02 06:46

思路不同，实现不同等。
思路不同：动态规划法通常是从问题的最优子结构出发，通过将问题分解为子问题，并保存子问题的解，最终得到原问题的解。它通常适用于具有重叠子问题和最优子结构性质的问题。递推法通常是通过定义递推关系式，从已知的初始条件出发，逐步推导出问题的解。它通常适用于问题的解可以通过前面的解来计算的情况。
实现不同：动态规划法通常需要使用一个数组或者矩阵来保存子问题的解，以便在计算当前问题时能够直接使用已经计算过的子问题的解。递推法通常只需要使用几个变量来保存中间结果，不需要保存所有的子问题的解。