动态规划

code: dynamic_programming

1. 问题分析

1.1 问题定义

问题：假设要爬n阶楼梯，每次可以爬1阶或2阶，问有多少种不同的方法可以爬到楼顶。

示例：

  • n=1：只有1种方法（1）
  • n=2：有2种方法（1+1, 2）
  • n=3：有3种方法（1+1+1, 1+2, 2+1）

1.2 数学递推关系

1
dp[n] = dp[n-1] + dp[n-2]

解释：到达第n阶楼梯，可以从第n-1阶爬1阶上来，或者从第n-2阶爬2阶上来。

2. 各算法实现详细解析

2.1 暴力递归算法 (ViolentRecursion)

1
2
3
4
5
6
7
int32_t ViolentRecursion::ClimbStairs(uint32_t stairFloors)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    return ClimbStairs(stairFloors - 1) + ClimbStairs(stairFloors - 2);
}

算法思想：直接根据递推公式进行递归计算。

时间复杂度分析：

  • 形成二叉树递归结构，高度为n
  • 时间复杂度：O(2^n) - 指数级复杂度
  • 空间复杂度：O(n) - 递归栈深度

缺点：存在大量重复计算。例如计算ClimbStairs(5)时：

  • ClimbStairs(3)被计算了2次
  • ClimbStairs(2)被计算了3次
  • ClimbStairs(1)被计算了5次

2.2 记忆化搜索算法 (MemoryBasedSearch)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int32_t MemoryBasedSearch::ClimbStairs(uint32_t stairFloors)
{
    std::vector<int32_t> memo(stairFloors + 1, -1);  // 关键：大小为 stairFloors + 1
    return Dfs(stairFloors, memo);
}

int32_t MemoryBasedSearch::Dfs(uint32_t stairFloors, std::vector<int32_t> &memo)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    if (memo[stairFloors] != -1) {  // 如果已经计算过，直接返回结果
        return memo[stairFloors];
    }
    memo[stairFloors] = Dfs(stairFloors - 1, memo) + Dfs(stairFloors - 2, memo);
    return memo[stairFloors];
}

算法思想：在递归基础上增加记忆化，避免重复计算。

时间复杂度：O(n) - 每个子问题只计算一次

空间复杂度：O(n) - 存储n个结果+递归栈深度

2.3 标准动态规划算法 (DynamicProgramming)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int32_t DynamicProgramming::ClimbStairs(uint32_t stairFloors)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    std::vector<int32_t> dp(stairFloors + 1);  // 同样需要+1的大小
    dp[1] = 1;
    dp[2] = 2;

    for (uint32_t i = 3; i <= stairFloors; ++i) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[stairFloors];
}

算法思想：自底向上构建解，从基础情况逐步推导到目标解。

动态规划三要素：

  1. 最优子结构：大问题的最优解包含小问题的最优解
  2. 重叠子问题：问题可以分解为重复的子问题
  3. 状态转移方程：dp[i] = dp[i-1] + dp[i-2]

时间复杂度：O(n)
空间复杂度：O(n)

2.4 空间优化版动态规划 (PerfDynamicProgramming)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int32_t PerfDynamicProgramming::ClimbStairs(uint32_t stairFloors)
{
    if (stairFloors <= 2) {
        return static_cast<int32_t>(stairFloors);
    }
    int32_t prev2 = 1; // dp[i-2]，对应1阶楼梯的解
    int32_t prev1 = 2; // dp[i-1]，对应2阶楼梯的解
    int32_t current;

    for (uint32_t i = 3; i <= stairFloors; ++i) {
        current = prev1 + prev2;  // 计算当前阶梯的解
        prev2 = prev1;           // 更新前两个阶梯的状态
        prev1 = current;
    }

    return prev1;  // 循环结束时，prev1存储的就是stairFloors的解
}

优化思想：观察状态转移方程发现，当前状态只依赖于前两个状态，因此不需要存储整个数组。

为什么prev2=1, prev1=2？

  • 这是初始化状态，对应楼梯数为1和2时的解
  • 当计算第3阶时：需要前两阶的解（1阶和2阶）
  • prev2代表dp[i-2]（1阶的解=1）
  • prev1代表dp[i-1]（2阶的解=2）

状态更新过程（以n=5为例）：

1
2
3
4
i=3: current = 2 + 1 = 3, prev2=2, prev1=3
i=4: current = 3 + 2 = 5, prev2=3, prev1=5  
i=5: current = 5 + 3 = 8, prev2=5, prev1=8
结果：8

时间复杂度：O(n)
空间复杂度：O(1) - 只使用常数个变量

3. 动态规划算法核心思想详解

3.1 动态规划的本质

动态规划是一种将复杂问题分解为简单子问题的算法思想，通过存储中间结果来避免重复计算。

3.2 动态规划的适用条件

  1. 最优子结构：问题的最优解包含其子问题的最优解
  2. 重叠子问题：递归算法会反复求解相同的子问题

3.3 动态规划的解题步骤

  1. 定义状态：dp[i]表示什么含义
  2. 确定状态转移方程：dp[i]与dp[i-1], dp[i-2]等的关系
  3. 初始化边界条件：最小子问题的解
  4. 确定计算顺序：自底向上或自顶向下
  5. 空间优化（可选）：减少存储空间

3.4 爬楼梯问题的状态定义

  • 状态：dp[i]表示爬i阶楼梯的方法数
  • 转移方程：dp[i] = dp[i-1] + dp[i-2]
  • 边界条件：dp[1] = 1, dp[2] = 2
  • 计算顺序：从3到n依次计算

4. 性能对比分析

4.1 时间复杂度对比

算法 时间复杂度 适用场景
暴力递归 O(2^n) 教学演示，实际不可用
记忆化搜索 O(n) 递归思维，中等规模
标准动态规划 O(n) 通用解法，易于理解
优化动态规划 O(n) 生产环境，空间最优

4.2 空间复杂度对比

算法 空间复杂度 说明
暴力递归 O(n) 递归栈空间
记忆化搜索 O(n) 记忆数组+递归栈
标准动态规划 O(n) DP数组
优化动态规划 O(1) 常数个变量