在算法面试领域，动态规划占据着极为关键的地位，是众多大厂面试考查的重点。动态规划旨在将复杂问题拆解为一系列相互关联的子问题，通过求解子问题并存储其结果，避免重复计算，从而高效地解决原问题。本文将深入剖析动态规划的核心概念，包括最优子结构、重叠子问题等。详细阐述其解题的一般步骤，如状态定义、转移方程推导、边界初始化等。同时，对算法面试中常见的动态规划高频题型，如背包问题、最长子序列问题等进行分类解析，并结合具体题目给出详细的解题思路与代码实现。无论是初次接触动态规划的新手，还是希望进一步提升解题能力的进阶者，都能从本文中获取深入理解动态规划、掌握解题技巧的助力，从而在算法面试中应对自如。​

一、动态规划基础概念​

1.1 定义与核心思想​

动态规划（Dynamic Programming，DP）是一种用于解决复杂问题的算法策略。其核心在于把一个复杂的问题分解成多个相互关联的子问题，通过求解这些子问题，再利用子问题的解来构建原问题的解。与分治法不同，动态规划允许子问题重叠，并且通常采用自底向上的方式求解，即先解决规模较小的子问题，逐步构建出规模较大问题的解。这种方法通过存储子问题的解（记忆化），避免了重复计算，从而显著提高了算法效率。​

1.2 关键要素​

1. 最优子结构：指一个问题的最优解可以由其子问题的最优解有效地构造出来。例如，在计算从起点到终点的最短路径问题中，如果存在一条经过中间节点的最短路径，那么从起点到该中间节点的路径以及从该中间节点到终点的路径，也分别是这两个子问题的最短路径。这种特性使得我们可以通过求解子问题的最优解来得到原问题的最优解。​

1. 重叠子问题：在解决问题的过程中，会出现大量重复计算相同子问题的情况。以斐波那契数列为例，计算第 n 项时，需要重复计算第 n - 1 项和第 n - 2 项等子问题。动态规划通过记录已经解决的子问题的解，当再次遇到相同子问题时，直接从记录中获取结果，避免了重复计算，大大提高了算法效率。​

1. 状态转移方程：是动态规划的核心，它描述了如何从一个状态转移到另一个状态，即如何根据子问题的解推导出原问题的解。例如，在斐波那契数列中，状态转移方程为 F (n) = F (n - 1) + F (n - 2)，其中 F (n) 表示第 n 项的值，通过前两项的值可以计算出当前项的值。状态转移方程的正确推导是解决动态规划问题的关键步骤。​

1.3 适用场景​

动态规划适用于具有最优子结构和重叠子问题的问题。常见的场景包括资源分配问题，如背包问题，在给定背包容量和物品重量、价值的情况下，如何选择物品以最大化背包内物品的总价值；路径规划问题，如寻找地图上两点之间的最短路径；序列问题，如最长公共子序列问题，找出两个序列中最长的相同子序列。当遇到一个问题时，可以尝试分析它是否具备这些特性，若具备，则可以考虑使用动态规划方法来解决。​

二、动态规划解题步骤​

2.1 确定状态​

确定状态是动态规划解题的首要步骤，关键在于找到一个合适的变量或一组变量来描述问题在不同阶段的状态。通常可以从问题的输入参数入手，思考哪些参数的变化会影响问题的解。例如，在背包问题中，状态可以定义为 dp [i][j]，其中 i 表示考虑到第 i 个物品，j 表示背包当前剩余容量，dp [i][j] 表示在这种状态下背包能装下的最大价值。在定义状态时，要确保状态能够完整地描述问题的子结构，并且具有无后效性，即当前状态的决策不会影响到之前已经确定的状态。​

2.2 推导转移方程​

转移方程是动态规划的核心，它描述了不同状态之间的转换关系。推导转移方程需要深入分析问题的逻辑和状态之间的联系。以 0 - 1 背包问题为例，对于状态 dp [i][j]，考虑第 i 个物品时，有两种情况：若不放入第 i 个物品，则 dp [i][j] = dp [i - 1][j]；若放入第 i 个物品（前提是背包容量 j 大于等于第 i 个物品的重量），则 dp [i][j] = dp [i - 1][j - w [i]] + v [i]，其中 w [i] 是第 i 个物品的重量，v [i] 是第 i 个物品的价值。综合这两种情况，转移方程为 dp [i][j] = max (dp [i - 1][j], dp [i - 1][j - w [i]] + v [i])。推导转移方程时，要全面考虑所有可能影响状态转移的因素，确保方程的正确性和完整性。​

2.3 设定边界条件​

边界条件是动态规划算法中初始状态的值，它们是算法自底向上求解的基础。不同的问题边界条件各不相同。在斐波那契数列问题中，边界条件为 F (0) = 0，F (1) = 1，因为这是数列最基础的两项，从这两项开始可以通过状态转移方程计算出后续所有项的值。在背包问题中，当 i = 0（即没有物品可选择）或 j = 0（背包没有容量）时，dp [0][j] = 0，dp [i][0] = 0，表示没有物品可选或者背包没有容量时，能获得的最大价值为 0。准确设定边界条件对于确保算法的正确性至关重要，否则可能导致错误的结果或算法无法正常运行。​

