动态规划基本原理

动态规划的基本原理和基本应用动态规划（Dynamic Programming）是一种通过将一个问题分解为较小的子问题并存储子问题的解来解决复杂问题的方法。

动态规划的基本原理是通过记忆化或自底向上的迭代方式来求解问题，以减少不必要的重复计算。

它在计算机科学和数学中具有广泛的应用，尤其是在优化、组合数学和操作研究等领域。

1.确定最优子结构：将原问题分解为较小的子问题，并且子问题的最优解能够推导出原问题的最优解。

2.定义状态：确定存储子问题解的状态变量和状态方程。

3.确定边界条件：确定初始子问题的解，也称为边界状态。

4.递推计算：利用状态方程将子问题的解计算出来，并存储在状态变量中。

5.求解最优解：通过遍历状态变量找到最优解。

1.背包问题：背包问题是动态规划的经典应用之一、它有多种变体，其中最基本的是0/1背包问题，即在限定容量的背包中选择物品，使得所选物品的总价值最大。

可以使用动态规划的思想来解决背包问题，确定状态为背包容量和可选物品，递推计算每个状态下的最优解。

2. 最长递增子序列：最长递增子序列（Longest Increasing Subsequence）是一种常见的子序列问题。

给定一个序列，找到其中最长的递增子序列。

可以使用动态规划来解决这个问题，状态可以定义为以第i个元素为结尾的最长递增子序列的长度，并递推计算每个状态的解。

3.矩阵链乘法：矩阵链乘法是一种优化矩阵连乘计算的方法。

给定一系列矩阵，求解它们相乘的最小计算次数。

可以使用动态规划解决矩阵链乘法问题，状态可以定义为矩阵链的起始和结束位置，递推计算每个状态下最小计算次数。

4.最短路径问题：最短路径问题是在有向图或无向图中找到两个节点之间最短路径的问题。

可以使用动态规划解决最短路径问题，状态可以定义为起始节点到一些节点的最短距离，递推计算每个状态的最优解。

动态规划算法原理和实现动态规划是解决某些优化问题的一种算法思想，它主要针对的是那些可以分解成子问题的大问题，因此也被称作分治法。

动态规划算法的核心思想是将大问题分解成一个个小问题，然后逐步求解这些小问题并将它们组合成原问题的解。

本文将简单介绍动态规划算法的原理和实现。

一、动态规划算法的原理为了更好地理解动态规划算法的原理，我们可以以一个实例为例：假设有一个背包，它最多能装W重量的物品，现在有n种不同的物品，每种物品都有自己的重量w和价值v。

我们需要选择哪些物品放入背包中，以使得背包中物品的总价值最大。

这是一个典型的动态规划问题。

首先，我们可以把问题分解成子问题：设f(i,j)表示前i种物品放入一个容量为j的背包可以获得的最大价值。

因此，我们可以得到以下状态方程式：f(i,j) = max{f(i-1,j), f(i-1,j-w[i])+v[i]} （1≤i≤n,1≤j≤W）其中，f(i-1,j)表示不放第i种物品的最大价值，f(i-1,j-w[i])+v[i]表示放入第i种物品的最大价值。

因此，当我们计算出f(i,j)时，我们就得到了「前i种物品放入容量为j的背包的最大价值」，这也就是原问题的解。

这样，我们就可以使用动态规划算法来计算出最优解。

具体来说，我们从0开始，逐个计算出f(i,j)的值，直到计算出f(n,W)为止。

此外，我们还需要注意以下几点：1. 在计算f(i,j)的时候，我们需要使用到f(i-1,j)和f(i-1,j-w[i])这两个状态，因此我们需要先计算出f(1,j)，在此基础上计算f(2,j)，以此类推。

2. 对于一些特殊的情况，我们需要单独处理。

比如当背包容量小于某种物品重量时，我们就无法放入该物品。

3. 我们在计算f(i,j)时，有许多状态是可以复用的。

比如，当我们计算出f(i-1,j)后，我们就可以直接使用这个值来计算f(i,j)，而无需重新计算。

二、动态规划算法的实现上面我们已经介绍了动态规划算法的核心思想和实现原理，下面我们来看看具体的实现过程。

动态规划算法的详细原理及使用案例一、引言动态规划是一种求解最优化问题的算法，它具有广泛的应用领域，如机器学习、图像处理、自然语言处理等。

