【递归与动态规划(DP) C/C++】(1)递归 与 动态规划(DP)

发布于:2025-03-18 ⋅ 阅读:(19) ⋅ 点赞:(0)

- 第 82 篇 -
Date: 2025 - 03 - 17
Author: 郑龙浩/仟濹
【递归与动态规划(DP) C/C++】

一 递归

我看的课程,如下视频链接

https://www.bilibili.com/video/BV1LiS1YSEgF/?share_source=copy_web&vd_source=123565abb60ee9d849adaeb118d98b85

1基本介绍

是什么

递归就是函数自己调用自己。

核心

将大问题分解成规模更小的相同问题,直到达到可直接求解的简单情况(如 n=1),再逐层返回结果。
优化 - 记忆化搜索

如果过程中会出现重复计算,则可以提前将重复计算保存下来

2 递归技巧

(1) 递归三步法

  1. 定义基准条件(确定结束条件)

    明确递归终止的边界条件(如 阶乘时的n=1 ),避免无限递归

  2. 假设子问题已解决
    将递归函数视为黑盒,直接假设它能返回子问题的正确结果(例如:算 f(n) 时,直接相信 f(n-1)f(n-2) 是对的)

    说简单点就是: 只管向问问题,它一定能返回正确答案。

  3. 组合子问题的解(拆解问题)

    用子问题的解构建当前问题的解(如 return f(n-1) + f(n-2)

    说简单点就是: 把子问题的答案组合起来,得到当前问题的解

(2) 思维小技巧

无需提前理解完整递归过程!!!

我之前就陷入了这个问题。就是我在写递归的时候,必须想清楚递归从头到尾的所有过程和细节,其实没有必要,直接当作这个递归函数已经存在且写完

递归是「自相似性」的数学抽象,只需关注当前层逻辑,无需脑补调用栈细节(如 f(n-1) 内部如何实现)

不要陷入 “先有鸡还是先有蛋“ 的思维陷阱!!!

一定要注意,我之前因为陷入这个思维陷阱,特别较真,特别想搞清楚具体过程,太没必要了

  • 直接假设递归函数已能正确工作(即使它尚未写完),基于此设计当前逻辑。这种「信任递归」的思维是突破递归障碍的关键
  • 即直接将没写完的递归函数当作已经有了的函数去写,就认为这个函数是有答案的,这么去写就可以了,无需把这个递归函数中的自身的函数当作递归函数
  • 禁止:在编码时脑补多级递归调用的堆栈状态

3 例题

(1) 阶乘 (纯递归 or DP)

不使用记忆化搜索 Or 使用记忆化搜索

// 2025-03-16
#include <bits/stdc++.h>
using namespace std;
// 不使用记忆化搜索
long long funA( long long n ) {
    if (n == 1)
        return 1;
    return funA(n - 1) * n;
}
// 使用记忆化搜索
// 使用数组或哈希表记忆
unordered_map <long long, long long> memo;
long long funB( long long n ) {
    if (n == 1)
        return 1;
    if (memo.find(n) == memo.end()) {
        memo[n] = funB(n - 1) * n;
    }
    return memo[n];
}

int main( void ) {
    long long n;
    cin >> n;
    // 不使用记忆化搜索
    cout << "不使用记忆化搜索的答案:" << funA(n) << '\n';
    // 使用记忆化搜索
    cout << "使用记忆化搜索的答案:" << funB(n) << '\n';
    return 0;
}

(2) 斐波那契数列 (纯递归 or DP)

不使用记忆化搜索 Or 使用记忆化搜索

// 2025-03-16
#include <bits/stdc++.h>
using namespace std;
// 不使用记忆化搜索
long long funA( long long n ) {
    if (n <= 2) return 1;
    return funA(n - 1) + funA(n - 2);
}
// 使用记忆化搜索
// 使用数组或哈希表记忆
unordered_map <long long, long long> memo;
long long funB( long long n ) {
    if (n <= 2) return 1;
    if (memo.find(n) == memo.end())
        memo[n] = funB(n - 1) + funB(n - 2);
    return memo[n];
}

int main( void ) {
    // 第n位斐波那契数字
    long long n;
    cin >> n;
    // 不使用记忆化搜索
    cout << "不使用记忆化搜索的答案:" << funA(n) << '\n';
    // 使用记忆化搜索
    cout << "使用记忆化搜索的答案:  " << funB(n) << '\n';
    return 0;
}

(3) 汉诺塔 (纯递归 or DP)

必须要注意,打印的不是 前 n 个 圆盘从某个柱子移动到某个柱子,而是 第 n 个 圆盘从某个柱子移动到某个柱子。

我刚开始想了好久,就是这个地方理解错了,我以为打印的是 前 n 个 圆盘,后来意识到是 第 n 个 圆盘以后,恍然大悟,理解了这个程序。

然后为了助于我理解,我又写了一个中文打印过程版本,以免以后复习的时候,看到这个英文打印的代码又理解错了。

① 英文打印过程的版本

代码

// 2025-03-16
// 输入圆盘数量,三个柱子标识
// 打印圆盘的移动过程: 移动数量 from ? to ? ---> 错误理解
// 打印圆盘的移动过程: 第n个 from ? to ? (这个意思是第 n 个 从 ? 移动到 ?) --> 正确理解
// 注意:该题要求的是移动过程的输出,而不是真的移动,所以不要钻牛角尖,我想了半天为什么只打印不移动,实际人家要的结果就是打印
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char F, char A, char T) {
    if (n == 1) { // 递归终止条件:只剩一个盘子时直接移动
        // 打印:move 1 from A to C
        // 打印:移动第 n 个盘子到目标柱 T
        printf("move %d from %c to %c\n", n, F, T);
        return;
    }
    // 步骤1:将前 n-1 个盘子从 F 移到 A(借助 T 辅助)
    hanoi(n - 1, F, T, A); 
    // 步骤2:打印:移动第 n 个盘子到目标柱 T
    printf("move %d from %c to %c\n", n, F, T);
    // 步骤3:将 n-1 个盘子从 A 移到 T(借助 F 辅助)
    hanoi(n - 1, A, F, T);
}
int main( void ) {
    int n, F, A, T;
    cout << "请输入圆盘数量" << endl;
    cin >> n;getchar();
    cout << "请输入起始柱、辅助柱、目标柱" << endl;
    scanf ("%c %c %c", &F, &A, &T);
    hanoi (n, F, A, T);
    return 0;
}