2.4 计算顺序​

计算顺序决定了状态更新的先后顺序，它必须与状态转移方程的依赖关系相匹配。在大多数动态规划问题中，通常采用自底向上的计算顺序，即从小规模的子问题开始，逐步计算大规模的子问题。例如，在背包问题中，我们先计算只有一个物品时，不同背包容量下的最大价值（即 dp [1][j]），然后再依次增加物品数量，计算 dp [2][j]、dp [3][j] 等。在计算 dp [i][j] 时，由于其依赖于 dp [i - 1][j] 和 dp [i - 1][j - w [i]]，而这些值在之前的计算中已经得到，所以按照这种顺序计算能够保证每个状态在被使用时已经被正确计算出来。合理的计算顺序可以确保算法高效、正确地运行，避免出现错误的状态引用。​

三、动态规划高频题型解析​

3.1 背包问题​

1. 0 - 1 背包问题：这是最基本的背包问题类型。给定 n 个物品，每个物品有重量 w [i] 和价值 v [i]，以及一个容量为 C 的背包。每个物品只能选择放入背包一次或者不放入，目标是选择一些物品放入背包，使得背包内物品的总价值最大。状态定义为 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]。边界条件为 dp [0][j] = 0（没有物品可选时价值为 0），dp [i][0] = 0（背包容量为 0 时价值为 0）。计算顺序是外层循环遍历物品（从 1 到 n），内层循环遍历背包容量（从 C 到 w [i]，逆序遍历以避免重复选择同一物品）。​

1. 完全背包问题：与 0 - 1 背包问题的区别在于，每个物品可以无限次地放入背包。状态定义与 0 - 1 背包相同，但转移方程有所变化。当考虑放入第 i 个物品时，因为可以多次放入，所以 dp [i][j] = max (dp [i - 1][j], dp [i][j - w [i]] + v [i]) （当 j >= w [i] 时），否则 dp [i][j] = dp [i - 1][j]。这里 dp [i][j - w [i]] 表示在已经考虑了第 i 个物品多次放入的情况下，剩余容量为 j - w [i] 时的最大价值。计算顺序与 0 - 1 背包类似，但内层循环可以正序遍历，因为同一物品可以多次选择，正序遍历不会影响结果。​

1. 多重背包问题：每个物品有一定的数量限制 count [i]。一种朴素的解法是将每个物品拆分成 count [i] 个相同的物品，然后转化为 0 - 1 背包问题求解。但这种方法时间复杂度较高。更高效的方法是采用二进制优化，将每个物品拆分成若干组，每组代表一个二进制数，通过这种方式可以将时间复杂度从 O (nC∑count (i)) 优化到 O (nC∑log (count (i)))。状态定义和基本的计算逻辑与 0 - 1 背包有相似之处，但在处理物品数量限制时采用了不同的策略。​

3.2 最长子序列问题​

1. 最长递增子序列（LIS）：给定一个整数序列，找出其中最长的递增子序列的长度。例如，对于序列 [10, 9, 2, 5, 3, 7, 101, 18]，最长递增子序列是 [2, 3, 7, 101]，长度为 4。状态定义为 dp [i]，表示以第 i 个元素结尾的最长递增子序列的长度。转移方程为 dp [i] = max (dp [j]) + 1，其中 0 <= j < i 且 nums [j] < nums [i]，即遍历前面的元素 j，如果 nums [j] 小于 nums [i]，则更新 dp [i] 为 dp [j] + 1 中的最大值。边界条件为 dp [i] = 1（每个元素自身可以构成长度为 1 的递增子序列）。计算顺序是依次遍历序列中的每个元素，对于每个元素计算其对应的 dp 值。​

1. 最长公共子序列（LCS）：给定两个序列 X 和 Y，找出它们最长的公共子序列的长度。例如，对于序列 X = [1, 3, 4, 5, 6, 7, 7, 8] 和 Y = [3, 5, 7, 4, 8, 6, 7, 8, 2]，最长公共子序列是 [3, 5, 7, 8]，长度为 4。状态定义为 dp [i][j]，表示 X 的前 i 个元素和 Y 的前 j 个元素的最长公共子序列的长度。转移方程为：若 X [i - 1] == Y [j - 1]，则 dp [i][j] = dp [i - 1][j - 1] + 1；否则 dp [i][j] = max (dp [i - 1][j], dp [i][j - 1])。边界条件为 dp [0][j] = 0，dp [i][0] = 0（其中一个序列为空时，最长公共子序列长度为 0）。计算顺序是外层循环遍历序列 X 的长度，内层循环遍历序列 Y 的长度。​

3.3 路径问题​

