🔥动态规划：从暴力递归到高效填表，一文搞懂最优解套路！

🔥为了更好的让大家理解算法这里推荐一个算法可视化的网站https://staying.fun/zh/features/algorithm-visualize

复制文章中JavaScript代码示例到这个网站上就可以看到可视化算法运算的过程了！大家快点来试试吧！！！！

一、动态规划的本质：用表格存储避免重复计算

动态规划（Dynamic Programming，DP）是一种通过把原问题分解为相对简单的子问题，并利用表格来避免重复计算的算法。它的核心思想是将问题划分为一系列相互关联的子问题，通过求解子问题并保存其结果，从而避免重复计算，提高求解效率。这种方法适用于具有最优子结构和重叠子问题的问题。💡 类比场景：做数学题时，把中间步骤的答案记在草稿纸上，避免重复计算。

最优子结构：如果一个问题的最优解可以由其子问题的最优解有效地构造出来，我们就称该问题具有最优子结构性质。例如，在计算从 A 地到 C 地的最短路径时，如果经过 B 地，那么从 A 到 B 和从 B 到 C 的路径也必须是各自的最短路径 。

重叠子问题：在求解问题的过程中，会出现子问题被多次重复计算的情况。例如，计算斐波那契数列时，F (n) = F (n - 1) + F (n - 2)，F (n - 1) 和 F (n - 2) 又会有重复的子问题计算。动态规划通过保存子问题的解，避免了重复计算，大大提高了效率 。

二、动态规划的实现关键点

2.1 状态定义

在动态规划中，状态定义是非常关键的一步。状态是指问题在某一阶段的特征，我们通常用一个数组（如dp数组）来表示状态。例如，在计算斐波那契数列时，dp[i]可以表示第i个斐波那契数 。而状态转移方程则描述了不同状态之间的关系，它是动态规划的核心。比如斐波那契数列的状态转移方程为dp[i] = dp[i - 1] + dp[i - 2] ，它表示第i个斐波那契数是前两个斐波那契数之和 。再比如在背包问题中，我们可以定义dp[i][j]表示在前i个物品中，背包容量为j时能获得的最大价值 。状态转移方程则根据是否选择第i个物品来确定：如果不选择第i个物品，dp[i][j] = dp[i - 1][j]；如果选择第i个物品，dp[i][j] = dp[i - 1][j - w[i]] + v[i] （其中w[i]是第i个物品的重量，v[i]是第i个物品的价值） 。

2.2 边界条件

边界条件是动态规划中不可或缺的一部分。它通常指的是初始状态或最小子问题的解，这些解需要我们手动定义。以斐波那契数列为例，边界条件为dp[0] = 0，dp[1] = 1 ，这是斐波那契数列的起始值，后续的数值都基于这两个初始值进行计算 。在其他问题中，边界条件也同样重要。比如在计算从起点到终点的路径数量时，如果起点和终点重合，那么路径数量为 1；如果起点或终点不可达，那么路径数量为 0 。正确设置边界条件可以确保动态规划算法的正确性和完整性。

2.3 填表顺序

填表顺序也是动态规划实现中的一个重要因素。通常，我们会按子问题规模从小到大的顺序填充表格，这样可以确保在计算当前状态时，依赖的子状态已经被计算完成。例如，在计算斐波那契数列的dp数组时，我们会从dp[2]开始计算，因为dp[2]依赖于dp[0]和dp[1]，而这两个值已经在边界条件中定义好了 。在背包问题中，我们会先遍历物品（即外层循环为物品索引i），再遍历背包容量（即内层循环为背包容量j），这样可以保证在计算dp[i][j]时，dp[i - 1][j]和dp[i - 1][j - w[i]]已经被计算出来 。合理的填表顺序可以提高算法的效率和正确性。

三、经典案例解析与代码实现

3.1 斐波那契数列：从递归到动态规划的优化

斐波那契数列是动态规划的经典入门案例，其定义为：F (0) = 0，F (1) = 1，F (n) = F (n - 1) + F (n - 2) （n >= 2，n∈N*） 。简单来说，从第三项开始，每一项都等于前两项之和 。比如数列：0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

递归实现：

function fibonacciRecursive(n) {

   if (n === 0) return 0; // 边界条件：第0项为0

   if (n === 1) return 1; // 边界条件：第1项为1

   return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); // 递归计算第n项

}

// 调用函数并打印结果

console.log(fibonacciRecursive(5));