本文将详细介绍动态规划算法的原理，并提供一些使用案例，以帮助读者理解和应用这一算法的具体过程。

二、动态规划的基本原理动态规划算法通过将问题分解为多个子问题，并利用已解决子问题的解来求解更大规模的问题。

其核心思想是利用存储技术来避免重复计算，从而大大提高计算效率。

具体来说，动态规划算法通常包含以下步骤：1. 定义子问题：将原问题分解为若干个子问题，这些子问题具有相同的结构，但规模更小。

这种分解可以通过递归的方式进行。

2. 定义状态：确定每个子问题的独立变量，即问题的状态。

状态具有明确的定义和可计算的表达式。

3. 确定状态转移方程：根据子问题之间的关系，建立状态之间的转移方程。

这个方程可以是简单的递推关系式、递归方程或其他形式的方程。

4. 解决问题：使用递推或其他方法，根据状态转移方程求解每个子问题，直到获得最终解。

三、动态规划的使用案例1. 背包问题背包问题是动态规划算法的经典案例之一。

假设有一个背包，它能容纳一定重量的物品，每个物品有对应的价值。

目的是在不超过背包总重量的前提下，选取最有价值的物品装入背包。

这个问题可以通过动态规划算法来求解。

具体步骤如下：（1）定义问题：在不超过背包容量的限制下，选取物品使得总价值最大化。

（2）定义状态：令dp[i][j]表示将前i个物品放入容量为j的背包中所能获得的最大价值。

（3）状态转移方程：dp[i][j] = max(dp[i-1][j-w[i]]+v[i], dp[i-1][j])，其中w[i]为第i个物品的重量，v[i]为第i个物品的价值。

（4）解决问题：根据状态转移方程依次计算每个子问题的解，并记录最优解，直到获得最终答案。

2. 最长公共子序列最长公共子序列（Longest Common Subsequence，简称LCS）是一种经典的动态规划问题，它用于确定两个字符串中最长的共同子序列。

动态规划算法在路径规划中的应用路径规划在日常生活中随处可见，比如搜索最短路线、规划旅游路线、寻找交通路线等等。

其中，动态规划算法被广泛应用于路径规划领域，可解决诸如最短路径、最小花费路径等问题。

这篇文章将介绍动态规划算法在路径规划中的应用。

一、动态规划算法的基本原理动态规划算法是一种求解多阶段决策问题的优化方法。

它将问题分成多个子问题，并分别求解这些子问题的最优解。

最后通过不断合并子问题的最优解得到原问题的最优解。

其基本思想可以用以下三个步骤来概括：1.确定状态：将原问题分解成若干个子问题，每个子问题对应一个状态。

2.确定状态转移方程：确定每个状态之间的转移关系。

3.确定边界条件：确定初始状态和结束状态。

动态规划算法通常包括两种方法：自顶向下的记忆化搜索和自底向上的迭代法。

其中，自顶向下的记忆化搜索依赖于递归调用子问题的解，而自底向上的迭代法则通过维护状态表来解决问题。

二、动态规划算法在路径规划中的应用路径规划是动态规划算法的一个重要应用场景。

动态规划算法可以用来求解最短路径、最小花费路径、最大价值路径等问题。

这里以求解最短路径为例，介绍动态规划算法在路径规划中的应用。

1.问题定义假设我们需要从城市A走到城市B，中途经过若干个城市。

每个城市之间的距离已知，现在需要求出从城市A到城市B的最短路径。

这个问题可以用动态规划算法来求解。

2.状态定义在这个问题中，我们可以用一个二元组(u, v)表示从城市u到城市v的一条路径。

因此，在求解最短路径问题时，我们需要进行状态定义。

通常情况下，状态定义成一个包含一个或多个变量的元组，这些变量描述了在路径中的某个位置、某种状态和其他有关的信息。

在这个问题中，状态定义为S(i,j)，它表示从城市A到城市j的一条路径，该路径经过了城市集合{1, 2, …, i}。

3.状态转移方程状态转移方程描述了相邻状态之间的关系，即从一个状态到另一个状态的计算方法。

在求解最短路径问题时，状态转移方程可以定义为：d(i, j) = min{d(i-1, j), d(i, k) + w(k, j)}其中，d(i,j)表示从城市A到城市j经过城市集合{1, 2, …, i}的最短路径长度。