1. 不同路径问题：在一个 m x n 的网格中，从左上角开始，每次只能向下或向右移动一步，求到达右下角的不同路径数量。状态定义为 dp [i][j]，表示从起点 (0, 0) 到位置 (i, j) 的不同路径数量。转移方程为 dp [i][j] = dp [i - 1][j] + dp [i][j - 1] （当 i > 0 且 j > 0 时），因为可以从上方或左方到达当前位置。边界条件为 dp [0][j] = 1（第一行只能从左边过来，路径数为 1），dp [i][0] = 1（第一列只能从上方过来，路径数为 1）。计算顺序是从左上角开始，逐行逐列地计算 dp 值，直到计算到右下角的 dp [m - 1][n - 1]。​

1. 最小路径和问题：同样在一个 m x n 的网格中，每个位置有一个非负整数表示经过该位置的代价，从左上角到右下角，每次只能向下或向右移动一步，求路径上的最小代价和。状态定义为 dp [i][j]，表示从起点 (0, 0) 到位置 (i, j) 的最小路径和。转移方程为 dp [i][j] = min (dp [i - 1][j], dp [i][j - 1]) + grid [i][j] （当 i > 0 且 j > 0 时），即选择从上方或左方过来的较小路径和，再加上当前位置的代价。边界条件为 dp [0][j] = dp [0][j - 1] + grid [0][j] （第一行只能从左边过来），dp [i][0] = dp [i - 1][0] + grid [i][0] （第一列只能从上方过来）。计算顺序与不同路径问题相同，从左上角开始按行按列计算，最终得到 dp [m - 1][n - 1] 即为最小路径和。​

四、实战案例分析​

4.1 题目描述与分析​

题目：给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。例如，对于数组 [-2, 1, -3, 4, -1, 2, 1, -5, 4]，连续子数组 [4, -1, 2, 1] 的和最大，为 6。分析：这是一个典型的动态规划问题，具有最优子结构和重叠子问题特性。我们可以通过定义合适的状态和转移方程来解决。​

4.2 解题思路与代码实现​

1. 状态定义：设 dp [i] 表示以 nums [i] 结尾的最大子数组和。​

1. 转移方程：dp [i] = max (dp [i - 1] + nums [i], nums [i])。这是因为对于以 nums [i] 结尾的子数组，要么将 nums [i] 加入到以 nums [i - 1] 结尾的最大子数组中（如果加入后和更大），要么重新开始一个新的子数组（即只包含 nums [i]）。​

1. 边界条件：dp [0] = nums [0]，因为以第一个元素结尾的最大子数组和就是第一个元素本身。​

1. 计算顺序：从左到右依次计算 dp [i]，最后遍历 dp 数组找到最大值即为结果。​

以下是 Python 代码实现：​

​

def maxSubArray(nums):​

n = len(nums)​

dp = [0] * n​

dp[0] = nums[0]​

for i in range(1, n):​

dp[i] = max(dp[i - 1] + nums[i], nums[i])​

return max(dp)​

​

4.3 复杂度分析​

时间复杂度：代码中有一个 for 循环遍历数组，时间复杂度为 O (n)，其中 n 是数组 nums 的长度。空间复杂度：使用了一个与数组长度相同的 dp 数组来存储中间结果，空间复杂度为 O (n)。但实际上，由于 dp [i] 只依赖于 dp [i - 1]，可以通过优化将空间复杂度降低到 O (1)，即只使用两个变量来存储当前状态和前一个状态的值。优化后的代码如下：​

​

def maxSubArray(nums):​

n = len(nums)​

pre = nums[0]​

max_sum = nums[0]​

for i in range(1, n):​

cur = max(pre + nums[i], nums[i])​

max_sum = max(max_sum, cur)​

pre = cur​

return max_sum​

​

优化后空间复杂度降为 O (1)，而时间复杂度保持 O (n) 不变。​

五、总结与提升​

5.1 动态规划解题要点回顾​

动态规划作为一种强大的算法策略，在解决复杂问题时具有独特的优势。在解题过程中，准确把握几个关键要点至关重要。首先，要精准地定义状态，状态的选择应能全面、简洁地描述问题的子结构，且具备无后效性，这是构建动态规划算法的基础。其次，推导状态转移方程是核心环节，需要深入分析问题的内在逻辑，找出不同状态之间的递推关系，确保方程的正确性和完整性。再者，合理设定边界条件为算法提供了初始值，是算法自底向上求解的起点，必须谨慎处理。最后，明确计算顺序，使其与状态转移方程的依赖关系相契合，保证每个状态在被使用时已被正确计算。​

5.2 应对面试的建议​

在算法面试中，动态规划题目出现频率较高，为了能够更好地应对：平时要进行大量的针对性练习，通过练习不同类型的动态规划题目，熟悉各种常见的题型和解题思路，培养对问题的敏感度，以便在面试中能快速识别问题的类型并找到解题方向。在练习过程中，注重总结归纳，将相似的题目进行分类，分析它们的共性和差异，提炼出通用的解题模板和技巧。同时，要理解每一步的原理，不仅仅是记住代码，这样才能在遇到变形题目时灵活应对。面试时，保持清晰的思路，先向面试官阐述自己