大厂高频经典面试题-《递归和动态规划合集》_动态规划常见面试题

让你彻底掌握递归和动态规划的常用算法和场景应用。
✅1、所有示例代码，均可正常编译运行。同时文中也贴出了运行结果，一目了然，非常方便学习。
✅2、对于复杂些的流程和算法，都标配了图解，拆开代码表象，深入逻辑本质。一步一步的图解整个算法过程，帮助理解复杂表象背后蕴含的简单道理。
✅3、所有示例代码，均配备有详细注释，流程描述，时间复杂度说明，算法复杂度说明。多维度，多视角，透彻理解各个知识点。

以下是关于递归和动态规划的常见面试题合集：

大厂高频经典面试题(49)-递归乘法

大厂高频经典面试题(50)-汉诺塔问题

大厂高频经典面试题(51)-不重复字符串排列组合

大厂高频经典面试题(52)-重复字符串排列组合

大厂高频经典面试题(53)-括号组合

大厂高频经典面试题(54)-颜色填充

大厂高频经典面试题(55)-硬币组合

大厂高频经典面试题(56)-八皇后摆法

大厂高频经典面试题(57)-堆箱子

大厂高频经典面试题(58)-布尔运算

《深入理解递归与动态规划：原理、应用及代码实现》

一、递归与动态规划基础概念回顾

（一）递归的定义与本质

递归，简单来说，就是在函数的定义中使用函数自身的方法。它的核心在于：将一个复杂问题，分解为规模更小的相似子问题，通过不断解决这些子问题，最终解决原问题。

就像我们在日常生活中整理书架，如果要整理一个大书架，我们可以把它看作是由多个小部分组成，先整理好每个小部分（小格子），再将这些小部分的整理结果组合起来，完成整个书架的整理。

例如计算第n项斐波那契数列，斐波那契数列的定义为：$F(n)=F(n-1)+F(n-2)$，$F(0)=0$，$F(1)=1$ 。用递归方法实现的代码如下：

int fibonacci(int n) { if (n == 0) return 0; if (n == 1) return 1; return fibonacci(n - 1) + fibonacci(n - 2);}

在这段代码中，fibonacci函数不断调用自身，通过解决n - 1和n - 2的子问题来计算n的斐波那契值。

（二）递归的解题思路

1）自底向上的递归

自底向上的递归是从最基础的情况开始，逐步构建出更大规模问题的解。以计算斐波那契数列为例，我们先确定最基础的F(0)和F(1)的值，然后根据这两个基础值，逐步计算出F(2)、F(3)……直到我们需要的F(n)。就好比搭建一座积木塔，从最底层的积木开始，一块一块往上搭，每一层都依赖于下面的层。

这种方式的优点是直观易懂，代码实现相对简单，缺点是可能会计算一些不必要的中间结果，导致效率较低。

2）自上而下的递归

自上而下的递归则是从问题的整体出发，将规模为N的问题分解为多个子问题，通过解决这些子问题来得到原问题的解。在分解过程中，需要注意子问题是否存在重叠。比如在计算斐波那契数列时，我们从F(n)开始，将其分解为F(n - 1)和F(n - 2)两个子问题，然后继续分解这两个子问题，直到遇到基础情况。

这种方式的优点是，可以根据问题的特点灵活地分解问题，但实现起来可能相对复杂，并且由于可能会重复计算相同的子问题，也会影响效率。

3）数据分割的递归

数据分割的递归是将数据集分成两半，分别对这两半进行处理，然后将结果合并。

二分查找和归并排序是典型的例子。二分查找在一个排序数组中查找目标元素时，先将数组分成两半，判断目标元素在左半部分还是右半部分，然后在相应的半部分继续查找，直到找到目标元素或确定目标元素不存在。归并排序则是先将数组不断分成两半，分别对这两半进行排序，最后将排序好的两半合并成一个有序数组。

这种递归方式适用于可以将数据进行有效分割和合并的问题，提高算法的效率。

（三）递归与迭代的比较