递归实现虽然代码简洁，但其时间复杂度为 O (2^n) ，因为会有大量的重复计算。例如，计算 F (5) 时，F (3) 会被重复计算多次 。可以想象成一棵递归树，每个节点都要计算左右子节点，随着 n 的增大，计算量呈指数级增长 。

动态规划实现：

function fibonacciDP(n) {

   if (n === 0) return 0; // 边界条件：第0项为0

   if (n === 1) return 1; // 边界条件：第1项为1

   let dp = new Array(n + 1); // 创建一个数组来存储状态

   dp[0] = 0; // 初始化第0项

   dp[1] = 1; // 初始化第1项

   for (let i = 2; i <= n; i++) {

       dp[i] = dp[i - 1] + dp[i - 2]; // 根据状态转移方程计算第i项

   }

   return dp[n];

}

// 调用函数并打印结果

console.log(fibonacciDP(5));

动态规划通过数组dp来保存子问题的解，避免了重复计算，时间复杂度降低到 O (n) 。这里的dp数组就像是一个记忆小本本，把已经算过的结果记下来，下次直接用，不用再重新计算 。

优化空间复杂度：

function fibonacciOptimized(n) {

   if (n === 0) return 0; // 边界条件：第0项为0

   if (n === 1) return 1; // 边界条件：第1项为1

   let a = 0; // 记录前前一项

   let b = 1; // 记录前一项

   let result;

   for (let i = 2; i <= n; i++) {

       result = a + b; // 计算当前项

       a = b; // 更新前前一项

       b = result; // 更新前一项

   }

   return result;

}

// 调用函数并打印结果

console.log(fibonacciOptimized(5));

在计算斐波那契数列时，我们其实只需要前两项的结果，所以可以不用保存整个dp数组，只使用两个变量a和b来保存前两项，这样空间复杂度就优化到了 O (1) 。

3.2 爬楼梯问题：状态转移方程的应用

假设你正在爬楼梯，需要 n 步才能到达楼顶。每次你可以爬 1 或 2 个台阶。求有多少种不同的方法可以爬到楼顶 。这是一个典型的动态规划问题 。

思路分析：

爬到第 n 阶的方法数，等于爬到第 n - 1 阶的方法数加上爬到第 n - 2 阶的方法数 。因为可以从第 n - 1 阶再爬 1 步到达第 n 阶，也可以从第 n - 2 阶再爬 2 步到达第 n 阶 。

状态定义：

设dp[i]表示爬到第 i 阶的方法数 。

状态转移方程：

dp[i] = dp[i - 1] + dp[i - 2] 。

边界条件：

dp[1] = 1，表示只有 1 阶楼梯时，只有 1 种方法；dp[2] = 2，表示有 2 阶楼梯时，有 2 种方法（一次爬 2 阶或分两次每次爬 1 阶） 。

代码实现：

function climbStairs(n) {

   if (n === 1) return 1; // 边界条件：1阶楼梯只有1种方法

   if (n === 2) return 2; // 边界条件：2阶楼梯有2种方法

   let dp = new Array(n + 1); // 创建数组存储状态

   dp[1] = 1; // 初始化第1阶的方法数

   dp[2] = 2; // 初始化第2阶的方法数

   for (let i = 3; i <= n; i++) {

       dp[i] = dp[i - 1] + dp[i - 2]; // 根据状态转移方程计算第i阶的方法数

   }

   return dp[n];

}

// 调用函数并打印结果

console.log(climbStairs(5));

这段代码通过动态规划，利用状态转移方程计算出爬到第 n 阶的方法数 。时间复杂度为 O (n) ，空间复杂度也为 O (n) 。同样，我们也可以优化空间复杂度，只使用两个变量来保存前两阶的方法数，代码如下：

function climbStairsOptimized(n) {

   if (n === 1) return 1; // 边界条件：1阶楼梯只有1种方法

   if (n === 2) return 2; // 边界条件：2阶楼梯有2种方法

   let a = 1; // 记录前前一阶的方法数

   let b = 2; // 记录前一阶的方法数

   let result;

   for (let i = 3; i <= n; i++) {

       result = a + b; // 计算当前阶的方法数

       a = b; // 更新前前一阶的方法数

       b = result; // 更新前一阶的方法数

   }

   return result;

}

// 调用函数并打印结果

console.log(climbStairsOptimized(5));

优化后的代码空间复杂度降为 O (1) ，在实际应用中，如果 n 很大，这种优化可以显著减少内存占用 。

四、算法复杂度分析

