C++爬楼梯——DFS、递归、动态规划、递推详解

C++爬楼梯——DFS、递归、动态规划、递推详解

引用

CSDN

1.

https://m.blog.csdn.net/2401_88591507/article/details/145271099

本文通过一个经典的爬楼梯问题，详细讲解了DFS、递归、动态规划和递推四种算法思想，并提供了C++代码实现。通过这个例子，读者可以深入理解这些算法的本质和应用场景。

动态规划

动态规划是一种将复杂问题分解为更小的子问题来解决的方法。其核心思想是：

• 分解子问题：将原问题分解为更小的子问题，直到子问题可以直接解决。
• 保存子问题答案：将子问题的答案保存起来，避免重复计算。
• 反推原问题解：根据子问题的答案，逐步推导出原问题的解。

递归

递归是一种通过函数自身调用来解决问题的方法。其过程可以分为两个阶段：

• "递"的过程：分解子问题的过程，自顶向下。
• "归"的过程：产生答案的过程，自底向上。

递归适用于以下情况：

1. 问题具有递归结构
2. 递归基和递归步骤清晰
3. 问题规模适中
4. 代码可读性优先

递归与栈的特性相似，遵循"后进先出"的原则。

递推

递推是递归的"归"的过程，通常用于动态规划中。递推公式对应于DFS向下递归的公式，递推数组的初始值对应于递归的边界条件。

记忆化搜索

记忆化搜索是递归的一种优化方法，通过保存已经计算过的子问题结果，避免重复计算。其核心思想是：

• 递归基：问题的最简单形式，可以直接求解。
• 递归步骤：将原问题分解为更小规模的子问题，并通过递归调用自身来解决这些子问题。

例题：爬楼梯问题

题目描述：一个楼梯共有 n 级台阶，每次可以走一级或者两级，问从第 0 级台阶走到第 n 级台阶一共有多少种方案。

输入格式：共一行，包含一个整数 n。

输出格式：共一行，包含一个整数，表示方案数。

数据范围：1≤n≤41

样例：

• 输入 10 输出 89
• 输入 19 输出 6765
• 输入 35 输出 14930352

此题本质就是斐波那契数列，long long类型可以存储下第101项的结果。

代码实现

代码一：DFS暴力搜索

#include<iostream>    
#include<algorithm>   
#include<cstring>     
using namespace std;  
using i64 = long long; 
int n;                 
i64 dfs(int x)
{
    if(x == 1) return 1;                
    else if(x == 2) return 2;           
    else return dfs(x - 1) + dfs(x - 2); 
}
int main()
{
    cin >> n;                           
    i64 ans = dfs(n);                   
    cout << ans << endl;                
    return 0;                           
}  

时间复杂度：O(2^n)，在n>41时会超时。

代码二：DFS记忆化搜索

通过引入记忆数组mem，将时间复杂度优化到O(n)。

#include<iostream>    
#include<algorithm>   
#include<cstring>     
using namespace std;  
using i64 = long long; 
const int N = 100;     
int n;                 
i64 mem[N];            
int dfs(int x)
{
    if(mem[x]) return mem[x]; 
    i64 sum = 0;              
    if(x == 1) sum = 1;       
    else if(x == 2) sum = 2;  
    else sum = dfs(x - 1) + dfs(x - 2); 
    mem[x] = sum;             
    return sum;               
}
int main()
{
    scanf("%d", &n);          
    i64 answer = dfs(n);      
    printf("%lld\n", answer); 
    return 0;                 
}  

代码思路分析：

1. 斐波那契数列的定义：F(1)=1，F(2)=2，F(n)=F(n−1)+F(n−2)。
2. 递归实现：通过dfs函数计算斐波那契数列的第x项。
3. 记忆化搜索：通过数组mem存储已经计算过的斐波那契数列的结果，避免重复计算。

代码三：动态规划

使用迭代方法计算斐波那契数列，避免递归调用。

#include<iostream>    
using namespace std;  
using i64 = long long; 
const int N = 100;    
i64 dp[N] = {0};      
int main()
{
    int n;            
    cin >> n;         
    dp[1] = 1;        
    dp[2] = 2;        
    for(int i = 3; i <= n; i++) 
    {
        dp[i] = dp[i - 1] + dp[i - 2]; 
    }
    cout << dp[n] << endl; 
    return 0;         
}  

代码功能说明：

1. 使用数组dp存储斐波那契数列的值，避免重复计算。
2. 初始化dp[1]为1，dp[2]为2。
3. 通过循环计算斐波那契数列的值，直到第n项。

代码四：空间优化

将空间复杂度优化到O(1)。

#include<iostream>    
using namespace std;  
using i64 = long long; 
int main()
{
    int n;            
    cin >> n;         
    i64 a = 1, b = 2, c; 
    if(n == 1) cout << a << endl;  
    else if(n == 2) cout << b << endl; 
    else
    {
        for(int i = 3; i <= n; i++) 
        {
            c = a + b;  
            a = b;      
            b = c;      
        }
        cout << c << endl; 
    }
    return 0;         
}  

通过只存储前两项的值，将空间复杂度优化到O(1)。