输入与运行结果

请输入圆盘数量
3
请输入起始柱、辅助柱、目标柱
A B C
move 1 from A to C
move 2 from A to B
move 1 from C to B
move 3 from A to C
move 1 from B to A
move 2 from B to C
move 1 from A to C
② 中文打印过程的版本(为了避免自己以后复习的时候又理解错误,故写了中文打印版本)

为了避免自己以后复习的时候又理解错误,故写了中文打印版本

代码

// 2025-03-16
// 输入圆盘数量,三个柱子标识
// 打印圆盘的移动过程: 移动数量 from ? to ? ---> 错误理解
// 打印圆盘的移动过程: 第n个 from ? to ? (这个意思是第 n 个 从 ? 移动到 ?) --> 正确理解
// 注意:该题要求的是移动过程的输出,而不是真的移动,所以不要钻牛角尖,我想了半天为什么只打印不移动,实际人家要的结果就是打印
#include <bits/stdc++.h>
using namespace std;
void hanoi(int n, char F, char A, char T) {
    if (n == 1) { // 递归终止条件:只剩一个盘子时直接移动
        // 打印:move 1 from A to C
        // 打印:移动第 n 个盘子到目标柱 T
        printf("将第 %d 个圆盘从 %c 柱子移动到 %c 柱子\n", n, F, T);
        return;
    }
    // 步骤1:将前 n-1 个盘子从 F 移到 A(借助 T 辅助)
    hanoi(n - 1, F, T, A); 
    // 步骤2:打印:移动第 n 个盘子到目标柱 T
    printf("将第 %d 个圆盘从 %c 柱子移动到 %c 柱子\n", n, F, T);
    // 步骤3:将 n-1 个盘子从 A 移到 T(借助 F 辅助)
    hanoi(n - 1, A, F, T);
}
int main( void ) {
    int n, F, A, T;
    cout << "请输入圆盘数量" << endl;
    cin >> n;getchar();
    cout << "请输入起始柱、辅助柱、目标柱" << endl;
    scanf ("%c %c %c", &F, &A, &T);
    hanoi (n, F, A, T);
    return 0;
}

输入与运行结果

请输入圆盘数量
3
请输入起始柱、辅助柱、目标柱
A B C
将第 1 个圆盘从 A 柱子移动到 C 柱子
将第 2 个圆盘从 A 柱子移动到 B 柱子      
将第 1 个圆盘从 C 柱子移动到 B 柱子      
将第 3 个圆盘从 A 柱子移动到 C 柱子      
将第 1 个圆盘从 B 柱子移动到 A 柱子      
将第 2 个圆盘从 B 柱子移动到 C 柱子      
将第 1 个圆盘从 A 柱子移动到 C 柱子