动态规划的第一个特征是问题可以被分解成相似的子问题，并且这些子问题会被多次求解。例如，在计算斐波那契数列时，F(n)=F(n-1)+F(n-2)，F(n-1)和F(n-2)会被多次计算。
动态规划的第二个特征是最优解包含了其子问题的最优解。如果一个问题的最优解可以从其子问题的最优解有效地构造出来，那么该问题就具备最优子结构特性。
无后效性有两层含义，第一层含义是，在推导后面阶段的状态的时候，我们只关心前面阶段的状态值，不关心这个状态是怎么一步一步推导出来的。第二层含义是，某阶段状态一旦确定，就不受之后阶段的决策影响。无后效性是一个非常“宽松”的要求。只要满足前面提到的动态规划问题模型，其实基本上都会满足无后效性。
动态规划广泛应用于各种问题，如：
使用表格来对比“动态规划算法”和“回溯算法”的异同及适用场景可以使信息更加清晰明了。以下是一个详细的对比表格：
尽管动态规划比回溯算法高效，但是，并不是所有问题，都可以用动态规划来解决。能用动态规划解决的问题，需要满足三个特征，最优子结构、无后效性和重复子问题。在重复子问题这一点上，动态规划和分治算法的区分非常明显。分治算法要求分割成的子问题，不能有重复子问题，而动态规划正好相反，动态规划之所以高效，就是因为回溯算法实现中存在大量的重复子问题。
贪心算法实际上是动态规划算法的一种特殊情况。它解决问题起来更加高效，代码实现也更加简洁。不过，它可以解决的问题也更加有限。它能解决的问题需要满足三个条件，最优子结构、无后效性和贪心选择性（这里我们不怎么强调重复子问题）。
其中，最优子结构、无后效性跟动态规划中的无异。“贪心选择性”的意思是，通过局部最优的选择，能产生全局的最优选择。每一个阶段，我们都选择当前看起来最优的决策，所有阶段的决策完成之后，最终由这些局部最优解构成全局最优解。
0-1背包问题是一个经典的动态规划问题。给定一个背包，最多能承载的重量为W，还有n个物品，每个物品有一个重量w[i]和价值v[i]。目标是在不超过背包最大承载重量的前提下，选择一部分物品放入背包，使得背包内物品的总价值最大化。每个物品只能选择放入或不放入背包。
动态规划通过将问题分解为更小的子问题，并通过记录每个子问题的结果来避免重复计算，从而有效地解决问题。
实现0-1背包问题，并记录选择的物品的代码：
拼写纠错是自然语言处理中的一个经典问题。给定一个错误的单词，目标是找到最接近的正确单词。常用的拼写纠错算法基于编辑距离（例如Levenshtein距离）来衡量两个单词的相似性。编辑距离是两个字符串之间的最小操作次数，这些操作包括插入、删除和替换字符。
为了实现拼写纠错功能，我们可以使用动态规划来计算输入单词与字典中每个单词的编辑距离，并选择编辑距离最小的单词作为纠正结果。
动态规划的思想是通过解决子问题并记录其结果来避免重复计算，从而有效地解决问题。对于最短路径问题，通常使用的动态规划方法是基于Bellman-Ford算法。
以下是使用Swift实现Bellman-Ford算法，并记录最短路径的代码，附有详细注释：
这个实现可以处理含有负权边的图，但不能处理负权回路。如果图中存在负权回路，算法会检测到并返回nil。