目录
3. 动态规划（Dynamic Programming, DP）
在C++编程中，递推、递归和动态规划是三种重要的算法思想，它们在解决复杂问题时各有特色。下面将分别介绍这三种算法思想，并探讨它们之间的区别。
1. 递推（Iteration）
定义与原理：
递推是一种通过已知信息（即初始条件或已求解的较小问题）逐步推导出未知信息（即较大问题的解）的方法。在递推过程中，每个问题的解都依赖于前面已经解决的问题的解。递推通常是通过循环结构（如for循环、while循环）来实现的，而不是通过函数调用自身。
特点：
- 正向求解：从已知条件出发，逐步推导出未知结果。
- 效率高：由于避免了函数调用的开销，递推通常比递归效率更高。
- 边界条件重要：递推需要明确初始条件和边界条件，以确保求解的正确性。
示例：斐波那契数列的计算，其中f(n) = f(n-1) + f(n-2)，且f(1) = 1, f(2) = 1。通过循环结构，可以从f(1)和f(2)出发，逐步推导出f(n)的值。
2. 递归（Recursion）
定义与原理：
递归是一种通过函数自我调用的方式来解决问题的算法思想。在递归中，一个函数会调用自身来解决一个规模更小但结构相同的问题。递归的核心在于找到递归的基线条件（即递归的终止条件），以及递归步骤（即将问题分解为更小问题的步骤）。
特点：
- 逆向求解：从问题的最终目标出发，逐步分解为更小的问题。
- 代码简洁：对于某些问题，递归代码更加简洁、易于理解。
- 效率可能较低：由于函数调用的开销，递归在效率上可能不如递推。此外，递归过深可能导致栈溢出。
示例：斐波那契数列的计算同样可以通过递归来实现。但是，由于递归函数会重复计算相同的值（如f(n-1)在计算f(n)和f(n+1)时都会被调用），因此效率较低。
3. 动态规划（Dynamic Programming, DP）
定义与原理：
动态规划是运筹学的一个分支，用于解决多阶段决策过程的最优化问题。它通过将复杂问题分解为多个简单的子问题，并保存已解决的子问题的解来避免重复计算，从而提高效率。动态规划通常与递归结合使用，但通过自底向上的方式（即先解决小问题，再逐步解决大问题）来避免递归中的重复计算。
特点：
- 避免重复计算：通过保存已解决的子问题的解来避免重复计算。
- 空间换时间：通常需要额外的空间来存储子问题的解。
- 适用范围广：可以应用于各种类型的问题，如最优化问题、计数问题等。
示例：斐波那契数列的计算可以通过动态规划来优化。我们可以使用一个数组来保存已经计算过的斐波那契数，从而在计算新的斐波那契数时直接引用之前的结果，避免重复计算。
递推、递归与动态规划的区别
| 递推 | 递归 | 动态规划 | |
|---|---|---|---|
| 求解方向 | 正向求解 | 逆向求解 | 正向或逆向，但通常与递归结合使用自底向上的方式 |
| 效率 | 较高（无函数调用开销） | 可能较低（有函数调用开销，且可能重复计算） | 较高（通过避免重复计算） |
| 空间复杂度 | 较低（通常只需少量额外空间） | 较高（递归栈可能占用较多空间） | 较高（需要额外空间存储子问题的解） |
| 适用场景 | 适用于可以直接通过循环结构求解的问题 | 适用于结构清晰、可以自然分解为更小子问题的问题 | 适用于多阶段决策过程的最优化问题 |
综上所述，递推、递归和动态规划在C++编程中各有优缺点和适用场景。在实际应用中，应根据问题的具体特点选择合适的算法思想来解决问题。
标签：问题,递归,求解,C++,第一期,算法,计算,动态,递推 From： https://blog.csdn.net/SpXace/article/details/140643215