当前位置：首页 > article >正文

力扣第 62 题（Unique Paths）两种递归实现

article 2024/11/26 0:46:52

直接递归的效率会非常低，因为会重复计算许多子问题。这种方法可以结合记忆化搜索（递归 + 缓存）优化效率，使其在合理的时间内求解问题。

递归解法

1. 基本递归（不推荐）

直接递归的思路是，从起点到终点有两种选择：向下或向右。总路径数等于向下和向右的路径数之和：

如果从位置 $(i, j)$ 出发：

$f (i, j) = f (i + 1, j) + f (i, j + 1)$

递归终止条件：

如果机器人超出边界，返回 0。
如果到达右下角，返回 1。

int uniquePathsRecursive(int m, int n) {
    if (m == 1 || n == 1) {
        return 1; // 到达边界，只有一条路径
    }
    return uniquePathsRecursive(m - 1, n) + uniquePathsRecursive(m, n - 1);
}

问题：

时间复杂度： $O(2^{m+n})$ ，因为递归会重复计算大量相同的子问题，效率非常低。

2. 记忆化搜索（递归 + 缓存）

为了解决重复计算的问题，可以使用一个二维数组缓存已经计算过的结果。

思路：

创建一个二维数组 memo[m][n]，用来存储从 $(i, j)$ 出发到右下角的路径数。
如果 memo[i][j] 已经计算过，直接返回。
否则按照递归公式计算，并将结果存储到 memo[i][j] 中。

实现代码：

#include <stdio.h>
#include <stdlib.h>

// 递归辅助函数
int dfs(int m, int n, int i, int j, int** memo) {
    // 如果超出边界，返回 0
    if (i >= m || j >= n) {
        return 0;
    }
    // 如果到达终点，返回 1
    if (i == m - 1 && j == n - 1) {
        return 1;
    }
    // 如果已经计算过，直接返回缓存的结果
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    // 递归计算路径数，并存入缓存
    memo[i][j] = dfs(m, n, i + 1, j, memo) + dfs(m, n, i, j + 1, memo);
    return memo[i][j];
}

// 主函数
int uniquePaths(int m, int n) {
    // 创建缓存数组并初始化为 -1
    int** memo = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        memo[i] = (int*)malloc(n * sizeof(int));
        for (int j = 0; j < n; j++) {
            memo[i][j] = -1;
        }
    }

    // 调用递归函数
    int result = dfs(m, n, 0, 0, memo);

    // 释放内存
    for (int i = 0; i < m; i++) {
        free(memo[i]);
    }
    free(memo);

    return result;
}

int main() {
    int m = 3, n = 7;
    printf("不同路径的数量: %d\n", uniquePaths(m, n));
    return 0;
}