动态规划算法原理与的应用动态规划算法是一种用于求解最优化问题的常用算法。

它通过将原问题划分为子问题，并将每个子问题的解保存起来，以避免重复计算，从而降低了问题的时间复杂度。

动态规划算法的核心思想是自底向上地构建解，以达到求解整个问题的目的。

下面将介绍动态规划算法的原理以及一些常见的应用。

1.动态规划算法的原理1)将原问题划分为多个子问题。

2)确定状态转移方程，即找到子问题之间的关系，以便求解子问题。

3)解决子问题，并将每个子问题的解保存起来。

4)根据子问题的解，构建整个问题的解。

2.动态规划算法的应用2.1最长公共子序列1) 定义状态：假设dp[i][j]表示序列A的前i个字符和序列B的前j个字符的最长公共子序列的长度。

2) 确定状态转移方程：若A[i] == B[j]，则dp[i][j] = dp[i-1][j-1] + 1；若A[i] != B[j]，则dp[i][j] = max(dp[i-1][j],dp[i][j-1])。

3) 解决子问题：从前往后计算dp数组中每个元素的值。

4) 构建整个问题的解：dp[m][n]即为最终的最长公共子序列的长度，其中m和n分别为序列A和序列B的长度。

2.2背包问题背包问题是指给定一个背包的容量和一些物品的重量和价值，要求在不超过背包容量的情况下，选择若干物品放入背包中，使得背包中物品的总价值最大。

该问题可通过动态规划算法求解，具体步骤如下：1) 定义状态：假设dp[i][j]表示在前i个物品中选择若干物品放入容量为j的背包中，能够获得的最大价值。

2) 确定状态转移方程：考虑第i个物品，若将其放入背包，则dp[i][j] = dp[i-1][j-wi] + vi；若不将其放入背包，则dp[i][j] = dp[i-1][j]。

3) 解决子问题：从前往后计算dp数组中每个元素的值。

4) 构建整个问题的解：dp[n][C]即为最终的背包能够获得的最大价值，其中n为物品的个数，C为背包的容量。

动态规划的状态转移方程动态规划是一种常用的求解最优化问题的方法，广泛应用于计算机科学、数学和经济学等领域。

在动态规划中，状态转移方程是关键步骤，它描述了问题的状态如何从一个状态转移到下一个状态。

本文将详细介绍动态规划的状态转移方程及其应用。

一、动态规划的基本原理动态规划是一种将复杂问题分解成更小且重叠的子问题来求解的方法。

它的基本思想是利用已经计算过的子问题的解来求解当前问题的解，从而避免重复计算，提高计算效率。

二、状态转移方程的定义状态转移方程是动态规划中的重要概念，它描述了问题的状态如何从一个阶段转移到下一个阶段。

状态转移方程通常使用递推的方式来表示，即通过已知状态推导出未知状态。

在解决最优化问题时，我们通常需要定义一个目标函数，通过优化目标函数来求解最优解。

状态转移方程可以将目标函数从一个阶段递推到另一个阶段，从而求解出最优解。

三、状态转移方程的形式状态转移方程的形式可以根据具体问题的特点灵活定义。

一般来说，状态转移方程包括以下几个要素：1. 状态的定义：将问题划分为若干个阶段，并定义每个阶段的状态。

状态可以是一个变量、一个数组或其他数据结构。

2. 状态转移的定义：描述问题的状态如何从一个阶段转移到下一个阶段。

状态转移可以使用数学表达式、递归方程或其他形式表示。

3. 初始状态和边界条件：确定问题的起始状态和终止状态，并定义边界条件。

四、举例说明以经典的背包问题为例，我们来看一下如何使用状态转移方程解决问题。

背包问题是一个经典的组合优化问题，给定一个背包的容量和一组物品，每个物品有一个重量和一个价值，需要选择一些物品放入背包中，使得背包的总重量不超过容量，且总价值最大。

在解决背包问题时，我们可以将其划分为若干个阶段，每个阶段表示选择第i个物品放入背包的决策。

我们可以定义一个二维数组dp[i][j]来表示在前i个物品中，背包容量为j时的最大价值。

状态转移方程可以表示为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])其中，dp[i-1][j]表示不选择第i个物品时的最大价值，dp[i-1][j-w[i]] + v[i]表示选择第i个物品时的最大价值。

