---

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

---

---

---

💯前言

• 在编程演练中，递归和记忆化算法是解决复杂问题的重要工具。特别是对于大规模动态规划问题，递归算法通过问题分解实现小问题的求解，而记忆化算法则是其性能优化的重要手段。本文将对一道基于递归和记忆化的函数计算题目进行全面解论，通过完整的思路解析和代码讲解，帮助研究生提升对递归与动态规划问题的理解深度和实现能力。
  C++ 参考手册
  

---

💯题目描述

有一个数列，函数定义如下：

$f(n)=f(n-1)+f(n//2)+f(n//3)$

其中：

• n//m表示正整除法。例如：3//2 = 1，4//2 = 2，5//2 = 2。
• 边界条件： 当 $n\le 0$ ，有 $f(n)=0$ 。
• 现在告诉你 $f(1)=x$，请计算 $f(n)$ 的值。

输入描述
输入两个整数 $x$ 和 $n$：

• $0<x$，$n\le 20$

输出描述
输出 $f(n)$ 的值。

示例1

• 输入：

  1 6
  

• 输出：

  16
  

题目提示

• $f(1)=1$
• $f(2)=f(1)+f(1)+f(0)=1+1+0=2$
• $f(3)=f(2)+f(1)+f(1)=2+1+1=4$
• $f(4)=f(3)+f(2)+f(1)=4+2+1=7$
• $f(5)=f(4)+f(2)+f(1)=7+2+1=10$
• $f(6)=f(5)+f(3)+f(2)=10+4+2=16$

通过此样例，可以看出，$f(n)$的值根据归约式进行递归计算，重复调用是此算法的重点。

---

💯思路解析

该题目的核心在于通过递归和记忆化算法实现函数计算。根据题目定义，我们可以将问题分解为以下步骤：

---

3.1 函数的递归定义

$f(n)$ 的值由三部分经结而成：

• $f(n-1)$：下一个数值的递归计算；
• $f(n//2)$：正整除的结果解析；
• $f(n//3)$：正整除法分解的值。

这三者求和即可实现函数的递归结果。

---

3.2 边界条件控制

• 当 $n\le 0$ 时，给出结果 $f(n)=0$，停止递归求和。
• 当 $n=1$ 时，固定值 $f(1)=x$ 。

---

3.3 记忆化搜索

在递归过程中，同样的函数值可能被重复计算。为了提高系统性能，通过存储计算结果实现记忆化，可以大大减少计算时间。

---

💯C++实现代码

#include <iostream>
using namespace std;

int x, n;
int memo[21]; // 因为n≤20，开数组即可。-1表示未计算。

int f(int m) {
    if (m <= 0) return 0;          // 边界条件：f(0)=0
    if (m == 1) return x;          // 特殊情况：f(1)=x
    if (memo[m] != -1) return memo[m]; // 如果已经计算过，直接返回
    memo[m] = f(m-1) + f(m/2) + f(m/3); // 递归定义f(m)
    return memo[m];
}

int main() {
    cin >> x >> n;
    for (int i = 0; i <= 20; i++) memo[i] = -1; // 初始化memo数组
    cout << f(n) << endl;         // 输决f(n)
    return 0;
}

---

💯添加解释

1. 算法核心：递归与记忆化

   • 递归实现大问题的分解，通过建立子问题的依赖关系逐步求解。
   • 记忆化通过存储中间计算结果，减少重复调用，优化时间复杂度。

2. 时间复杂度分析：

   • 由于记忆化的存在，每个状态最多仅被访问一次，因此时间复杂度为 $O(n)$；
   • 空间复杂度取出于递归深度和存储数组，为 $O(n)$。

3. 应用扩展：

   • 该方法不仅限于此类问题，还可推应到分治法、斐波那契数列、树式DP等递归与动态规划问题。

---

💯小结

• 
  本文通过对递归与记忆化算法的分析和 C++ 实现，给出了解决函数计算问题的优化思路。递归的分解和记忆化存储在进阶算法学习中具有重要的实际价值，它们是解决动态规划算法问题的基础。此外，大规模复杂问题也可以通过该思路求解，例如并行递归和动态应用等部分优化方案。

---

---