文章

3·子问题（递归，备忘录，动态规划，滚动数组）

发表于 更新于
作者 senlongan
9 分钟阅读

递归

  • 思想：将问题分解为相同子问题（函数调用自身），从而解决问题
  • 方向：自顶向下调用，自底向上执行，从子问题开始计算
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

int func(int n){//函数功能：返回n的阶乘
  //结束条件
  if(n <0)return-1;
  if(n ==0|| n ==1 )return n;
  //等价关系式
  return n *func(n -1);
}
int fibonacci(int i) {
   if(i <= 0) return 0;
   if(i == 1) return 1;
   return fibonacci(i-1) + fibonacci(i-2);
}
int fibonacci(int first, int second, int n) {//优化：滚动数组
    if (n <= 0) {
        return 0;
    }
    if (n < 3) {
        return 1;
    }
    else if (n == 3) {
        return first + second;
    }
    else {
        return fibonacci(second, first + second, n - 1);
    }
}
fibonacci(0, 1, n);

展开

  • 阶乘：n! = 1……n的乘积
  • 斐波那契数列：F (0)=0，F (1)=1, F (n)=F (n - 1)+F (n - 2)（n ≥ 2）
  • 步骤：
    • 明确函数功能
    • 状态转移方程：分解问题，找出函数的等价关系式
    • 返回条件（不能分解的基本问题）
  • 优点：对于某些问题递归要比循环思想简单许多
  • 缺点：存在函数调用的开销，子问题被大量重复调用，通常比迭代更低效
  • 时间复杂度：每次递归的时间复杂度 * 递归的次数（节点数量）
  • 空间复杂度：每次递归的空间复杂度 * 递归深度（树层数）
  • 以上复杂度分别是：n, 2^n, n
  • 图dfs：深度优先搜索
    • 数据结构：栈（向量）
    • 网格图：
      • 返回条件：超过边界，被访问过，找到了期望结果
      • 状态转移：从当前位置向4个递归
    • 临接图：
      • 返回条件：被访问过，找到了期望结果
      • 状态转移：从当前节点对所有邻居递归
    • 适用场景：快速找到可行路径（当首次找到目标，不能保证找到的是最短路径（构建树，目标节点出现在很多枝杈（路径）上，深度也不同））
    • 优势：内存占用少
  • 使用场景：通常问题有大量的组合方案，让我们计算可行的数量，或者最优选择

备忘录

1
2
3
4
5
6
7
8
9
10
11

vector<int> memo(n + 1, -1);
int fib_memo(int n, vector<int>& memo) {
    if (n <= 1) return n;
    // 如果已经计算过，直接返回结果
    if (memo[n] != -1) {
        return memo[n];
    }
    // 计算并存储结果
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo);
    return memo[n];
}

展开

  • 思想：将子问题计算结果保存，当遇到计算过的子问题，直接获取结果，避免重复计算子问题
  • 优点：优化递归的时间复杂度
  • 缺点：增加空间复杂度

动态规划DP

  • 思想：将问题分解为相同子问题，从子问题开始计算，并存储计算结果（在备忘录的基础上，更改计算方向）
  • 方向：自底向上，从子问题开始计算
  • 优点：相比于备忘录减少函数调用的开销
  • 步骤：
    • 明确函数功能
    • 状态转移方程
    • 明确dp数组元素的功能：子问题结果
    • 设置dp基本情况：不能分解的基本问题
    • 循环填充dp元素：自底向上计算

  • 01背包

    1
2
3
4
5
6
7
8
9
10
11
12
13
14

    int knapsack(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));//个数
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            if (j >= weights[i-1]) {
                dp[i][j] = max(dp[i-1][j], dp[i-1][j-weights[i-1]] + values[i-1]);
            } else {
                dp[i][j] = dp[i-1][j];
            }
        }
    }
    return dp[n][capacity];
}

    展开

    • 商品：重量wi，价值vi
    • 背包：容量
    • 问：如何才能获得最大的收益
    • 01：所有物品不可再分，要么整个装入背包，要么放弃
    • 状态转移方程：
      • 每个物体都有选和不选两种可能
      • 物体的重量<当前容量可以选和不选if (j >= w[i])：f[i][j] = max(f[i - 1][j], f[i - 1][j - w[i]] + v[j])
      • 只能不选else：f[i][j] = f[i - 1][j];
      • 横坐标 i 表示前i个物体，纵坐标 j 为当前背包容量

  • 完全背包

    1
2
3
4
5
6
7
8
9
10
11
12
13

    int completeKnapsack_2D(int capacity, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= capacity; j++) {
            dp[i][j] = dp[i-1][j];
            if (j >= weights[i-1]) {
                dp[i][j] = max(dp[i][j], dp[i][j - weights[i-1]] + values[i-1]);
            }
        }
    }
    return dp[n][capacity];
}

    展开

    • 完全：每个物品可以取无限次放入背包中
    • 状态转移方程：
      • 物体的重量<当前容量可以选if (j >= w[i])：f[i][j] = max(f[i][j], f[i][j - w[i]] + v[j]),i-1变为i，因为当前物品可选
      • 不能选else：f[i][j] = f[i - 1][j];

滚动数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

//循环
int func(int n){
  int d[n];
  d[0] =0;
  d[1] =1;
  for(int i =2; i <= n; i++){
    d[n] =d[n -1] +d[n -2];
  }
  return d[n];
}
//滚动数组
int func(int n){
  int d[3];
  d[1] =0;
  d[2] =1;
  for(int i =2; i <= n; i++){
    d[0] =d[1];
    d[1] =d[2];
    d[2] =d[0] +d[1];
  }
  return d[n];
}

展开

  • 思想：只分配依赖大小的空间
  • 优点：相比于普通dp减少空间复杂度

  • 使用场景：元素值只依赖前几个元素（一维）/ 前几行（二维）

    1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

    int knapsack_optimized(vector<int>& weights, vector<int>& values, int capacity) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0); 
    for (int i = 0; i < n; i++) {
        for (int j = capacity; j >= weights[i]; j--) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}
int completeKnapsack_1D(int capacity, vector<int>& weights, vector<int>& values) {
    int n = weights.size();
    vector<int> dp(capacity + 1, 0);
    for (int i = 0; i < n; i++) {
        for (int j = weights[i]; j <= capacity; j++) {
            dp[j] = max(dp[j], dp[j - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

    展开

  • 例子：斐波那契，爬楼梯，背包问题……
  • 注意：
    • dp数组：从二维变为一维
    • for循环方向：对于01背包：j改为反方向，依赖于上一行的值，避免覆盖，对于完全背包则不用，依赖于当前行的左侧元素，所以应该先计算左侧
    • 状态转移方程：本质不变，书写上变化
    • 返回结果：变为一维
算法与数据结构
本文由作者按照 CC BY 4.0 进行授权
本页总访问量次