最优控制与最优化问题中的动态规划方法动态规划方法是一种在最优控制和最优化问题中常用的方法。

它通过将问题分解为子问题，并利用子问题的最优解来求解整体问题的最优解。

本文将介绍动态规划方法的基本原理和应用，以及其在最优控制和最优化问题中的具体应用案例。

一、动态规划方法的基本原理动态规划方法的基本原理是将原问题分解为若干个子问题，并通过求解子问题的最优解来求解整体问题的最优解。

具体来说，动态规划方法有以下几个基本步骤：1. 定义状态：将问题的解表示为一个或多个状态变量。

2. 确定状态转移方程：根据问题的特点和约束条件，确定状态之间的转移关系。

3. 确定边界条件：确定问题的边界条件，即最简单的情况下的解。

4. 递推求解：利用状态转移方程和边界条件，递推求解问题的最优解。

二、动态规划方法在最优控制中的应用动态规划方法在最优控制中有广泛的应用。

最优控制问题的目标是找到一种控制策略，使得系统在给定的约束条件下达到最优性能。

动态规划方法可以用来求解最优控制问题的控制策略。

以倒立摆控制为例，倒立摆是一种常见的控制系统，其目标是使摆杆保持竖直位置。

动态规划方法可以将倒立摆控制问题分解为一系列子问题，每个子问题都是在给定状态下选择最优的控制动作。

通过递推求解子问题的最优解，最终可以得到整个控制过程的最优策略。

三、动态规划方法在最优化问题中的应用动态规划方法在最优化问题中也有广泛的应用。

最优化问题的目标是找到一组变量的最优取值，使得目标函数达到最小或最大值。

动态规划方法可以用来求解最优化问题的最优解。

以旅行商问题为例，旅行商问题是一个经典的最优化问题，其目标是找到一条路径，使得旅行商能够经过所有城市并且总路程最短。

动态规划方法可以将旅行商问题分解为一系列子问题，每个子问题都是在给定状态下选择最优的下一个城市。

通过递推求解子问题的最优解，最终可以得到整个旅行路径的最优解。

四、动态规划方法的优缺点动态规划方法有以下几个优点：1. 可以求解复杂的最优控制和最优化问题，具有较高的求解效率。

动态规划的最优化原理有哪些内容
动态规划的最优化原理包括以下内容：
1. 最优子结构性质：如果一个问题的最优解包含了其子问题的最优解，则称该问题具有最优子结构性质。

简单来说，就是问题的最优解由子问题的最优解构成。

2. 重叠子问题性质：在求解一个动态规划问题时，需解决很多相同或相似的子问题。

为了避免重复计算，可以使用备忘录或者动态规划表来存储已经计算过的子问题的解，以便之后需要时直接查表获取。

3. 无后效性：即一个状态的值一旦确定，就不受之后决策的影响。

在动态规划的状态转移方程中，只关心当前状态和之前的状态，不关心状态之后的发展。

4. 状态转移方程：动态规划的核心就是确定状态转移方程。

通过分析问题的特点，找到问题当前状态和之前状态之间的关系，从而推导出状态转移方程，进而解决整个问题。

动态规划的最优化原理是动态规划算法能够高效解决问题的基础，通过把问题划分为子问题，求解并保存子问题的解，最终得到原问题的最优解。

动态规划算法详解及应用实例动态规划算法是一种常见的解决各种最优化问题的算法。

它适用于很多复杂的问题，如图形分析、路线规划、搜索引擎等等。

本文将详细讲解动态规划算法的基本原理、特点和应用实例，供大家学习和借鉴。

一、动态规划算法基本原理动态规划，简称DP，是一种递推式算法，通过将问题分解成一系列子问题，并按照一定的顺序对子问题进行求解，最终得到问题的最优解。

其主要思想是：当我们在解题时遇到一个问题时，如果能将这个问题划分成若干个与原问题相似但规模更小的子问题，而这些子问题又可以逐一求解，最终将所有子问题的结果汇总起来得到原问题的解，那么这个问题就可以使用动态规划算法解决。

由于动态规划算法中有“最优解”的要求，所以在求解过程中需要涉及到状态转移方程的设计。

