本文系统讲解动态规划（DP）的核心原理，包括最优子结构、无后效性和重叠子问题。详细介绍了动态规划的解题步骤：定义状态、推导状态转移方程及设定边界条件。通过斐波那契数列、01 背包、完全背包及最长公共子序列等经典例题，提供了详细的 Python 代码实现与复杂度分析。最后探讨了资源分配、任务调度及金融投资等领域的应用场景，帮助读者掌握这一高效的最优化算法思想。
动态规划（Dynamic Programming，简称 DP），其核心思想并不复杂。简单来说，动态规划是一种将复杂问题分解成一系列相对简单的子问题，并通过求解子问题来得到原问题最优解的方法。
为了理解这一概念，我们可以举一个生活中的例子。假设你计划去旅游，有多个城市可供选择，每个城市之间的交通费用不同，你希望规划出一条从出发地到目的地且总费用最低的路线。这时候，动态规划就可以派上用场。
我们把整个旅程看作一个大问题，将其分解为多个阶段，每个阶段就是从一个城市到下一个城市的选择。比如，从城市 A 出发，你可以选择去城市 B、C 或 D，而从 B、C、D 又分别有不同的后续城市可以选择。我们可以通过计算每个阶段的最优选择，逐步构建出整个旅程的最优路线。
具体来说，在第一个阶段，你计算从 A 到 B、C、D 的费用，选择费用最低的路线作为当前的最优选择。到了第二个阶段，基于第一个阶段的最优选择，继续计算后续路线的费用，不断重复这个过程，直到到达目的地。在这个过程中，你会发现，有些子问题会被重复计算，比如从城市 B 到城市 E 的费用，在不同的路线选择中可能都会涉及到。动态规划的一个重要特点就是，它会记录已经计算过的子问题的解，当再次遇到相同的子问题时，直接使用之前的结果，而不是重新计算，这样就大大提高了计算效率。
简单总结一下，动态规划就是把一个大问题拆分成小问题，通过解决小问题，找到大问题的最优解，同时避免重复计算，节省时间和精力。
了解了动态规划的基本概念后，我们深入探讨一下它的核心原理，主要包括最优子结构、无后效性和重叠子问题这三个关键特性。
最优子结构是动态规划的一个重要特性，它指的是问题的最优解包含了子问题的最优解。简单来说，如果我们要求解一个大问题的最优解，那么可以通过求解它的子问题的最优解，然后将这些子问题的最优解组合起来，得到原问题的最优解。
以经典的背包问题为例，假设你有一个背包，它的容量为 5 千克，你有 3 个物品，分别是重量为 2 千克、价值为 3 元的物品 A，重量为 3 千克、价值为 4 元的物品 B，以及重量为 1 千克、价值为 2 元的物品 C。你需要在不超过背包容量的前提下，选择物品放入背包，使得背包中物品的总价值最大。
我们可以将这个问题分解为多个子问题。比如，先考虑只有物品 A 时，在背包容量为 1 千克、2 千克、3 千克、4 千克、5 千克的情况下，能获得的最大价值分别是多少；接着加入物品 B，计算在不同背包容量下，包含物品 A 和物品 B 时能获得的最大价值；最后加入物品 C，再次计算不同背包容量下的最大价值。
在这个过程中，我们发现，计算包含物品 A 和物品 B 时的最大价值，是基于只有物品 A 时的最大价值这个子问题的最优解。例如，当背包容量为 5 千克时，包含物品 A 和物品 B 的最大价值，可能是在只有物品 A 时，背包容量为 2 千克的最大价值（即放入物品 A，价值为 3 元），再加上物品 B 的价值（4 元），也可能是只有物品 A 时，背包容量为 5 千克的最大价值（即只放入物品 A，价值为 3 元），我们取这两者中的较大值，就是包含物品 A 和物品 B 时，背包容量为 5 千克的最大价值。这就是通过子问题的最优解来构建全局最优解的过程，体现了最优子结构的特性。
无后效性是动态规划的另一个关键特性。它是指某个状态的未来发展只取决于当前状态，而与它是如何到达当前状态的过去决策过程无关。也就是说，一旦当前状态确定，那么后续的决策和计算就只基于这个状态进行，不会受到之前决策的影响。
继续以上述背包问题为例，当我们确定了当前背包中已经放入了物品 A 和物品 B，背包剩余容量为 0 千克时，此时这个状态下的最大价值就是已经确定的，不会因为之前是先放入物品 A 还是先放入物品 B 而改变。后续如果还有新的物品要考虑放入，也是基于当前这个'背包中有物品 A 和物品 B，剩余容量为 0 千克'的状态来进行决策，而不会去考虑之前的放入顺序等历史信息。这就是无后效性的体现，它保证了我们在求解子问题时，可以按照一定的顺序进行，而不用担心之前的决策会对后续的计算产生干扰。
重叠子问题是动态规划能够提高效率的重要基础。它是指在求解问题的过程中，会出现一些相同的子问题被多次计算的情况。如果每次遇到这些子问题都重新计算，会浪费大量的时间和计算资源。动态规划通过记忆化存储的方式，将已经计算过的子问题的解保存下来，当再次遇到相同的子问题时，直接从存储中读取结果，而不需要重新计算，从而大大提高了算法的效率。
还是以背包问题来说，在计算不同背包容量和不同物品组合下的最大价值时，可能会多次遇到计算背包容量为 3 千克，包含物品 A 和物品 C 时的最大价值这个子问题。如果没有重叠子问题的概念，每次遇到都要重新计算一遍这个子问题，而利用动态规划，我们在第一次计算出这个子问题的解后，将其存储起来，后续再遇到同样的情况，直接读取存储的结果就可以了。这样，通过避免重复计算，大大加快了整个问题的求解速度。
了解了动态规划的核心原理后，我们来看看如何运用动态规划解决实际问题，一般来说，动态规划的解题步骤可以分为以下几步。
定义状态是动态规划解题的第一步，也是非常关键的一步。它的本质是找到一种合适的方式来描述问题的子问题，使得我们能够通过求解这些子问题，最终得到原问题的解。
在定义状态时，我们需要思考哪些信息能够完整地描述问题在某个阶段的情况，这些信息就是我们用来定义状态的变量。
以经典的斐波那契数列问题为例，斐波那契数列的定义是：(F(0)=0)，(F(1)=1)，(F(n)=F(n - 1)+F(n - 2))（(n\geq2)）。我们可以定义状态 (dp[i]) 表示第 (i) 个斐波那契数，这样就将求解整个斐波那契数列的问题，转化为求解每个 (dp[i]) 的子问题。
再比如背包问题，假设我们有一个容量为 (W) 的背包和 (n) 个物品，每个物品有重量 (w_i) 和价值 (v_i)。我们可以定义状态 (dp[i][j]) 表示在前 (i) 个物品中选择，背包容量为 (j) 时能获得的最大价值。这里的 (i) 和 (j) 就是状态变量，它们完整地描述了问题在某个阶段的情况，即考虑到第 (i) 个物品，背包容量为 (j) 时的最大价值。
状态转移方程是动态规划的核心，它描述了不同状态之间的关系，也就是如何从已知的状态推导出未知的状态。
推导状态转移方程的关键在于分析问题的最优子结构，找出当前状态与之前状态之间的联系。
继续以斐波那契数列为例，根据斐波那契数列的定义，我们很容易得到状态转移方程：(dp[i]=dp[i - 1]+dp[i - 2])。这个方程表示第 (i) 个斐波那契数等于第 (i - 1) 个斐波那契数和第 (i - 2) 个斐波那契数之和。
对于背包问题，状态转移方程的推导稍微复杂一些。对于状态 (dp[i][j])，我们有两种决策：一是不放入第 (i) 个物品，那么此时的最大价值就是 (dp[i - 1][j])，即在前 (i - 1) 个物品中选择，背包容量为 (j) 时的最大价值；二是放入第 (i) 个物品，前提是背包容量 (j) 大于等于第 (i) 个物品的重量 (w_i)，此时的最大价值是 (dp[i - 1][j - w_i]+v_i)，即在前 (i - 1) 个物品中选择，背包容量为 (j - w_i) 时的最大价值加上第 (i) 个物品的价值。所以，背包问题的状态转移方程为：(dp[i][j]=\max(dp[i - 1][j], dp[i - 1][j - w_i]+v_i))（当 (j\geq w_i) 时），当 (j\lt w_i) 时，(dp[i][j]=dp[i - 1][j])，表示由于背包容量不足，无法放入第 (i) 个物品，最大价值与前 (i - 1) 个物品时相同。
边界条件是动态规划算法正确运行的基础，它确定了问题的初始状态和一些特殊情况下的解。
在斐波那契数列中，边界条件就是 (dp[0]=0)，(dp[1]=1)。这两个值是斐波那契数列的初始值，也是我们后续推导其他值的基础。
对于背包问题，边界条件包括当 (i = 0) 时，即没有物品可选时，(dp[0][j]=0)，表示无论背包容量是多少，没有物品可选时，最大价值为 (0)；当 (j = 0) 时，即背包容量为 (0) 时，(dp[i][0]=0)，表示无论有多少物品，背包容量为 (0) 时，最大价值也为 (0)。
正确设定边界条件可以确保我们在使用状态转移方程进行递推时，有一个正确的起点，避免出现错误的结果。
斐波那契数列是一个非常经典的数学问题，也是动态规划的入门级案例。它的定义如下：(F(0)=0)，(F(1)=1)，(F(n)=F(n - 1)+F(n - 2))（(n\geq2\）。也就是说，从第三项开始，每一项都等于前两项之和。比如，斐波那契数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34...
我们用动态规划的方法来解决这个问题。
首先是定义状态，我们定义 (dp[i]) 表示第 (i) 个斐波那契数。
接着推导状态转移方程，根据斐波那契数列的定义，很容易得到状态转移方程为：(dp[i]=dp[i - 1]+dp[i - 2])。
然后设定边界条件，(dp[0]=0)，(dp[1]=1)。
下面是 Python 代码实现：
def fibonacci(n):
if n == 0:
return 0
if n == 1:
return 1
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
在这段代码中，我们首先处理了 (n) 为 0 和 1 的特殊情况，然后创建了一个长度为 (n+1) 的数组 (dp) 来存储斐波那契数。通过循环，从 2 开始，依次计算每个位置的斐波那契数，最后返回第 (n) 个斐波那契数。
这种方法的时间复杂度为 (O(n))，因为我们只需要遍历一次从 2 到 (n) 的数。空间复杂度也为 (O(n))，主要是用于存储 (dp) 数组。不过，我们可以进一步优化空间复杂度，因为在计算 (dp[i]) 时，只用到了 (dp[i - 1]) 和 (dp[i - 2])，所以可以只用两个变量来存储这两个值，从而将空间复杂度降低到 (O(1))。优化后的代码如下：
def fibonacci_optimized(n):
if n == 0:
return 0
if n == 1:
return 1
a, b = 0, 1
for i in range(2, n + 1):
a, b = b, a + b
return b
背包问题是动态规划中的经典问题，其中最常见的是 01 背包和完全背包问题。
01 背包问题的描述是：有 (n) 个物品，每个物品有重量 (w_i) 和价值 (v_i)，以及一个容量为 (W) 的背包。每个物品只能选择放入背包一次或者不放入，求在不超过背包容量的情况下，能装入背包的物品的最大价值。
我们用动态规划来解决这个问题。首先定义状态，设 (dp[i][j]) 表示在前 (i) 个物品中选择，背包容量为 (j) 时能获得的最大价值。
接着推导状态转移方程，对于第 (i) 个物品，我们有两种选择：不放入第 (i) 个物品，此时 (dp[i][j]=dp[i - 1][j])；放入第 (i) 个物品，前提是 (j\geq w_i)，此时 (dp[i][j]=dp[i - 1][j - w_i]+v_i)。所以状态转移方程为：(dp[i][j]=\max(dp[i - 1][j], dp[i - 1][j - w_i]+v_i))（当 (j\geq w_i) 时），当 (j\lt w_i) 时，(dp[i][j]=dp[i - 1][j])。
边界条件为：当 (i = 0) 时，即没有物品可选时，(dp[0][j]=0)；当 (j = 0) 时，即背包容量为 0 时，(dp[i][0]=0)。
下面是 Python 代码实现：
def knapsack_01(n, W, weights, values):
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, W + 1):
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][W]
在这段代码中，我们创建了一个二维数组 (dp)，并通过两层循环来填充这个数组。外层循环遍历物品，内层循环遍历背包容量。根据状态转移方程，计算每个状态下的最大价值，最后返回 (dp[n][W])，即在前 (n) 个物品中选择，背包容量为 (W) 时的最大价值。
该方法的时间复杂度为 (O(nW))，因为有两层循环，分别遍历物品和背包容量。空间复杂度也为 (O(nW))，主要是用于存储 (dp) 数组。实际上，我们可以通过滚动数组优化，将空间复杂度降低到 (O(W))。因为在计算 (dp[i][j]) 时，只用到了 (dp[i - 1][j]) 和 (dp[i - 1][j - w_i])，也就是只与上一行的数据有关，所以可以用滚动数组来优化。优化后的代码如下：
def knapsack_01_optimized(n, W, weights, values):
dp = [0 for _ in range(W + 1)]
for i in range(1, n + 1):
for j in range(W, weights[i - 1] - 1, -1):
dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1])
return dp[W]
在优化后的代码中，我们将 (dp) 数组改为一维数组。内层循环从 (W) 开始，倒序遍历到 (weights[i - 1])，这样可以保证在计算 (dp[j]) 时，(dp[j - weights[i - 1]]) 是上一轮的结果，从而实现滚动数组的效果。
完全背包问题与 01 背包问题类似，不同之处在于每个物品可以选择放入背包多次。
定义状态：设 (dp[i][j]) 表示在前 (i) 个物品中选择，背包容量为 (j) 时能获得的最大价值。
推导状态转移方程：对于第 (i) 个物品，我们可以选择放入 0 个、1 个、2 个…… 直到 (k) 个（(k) 满足 (k\times w_i\leq j)）。所以状态转移方程为：(dp[i][j]=\max(dp[i - 1][j - k\times w_i]+k\times v_i))，其中 (k = 0, 1, 2, \cdots)。不过，这个方程可以进一步优化，我们可以得到一个更简洁的状态转移方程：(dp[i][j]=\max(dp[i - 1][j], dp[i][j - w_i]+v_i))。这个方程的含义是，要么不放入第 (i) 个物品，价值为 (dp[i - 1][j])；要么放入至少一个第 (i) 个物品，价值为 (dp[i][j - w_i]+v_i)，取两者中的最大值。
边界条件与 01 背包问题相同：当 (i = 0) 时，(dp[0][j]=0)；当 (j = 0) 时，(dp[i][0]=0)。
下面是 Python 代码实现：
def knapsack_complete(n, W, weights, values):
dp = [[0 for _ in range(W + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, W + 1):
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][W]
同样，我们也可以对空间复杂度进行优化，将二维数组优化为一维数组。因为在完全背包问题中，每个物品可以无限次选择，所以内层循环需要正序遍历。优化后的代码如下：
def knapsack_complete_optimized(n, W, weights, values):
dp = [0 for _ in range(W + 1)]
for i in range(1, n + 1):
for j in range(weights[i - 1], W + 1):
dp[j] = max(dp[j], dp[j - weights[i - 1]] + values[i - 1])
return dp[W]
最长公共子序列（Longest Common Subsequence，简称 LCS）问题是指：给定两个序列，找出这两个序列中最长的公共子序列的长度。子序列是指在不改变序列中元素顺序的前提下，通过删除某些元素（也可以不删除）而得到的新序列。
例如，对于序列 (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]=Y[j])，那么 (dp[i][j]=dp[i - 1][j - 1]+1)；如果 (X[i]\neq Y[j])，那么 (dp[i][j]=\max(dp[i - 1][j], dp[i][j - 1]))。
边界条件：当 (i = 0) 或 (j = 0) 时，即其中一个序列为空时，(dp[i][j]=0)。
下面是 Python 代码实现：
def longest_common_subsequence(X, Y):
m, n = len(X), len(Y)
dp = [[0 for _ in range(n + 1)] for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if X[i - 1] == Y[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n]
在这段代码中，我们创建了一个二维数组 (dp)，并通过两层循环来填充这个数组。外层循环遍历序列 (X) 的元素，内层循环遍历序列 (Y) 的元素。根据状态转移方程，计算每个状态下的最长公共子序列长度，最后返回 (dp[m][n])，即序列 (X) 和序列 (Y) 的最长公共子序列长度。
该方法的时间复杂度为 (O(mn))，因为有两层循环，分别遍历两个序列的长度。空间复杂度也为 (O(mn))，主要是用于存储 (dp) 数组。实际上，我们可以通过滚动数组优化，将空间复杂度降低到 (O(\min(m, n)))。因为在计算 (dp[i][j]) 时，只用到了 (dp[i - 1][j]) 和 (dp[i - 1][j - 1])，也就是只与上一行的数据有关，所以可以用滚动数组来优化。优化后的代码如下：
def longest_common_subsequence_optimized(X, Y):
m, n = len(X), len(Y)
if m < n:
X, Y = Y, X
m, n = n, m
dp = [0 for _ in range(n + 1)]
for i in range(1, m + 1):
prev = 0
for j in range(1, n + 1):
temp = dp[j]
if X[i - 1] == Y[j - 1]:
dp[j] = prev + 1
else:
dp[j] = max(dp[j], dp[j - 1])
prev = temp
return dp[n]
在优化后的代码中，我们将 (dp) 数组改为一维数组。通过引入一个临时变量 (prev) 来保存 (dp[i - 1][j - 1]) 的值，从而实现滚动数组的效果。
动态规划作为一种强大的算法思想，在众多领域都有着广泛而深入的应用，它为解决各种复杂的实际问题提供了高效的解决方案。下面我们来看看它在一些常见领域中的精彩表现。
在资源分配问题中，动态规划可以帮助我们在有限的资源条件下，实现资源的最优分配，以达到最大的效益。比如，一家公司有一定数量的资金、人力等资源，需要分配到不同的项目中，每个项目在不同资源投入下会产生不同的收益。通过动态规划，我们可以定义状态为在不同资源量下分配到不同项目阶段的最大收益，状态转移方程则描述了如何从一个资源分配状态转移到下一个状态。通过求解这个动态规划问题，公司就能确定每个项目的最佳资源投入，从而实现总收益的最大化。在实际应用中，这种资源分配的场景还包括将原材料分配到不同的生产环节，将网络带宽分配给不同的用户或业务等。
任务调度是动态规划的另一个重要应用场景。在云计算、生产制造等环境中，常常需要对一系列任务进行调度，以满足特定的约束条件并优化某个目标，如最小化任务完成时间、最大化资源利用率等。以云计算中的任务调度为例，假设有多个虚拟机和多个任务，每个任务在不同虚拟机上的执行时间不同。我们可以将任务调度过程划分为多个阶段，每个阶段决定将哪个任务分配到哪个虚拟机上。通过定义状态为在某个阶段下，已分配任务的完成情况和资源使用情况，以及状态转移方程来描述任务分配的决策过程，利用动态规划算法可以找到最优的任务调度方案，提高云计算系统的整体性能和资源利用率。在生产制造中，也可以利用动态规划来安排生产任务在不同设备上的加工顺序，以减少生产周期和成本。
在金融投资领域，动态规划同样发挥着重要作用。投资者在进行投资决策时，需要考虑多个因素，如资产的价格波动、风险偏好、投资期限等，以实现投资收益的最大化。动态规划可以帮助投资者制定最优的投资策略。例如，在投资组合优化问题中，投资者需要在不同的资产类别（如股票、债券、基金等）之间分配资金。我们可以将投资过程按时间划分为多个阶段，每个阶段根据当前的资产价格、市场情况和投资组合的价值，决定是否调整资产配置。通过定义状态为在某个时间点的投资组合价值和资产配置情况，以及状态转移方程来描述投资决策对投资组合的影响，利用动态规划算法可以找到在不同风险偏好下的最优投资组合策略，帮助投资者在复杂的金融市场中做出更明智的决策。此外，动态规划还可以用于期权定价、风险管理等金融领域，为金融市场的稳定和发展提供有力支持。
动态规划作为一种强大的算法思想，通过将复杂问题分解为子问题，利用最优子结构、无后效性和重叠子问题的特性，高效地解决了众多最优化问题。从斐波那契数列到背包问题，再到最长公共子序列，我们看到了动态规划在不同场景下的应用和解题思路。
在实际运用动态规划时，关键在于准确地定义状态、推导状态转移方程以及设定边界条件。通过不断地练习和分析经典例题，我们能够逐渐掌握这种解题技巧，提高解决复杂问题的能力。同时，要注意动态规划算法的时间和空间复杂度，根据具体问题进行优化，如采用滚动数组等方法降低空间复杂度。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
暂无推荐文章，稍后可再来查看。
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
解析常见 curl 参数并生成 fetch、axios、PHP curl 或 Python requests 示例代码。 在线工具，curl 转代码在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML 转 Markdown 互为补充。 在线工具，Markdown 转 HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML 转 Markdown在线工具，online