递归算法虽然简洁明了，但它存在一个明显的问题，就是空间复杂度较高。每一次递归调用都会在栈中增加一层新的方法调用，当递归深度较大时，会占用大量的栈空间，甚至可能导致栈溢出。例如在计算斐波那契数列时，如果n的值较大，递归调用的层数会非常多，对栈空间的消耗就会很大。

而迭代算法则是通过循环的方式来解决问题，它避免了递归调用带来的栈空间消耗。所有的递归算法都可以用迭代算法实现，只是有些情况下，迭代算法的代码可能会更加复杂。比如计算斐波那契数列的迭代代码如下：

int fibonacciIterative(int n) { if (n == 0) return 0; if (n == 1) return 1; int a = 0, b = 1, c; for (int i = 2; i <= n; i++) { c = a + b; a = b; b = c; } return c;}

在这段代码中，我们使用了三个变量a、b和c，通过循环不断更新它们的值，最终得到F(n)的值。这种方式在空间复杂度上明显优于递归算法，适合处理大规模数据的计算。

（四）动态规划的概念与核心思想

动态规划通过把原问题分解为相对简单的子问题，并缓存子问题的结果来避免重复计算，从而解决复杂问题。它的核心思想是利用已经解决的子问题的结果，来解决更大规模的问题。这就好比我们在旅行中，如果已经知道了从A地到B地的最短路线，以及从B地到C地的最短路线，那么当我们要从A地到C地时，就可以直接利用这些已知的最短路线信息，不再需要重新计算所有可能的路线。

在实际应用中，动态规划通常用于解决具有最优子结构性质和子问题重叠性质的问题。最优子结构性质指的是问题的最优解可以由子问题的最优解组合而成，子问题重叠性质则是指在解决问题的过程中，会反复出现相同的子问题。例如在计算斐波那契数列时，F(n - 1)和F(n - 2)这两个子问题在计算F(n)时会被多次用到，这就是子问题重叠的体现。

（五）动态规划的实现方式 - 记忆法

记忆法是动态规划的一种重要实现方式。它通过缓存已经计算过的子问题的结果，避免在后续计算中重复计算这些子问题，从而提高算法的效率。以斐波那契数列为例，可以使用一个数组来缓存已经计算过的斐波那契值，代码如下：

int fibonacciMemoized(int n, int* memo) { if (n == 0 || n == 1) return n; if (memo[n] == 0) { memo[n] = fibonacciMemoized(n - 1, memo) + fibonacciMemoized(n - 2, memo); } return memo[n];}int fibonacci(int n) { int *memo = new int[n + 1](); int result = fibonacciMemoized(n, memo); delete[] memo; return result;}

在这段代码中，我们定义了一个memo数组，用于存储已经计算过的斐波那契值。在fibonacciMemoized函数中，每次计算一个新的斐波那契值之前，先检查memo数组中是否已经存在该值，如果存在，则直接返回，避免了重复计算。这种方式大大提高了计算效率，使得原本指数级时间复杂度的递归算法，优化为线性时间复杂度。

（六）自底向上的动态规划实现

除了记忆法这种自上而下的动态规划实现方式，还可以采用自底向上的方式来实现动态规划。还是以斐波那契数列为例，我们从最基础的F(0)和F(1)开始，逐步计算出F(2)、F(3)……直到F(n)。代码如下：

int fibonacciBottomUp(int n) { if (n == 0) return 0; if (n == 1) return 1; int *dp = new int[n + 1](); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[i] = dp[i - 1] + dp[i - 2]; } int result = dp[n]; delete[] dp; return result;}

在这段代码中，我们使用了一个dp数组来存储计算过程中的斐波那契值。从dp[2]开始，每个值都是由前两个值相加得到，通过这种方式，逐步构建出了整个斐波那契数列，最终得到F(n)的值。这种自底向上的方式同样避免了重复计算，并且代码实现相对简洁，易于理解。

二、递归与动态规划的应用场景

（一）递归的应用场景

1）树与图的遍历