状态转移方程是一个数学公式，它描述了一个状态如何从前一个状态转移而来，以及在当前状态下所做的某些决策对下一个状态的影响。

通过不断迭代求解状态转移方程，我们可以得到最优解。

二、动态规划算法的特点1、动态规划是一种自底向上的策略，通常需要维护一个状态表格，记录下每个阶段的最优解，最后汇总起来得到问题的最终解。

2、动态规划通常具有“无后效性”的特点，即求解某个决策问题时，当前状态之后的决策不会影响之前的决策。

因此，在涉及到状态转移时，只需考虑当前状态和以前的状态即可。

3、动态规划通常包含两个要素：最优子结构和重叠子问题。

最优子结构是指一个问题的最优解由其子问题的最优解递推而来，而重叠子问题则是指在递归求解的过程中，同一问题会被反复求解多次，因此需要使用记忆化搜索等技巧，避免重复计算。

4、动态规划算法的时间复杂度通常是O(n^2)或O(n^3)，空间复杂度通常也会比较高。

三、应用实例：0-1背包问题0-1背包问题是指在背包容量固定的情况下，如何选择物品才能使得背包装载的价值最大，其中每个物品只能选择一次。

对于此类问题，可以采用动态规划算法进行求解。

首先需要确定问题的状态转移方程，具体如下：设f(i,j)表示在前i个物品中，当背包的容量为j时，能够装载的最大价值，那么状态转移方程为：f(i,j)=max{f(i-1,j), f(i-1,j-wi)+vi}其中，wi表示第i个物品的重量，vi表示第i个物品的价值。

动态规划原理
动态规划是一种在数学、算法分析和组合优化中使用的有效技术，用于解决多步决策
问题，它把复杂的问题分解为若干个子问题，将已知条件依次应用于每个子问题，最终求
出最优的连续决策序列。

动态规划的核心思想就是将一系列具有特定结构的重叠子问题转换为个体子问题，然
后根据关于每个子问题的独立解决方案，求出一种最优解。

为了将问题简化，往往假设每
一步都只有一个状态，这种状态构成有限状态空间。

在空间状态下，能够求解问题最优解
的方式就是把状态转化为子问题，用最优子结构将这种重叠问题划分为之前的状态。

动态规划的过程是建立一个自顶向下的状态空间，由最优状态推导出其他的状态，从
而得到一组最优化决策序列。

在自底向上的过程中，我们可以按照最优化路径进行决策，
以实现最佳决策目标，这就是动态规划理论实施最优化结果的最终方向。

动态规划算法一般由三步组成：
状态定义：用一个数组来存储前一步的状态和本步状态，用它来确定本步之后最优解
的状态。

初始条件：设定初始状态，即确定最优解的起始状态。

转移方程：设定转移方程，用它来更新本步的状态，并据此更新最优解的状态。

在这三个步骤基础上，动态规划算法可以解决许多复杂问题，它可以帮助人们把大量
时间和空间复杂度消减到极小，使问题求解变得更简单。

其中最基础的应用包括赫夫曼树、矩阵连乘问题（Matrix–Chain Multiplication）、最长公共子序列等，动态规划算法的
广泛应用也是在网络路径、生物辨识、人脸识别、图像处理等多个领域中体现出来的。

Python中的动态规划解析动态规划是一种常用的算法思想，可以解决许多实际问题。

在Python中，动态规划的应用广泛，无论是求解最优解还是优化算法效率，都离不开动态规划的思想。

本文将对Python中的动态规划进行解析，并介绍其基本原理、常见应用和实现方法。

一、动态规划的基本原理动态规划（Dynamic Programming，简称DP）是一种通过拆分问题，定义问题状态和状态之间的关系，使得问题能够以递推（或递归）的方式去解决的算法思想。

它通常适用于有重叠子问题和最优子结构性质的问题。

具体来说，动态规划的基本原理可以概括为以下几步：1. 找到问题的最优子结构，即将原问题分解为若干个子问题；2. 定义问题状态，即确定需要存储的信息，以便用于子问题之间的转移；3. 确定状态转移方程，即问题状态之间的递推关系；4. 确定边界条件，即最小的子问题的解；5. 通过状态转移方程和边界条件，计算出原问题的解。

二、动态规划的应用动态规划在解决实际问题中有着广泛的应用。