时间复杂度：动态规划的时间复杂度通常取决于状态的数量以及计算每个状态所需的时间。一般来说，如果状态数为n，且计算每个状态的时间复杂度为O(k) ，那么总的时间复杂度就是O(n * k) 。以斐波那契数列的动态规划实现为例，状态数为n（即计算到第n个斐波那契数），而计算每个状态（即每个dp[i]）只需要O(1)的时间（简单的加法运算） ，所以时间复杂度为O(n) 。但在一些复杂问题中，如背包问题，状态数为物品数量n和背包容量m的乘积，计算每个状态时可能需要进行比较等操作，时间复杂度可能达到O(n * m) 。

空间复杂度：空间复杂度主要取决于存储状态所需的空间。在基本的动态规划实现中，通常需要一个数组（一维或多维）来存储所有状态，空间复杂度与状态数成正比。例如，在计算斐波那契数列时，使用长度为n + 1的数组dp来存储状态，空间复杂度为O(n) 。不过，很多时候可以通过优化来降低空间复杂度，比如滚动数组技术。在斐波那契数列的优化实现中，只使用了两个变量a和b来保存前两项，空间复杂度降为O(1) 。在背包问题中，也可以通过滚动数组将二维的dp数组优化为一维，空间复杂度从O(n * m)降低到O(m) 。

五、优化思路与技巧

5.1 空间优化：滚动数组

在动态规划中，很多时候当前状态只依赖于前面少数几个状态，而不是整个状态数组。这时可以使用滚动数组来优化空间复杂度 。以斐波那契数列为例，在计算第n项时，只需要前两项的结果，所以不需要保存整个dp数组，只使用两个变量来保存前两项即可 。这种方法就像是一个滚动的窗口，始终只关注当前需要的几个状态 。在背包问题中，如果状态转移方程为dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]) ，可以发现dp[i][j]只依赖于dp[i - 1][j]和dp[i - 1][j - w[i]] ，即只依赖于上一层的状态 。所以可以将二维的dp数组优化为一维数组，只保存上一层的状态，从而将空间复杂度从O(n * m)降低到O(m) （其中n是物品数量，m是背包容量） 。具体实现时，需要注意遍历背包容量时要从大到小遍历，以保证每个状态是基于上一层的状态计算的 。

5.2 剪枝优化

在计算过程中提前排除不可能成为最优解的分支：剪枝优化是指在计算过程中，提前判断并排除那些不可能成为最优解的分支，从而减少不必要的计算 。比如在解决旅行商问题（TSP）时，假设有一个旅行商需要访问多个城市，每个城市之间有不同的距离 。在搜索路径的过程中，如果当前已经走过的路径长度加上从当前城市到下一个城市的距离，已经超过了目前已知的最优解路径长度，那么就可以直接停止搜索这条路径 。因为即使继续搜索下去，这条路径也不可能成为最优解，这样就可以避免对这条路径后续的所有计算 。

例如：若当前路径已超过最优解，可提前终止：再比如在一个求从起点到终点的最短路径问题中，使用动态规划进行广度优先搜索 。假设当前已经找到了一条从起点到终点的路径，长度为minLength 。在继续搜索其他路径时，如果某条路径走到一半，其长度已经大于minLength ，那么就可以直接放弃这条路径的搜索，不再继续扩展它的后续节点 。通过这种剪枝操作，可以大大减少搜索的范围和计算量，提高算法的效率 。

六、常见问题与解决方案

在使用动态规划解决问题时，可能会遇到一些常见问题，以下是这些问题的解决方案：

问题场景	解决方案
状态定义不清晰	从子问题出发，明确状态的含义。比如在计算斐波那契数列时，明确dp[i]表示第i个斐波那契数；在背包问题中，定义dp[i][j]表示在前i个物品中，背包容量为j时能获得的最大价值 。
状态转移方程错误	画表格手动验证前几个状态的值，通过具体的例子来推导和验证状态转移方程。例如在爬楼梯问题中，手动计算前几个台阶的方法数，看是否符合状态转移方程dp[i] = dp[i - 1] + dp[i - 2] 。
空间溢出	使用滚动数组或压缩状态维度。如在斐波那契数列计算中，用两个变量代替数组来存储前两项；在背包问题中，将二维dp数组优化为一维数组 。

七、总结

动态规划是解决最优化问题的利器，通过状态定义、状态转移方程和边界条件的确定，能高效解决暴力递归无法处理的问题。掌握其核心思想后，可进一步探索最长公共子序列、股票买卖等进阶问题。快去试试把代码复制到编辑器，直观感受动态规划的填表过程吧！# 算法 #动态规划 #JavaScript #数据结构