在树和图的遍历算法中，递归有着广泛的应用。例如二叉树的前序遍历、中序遍历和后序遍历，都是基于递归的思想实现的。以中序遍历为例，其遍历顺序是先访问左子树，再访问根节点，最后访问右子树。代码实现如下：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};void inorderTraversal(TreeNode* root) { if (root != NULL) { inorderTraversal(root->left); std::cout << root->val << \" \"; inorderTraversal(root->right); }}

在这段代码中，inorderTraversal函数通过递归调用自身，实现了对二叉树的中序遍历。这种递归方式简洁明了，能够清晰地表达遍历的逻辑。

2）分治算法

分治算法是递归的一个重要应用领域。分治算法的基本思想是将一个规模较大的问题分解为若干个规模较小的子问题，分别解决这些子问题，然后将子问题的解合并起来，得到原问题的解。

归并排序和快速排序就是典型的分治算法。以归并排序为例，它先将数组分成两半，分别对这两半进行排序，然后将排序好的两半合并成一个有序数组。代码实现如下：

void merge(int arr[], int temp[], int left, int mid, int right) { int i = left; int j = mid + 1; int k = left; while (i <= mid && j <= right) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; } } while (i <= mid) { temp[k++] = arr[i++]; } while (j <= right) { temp[k++] = arr[j++]; } for (i = left; i <= right; i++) { arr[i] = temp[i]; }}void mergeSort(int arr[], int temp[], int left, int right) { if (left < right) { int mid = (left + right) / 2; mergeSort(arr, temp, left, mid); mergeSort(arr, temp, mid + 1, right); merge(arr, temp, left, mid, right); }}

在这段代码中，mergeSort函数通过递归不断将数组分成两半，然后在merge函数中进行合并，实现了对数组的排序。分治算法利用递归的特性，将复杂的问题分解为简单的子问题，使得算法的实现更加清晰和高效。

3）回溯算法

回溯算法也是基于递归的思想。它常用于解决一些组合优化问题，如八皇后问题、迷宫问题等。

以八皇后问题为例，该问题要求在8×8的棋盘上放置8个皇后，使得它们互不攻击（即任意两个皇后不能在同一行、同一列或同一对角线上）。题目库中也有八皇后这个例子，可以去详细参考。

我们可以使用回溯算法来解决这个问题，通过递归尝试在每一行放置皇后，当发现当前位置无法放置皇后时，回溯到上一步，重新尝试其他位置。代码实现如下：

bool isSafe(int board[8][8], int row, int col) { int i, j; for (i = 0; i < col; i++) { if (board[row][i]) return false; } for (i = row, j = col; i >= 0 && j >= 0; i--, j--) { if (board[i][j]) return false; } for (i = row, j = col; j >= 0 && i < 8; i++, j--) { if (board[i][j]) return false; } return true;}bool solveNQueens(int board[8][8], int col) { if (col >= 8) return true; for (int i = 0; i < 8; i++) { if (isSafe(board, i, col)) { board[i][col] = 1; if (solveNQueens(board, col + 1)) return true; board[i][col] = 0; } } return false;}

在这段代码中，solveNQueens函数通过递归不断尝试在每一列放置皇后，isSafe函数用于检查当前位置是否可以放置皇后。如果在某一列找到了合适的位置，就继续递归放置下一列的皇后；如果在某一列找不到合适的位置，就回溯到上一列，重新尝试其他位置。这种回溯的方式能够有效地避免不必要的计算，提高解决问题的效率。

（二）动态规划的应用场景

1）背包问题

背包问题是动态规划的经典应用之一。假设有一个背包，它的容量为W，有n个物品，每个物品都有重量w[i]和价值v[i]。我们需要在这些物品中选择一些放入背包，使得背包中物品的总价值最大，同时总重量不能超过背包的容量。这个问题可以用动态规划来解决。我们定义一个二维数组dp[n + 1][W + 1]，其中dp[i][j]表示在前i个物品中选择物品放入容量为j的背包时，所能获得的最大价值。状态转移方程为：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) ，当j >= w[i]时；dp[i][j] = dp[i - 1][j] ，当j < w[i]时。代码实现如下：