以下是一些常见的动态规划问题及其解决方法：1. 斐波那契数列斐波那契数列是一个常见的动态规划问题，其定义如下：F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) （n ≥ 2）2. 背包问题背包问题是求解在有限的背包容量下，如何选择装入背包的物品，使得物品的价值最大化或重量最小化的问题。

常见的背包问题包括01背包问题、完全背包问题和多重背包问题。

3. 矩阵链乘法问题矩阵链乘法问题是求解如何在给定的一系列矩阵相乘的情况下，使得计算乘法的次数最少的问题。

4. 最长公共子序列问题最长公共子序列问题是求解两个序列中最长的公共子序列的问题，常见的解决方法是使用动态规划。

三、动态规划的实现方法在Python中，可以使用递归或迭代的方式来实现动态规划。

1. 基于递归的实现基于递归的实现方式通常会利用递归的性质来解决问题，但由于递归会导致重复计算，因此需要使用记忆化搜索（Memoization）来优化递归过程。

运筹学中的动态规划原理-教案一、引言1.1动态规划的基本概念1.1.1动态规划的定义：动态规划是一种数学方法，用于求解多阶段决策过程的最优化问题。

1.1.2动态规划的特点：将复杂问题分解为简单的子问题，通过求解子问题来得到原问题的最优解。

1.1.3动态规划的应用：广泛应用于资源分配、生产计划、库存控制等领域。

1.2动态规划的基本原理1.2.1最优性原理：一个最优策略的子策略也是最优的。

1.2.2无后效性：某阶段的状态一旦确定，就不受这个状态以后决策的影响。

1.2.3子问题的重叠性：动态规划将问题分解为子问题，子问题之间往往存在重叠。

1.3动态规划与静态规划的关系1.3.1静态规划：研究在某一特定时刻的最优决策。

1.3.2动态规划：研究在一系列时刻的最优决策。

1.3.3动态规划与静态规划的区别：动态规划考虑时间因素，将问题分解为多个阶段进行求解。

二、知识点讲解2.1动态规划的基本模型2.1.1阶段：将问题的求解过程划分为若干个相互联系的阶段。

2.1.2状态：描述某个阶段的问题情景。

2.1.3决策：在每个阶段，根据当前状态选择一个行动。

2.1.4状态转移方程：描述一个阶段的状态如何转移到下一个阶段的状态。

2.2动态规划的基本算法2.2.1递归算法：通过递归调用求解子问题。

2.2.2记忆化搜索：在递归算法的基础上，保存已经求解的子问题的结果，避免重复计算。

2.2.3动态规划算法：自底向上求解子问题，将子问题的解存储在表格中。

2.2.4动态规划算法的优化：通过状态压缩、滚动数组等技术，减少动态规划算法的空间复杂度。

2.3动态规划的经典问题2.3.1背包问题：给定一组物品，每种物品都有自己的重量和价值，求解在给定背包容量下，如何选择物品使得背包中物品的总价值最大。

2.3.2最长递增子序列问题：给定一个整数序列，求解序列的最长递增子序列的长度。

2.3.3最短路径问题：给定一个加权有向图，求解从源点到目标点的最短路径。

动态规划的基本原理和基本应用
一、动态规划的基本原理
动态规划（Dynamic Programming）是一种运用在运筹学中的一种数
学规划方法。

它的基本思路是：将一个复杂的求解问题分解成若干个更简
单的子问题，再从这些子问题出发，求出各子问题的解，回溯到原问题求
出原问题的解，通常情况下，动态规划的核心是对于每一个子问题只求解
一次，存储子问题的解，避免了重复求解子问题。

1.最优子结构性质：具有最优子结构性质的问题可以用动态规划求解，即如果一些问题的求解最优解由其子问题的最优解组合而成，那么该问题
也是最优的；
2.重复子问题性质：具有重复子问题性质的问题可以用动态规划求解，即一些问题的解可以由重复的子问题的解组合而成；
3.边界条件：求解动态规划的问题要求有边界条件，即知道求解问题
的初始和终止条件；
4.最优化原理：即求解问题的全局最优解可以由求子问题的最优解组
合而成，求解问题从最优解的最终状态开始，逐渐迭代至初始状态；
5.无后效性：即状态仅取决于其之前的几个状态，不受其之后状态的
影响。

二、动态规划的基本应用
1.适用于短路径问题：在交通运输、通信网络中。