int knapsack(int w[], int v[], int W, int n) { int dp[n + 1][W + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= W; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (w[i - 1] <= j) { dp[i][j] = std::max(dp[i - 1][j], dp[i - 1][j - w[i - 1]] + v[i - 1]); } else { dp[i][j] = dp[i - 1][j]; } } } return dp[n][W];}

在这段代码中，我们通过两层循环遍历物品和背包容量，根据状态转移方程不断更新dp数组的值，最终得到在给定条件下的最大价值。

2）最长公共子序列问题

最长公共子序列问题是指在两个序列中，找出一个最长的子序列，使得这个子序列在两个原始序列中都出现，且顺序一致。

例如，对于序列{1, 3, 4, 5, 6, 7, 7, 8}和{3, 5, 7, 4, 8, 6, 7, 8, 2}，它们的最长公共子序列是{3, 5, 7, 8} 。我们可以用动态规划来解决这个问题。定义一个二维数组dp[m + 1][n + 1]，其中m和n分别是两个序列的长度，dp[i][j]表示第一个序列的前i个元素和第二个序列的前j个元素的最长公共子序列的长度。状态转移方程为：dp[i][j] = dp[i - 1][j - 1] + 1 ，当a[i - 1] == b[j - 1]时；dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) ，当a[i - 1] != b[j - 1]时。代码实现如下：

int longestCommonSubsequence(std::string a, std::string b) { int m = a.size(); int n = b.size(); int dp[m + 1][n + 1]; for (int i = 0; i <= m; i++) { for (int j = 0; j <= n; j++) { if (i == 0 || j == 0) { dp[i][j] = 0; } else if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1; } else { dp[i][j] = std::max(dp[i - 1][j], dp[i][j - 1]); } } } return dp[m][n];}

（三）动态规划的优化技巧

1）空间优化

在动态规划中，我们常常使用二维数组来存储状态，但在一些情况下，通过观察状态转移方程，我们可以发现当前状态只依赖于之前的某些状态，因此可以使用滚动数组将空间复杂度从二维优化到一维。以背包问题为例，原本我们使用dp[i][j]来表示状态，实际上在计算dp[i][j]时，只用到了dp[i - 1][j]和dp[i - 1][j - w[i]]，所以可以将二维数组优化为一维数组。优化后的代码如下：

int knapsackSpaceOptimized(int w[], int v[], int W, int n) { int dp[W + 1] = {0}; for (int i = 0; i < n; i++) { for (int j = W; j >= w[i]; j--) { dp[j] = std::max(dp[j], dp[j - w[i]] + v[i]); } } return dp[W];}

这里内层循环从大到小遍历，是为了保证在计算dp[j]时，dp[j - w[i]]仍然是上一轮的状态，避免重复计算。

2）减少不必要的计算

在动态规划过程中，我们可以通过分析问题的特性，减少不必要的计算。例如在最长公共子序列问题中，如果两个序列的长度差异很大，我们可以选择较短的序列作为外层循环，这样可以减少内层循环的次数，提高效率。同时，在计算状态时，可以提前判断一些不可能产生最优解的情况，直接跳过相应的计算。

（四）递归与动态规划的结合应用

在实际问题中，递归和动态规划常常结合使用。例如在解决一些复杂的树状结构问题时，我们可以先使用递归的方式遍历树，在遍历过程中，利用动态规划的思想来记录和更新一些状态信息。以求解二叉树中最大路径和问题为例，我们需要找到一条从树中某个节点到另一个节点的路径，使得这条路径上的节点值之和最大。我们可以通过递归遍历二叉树，在每个节点处计算以该节点为起点的最大路径和，并记录全局最大路径和。在递归过程中，我们使用动态规划的思想，保存已经计算过的节点的最大路径和，避免重复计算。代码实现如下：

struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};int maxPathSumHelper(TreeNode* root, int& maxSum) { if (!root) return 0; int leftMax = std::max(0, maxPathSumHelper(root->left, maxSum)); int rightMax = std::max(0, maxPathSumHelper(root->right, maxSum)); int currentPathSum = root->val + leftMax + rightMax; maxSum = std::max(maxSum, currentPathSum); return root->val + std::max(leftMax, rightMax);}int maxPathSum(TreeNode* root) { int maxSum = INT_MIN; maxPathSumHelper(root, maxSum); return maxSum;}

在这段代码中，maxPathSumHelper函数通过递归遍历二叉树，在每个节点处计算以该节点为起点的最大路径和，并更新全局最大路径和maxSum。这里既利用了递归的遍历特性，又结合了动态规划保存中间状态的思想。

三、递归与动态规划常见问题及解决方案

（一）递归深度过大导致栈溢出

递归深度过大是递归算法常见的问题，当递归调用的层数过多时，会耗尽栈空间，导致栈溢出错误。为了解决这个问题，除了前面提到的将递归转换为迭代的方法外，还可以使用尾递归优化。尾递归是指在递归函数中，递归调用是函数的最后一个操作。在一些支持尾递归优化的编程语言中，编译器可以将尾递归转换为迭代形式，从而避免栈溢出问题。例如在计算阶乘的递归函数中：

// 普通递归计算阶乘int factorial(int n) { if (n == 0 || n == 1) return 1; return n * factorial(n - 1);}// 尾递归计算阶乘int factorialTailRecursion(int n, int acc = 1) { if (n == 0 || n == 1) return acc; return factorialTailRecursion(n - 1, n * acc);}

在factorialTailRecursion函数中，递归调用factorialTailRecursion(n - 1, n * acc)是函数的最后一个操作，这就是尾递归。在支持尾递归优化的环境中，这种方式可以避免栈溢出问题。

（二）动态规划状态定义与转移方程的确定

在使用动态规划解决问题时，正确定义状态和状态转移方程是关键。但这往往也是最具挑战性的部分，需要对问题进行深入分析。在定义状态时，要确保状态能够完整地描述问题的子问题，并且状态之间具有递推关系。在确定状态转移方程时，可以通过列举一些简单的例子，观察状态之间的变化规律来推导。同时，要注意边界条件的处理，确保状态转移方程在所有情况下都正确。

例如在编辑距离问题中，我们需要计算两个字符串之间的编辑距离（即通过插入、删除或替换字符，将一个字符串转换为另一个字符串所需的最少操作次数）。定义dp[i][j]表示将字符串str1的前i个字符转换为字符串str2的前j个字符所需的最少操作次数。状态转移方程为：

if (str1[i - 1] == str2[j - 1]) { dp[i][j] = dp[i - 1][j - 1];} else { dp[i][j] = 1 + std::min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});}

这里通过比较两个字符串当前位置的字符是否相等，来确定状态的转移方式。同时，要注意dp[0][0] = 0，以及dp[i][0] = i和dp[0][j] = j这些边界条件的处理。

（三）子问题重叠的识别与处理

子问题重叠是动态规划能够发挥优势的基础，但在实际应用中，有些问题的子问题重叠并不明显，需要我们仔细分析。在识别出子问题重叠后，我们可以使用记忆化搜索或自底向上的动态规划方法来避免重复计算。

例如在计算组合数C(n, k)时，我们知道C(n, k) = C(n - 1, k - 1) + C(n - 1, k)，这就存在子问题重叠的情况。我们可以使用动态规划来解决：

int combination(int n, int k) { int dp[n + 1][k + 1]; for (int i = 0; i <= n; i++) { for (int j = 0; j <= std::min(i, k); j++) { if (j == 0 || j == i) { dp[i][j] = 1; } else { dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]; } } } return dp[n][k];}

在这段代码中，我们通过二维数组dp记录已经计算过的组合数，避免了重复计算，提高了效率。

感谢您的阅读。原创不易，如您觉得有价值，请点赞，关注。