《动态规划应用举例》课件

动态规划应用举例•动态规划简介•动态规划的算法流程•动态规划应用举例-背包问题CATALOGUE•动态规划应用举例-最长公共子序列目录•动态规划应用举例-斐波那契数列•动态规划应用举例-树的最大/最小路径和问题01动态规划简介CHAPTER动态规划的定义动态规划是一种通过将问题分解为相互重叠的子问题，并存储子问题的解以避免重复计算，从而高效地解决优化问题的算法它是一种通过将原问题分解为相对简单的子问题，并从子问题的最优解逐步构造出原问题的最优解的方法动态规划的基本思想将问题分解为子问题，并存储子通过自底向上的方式求解子问题，通常采用递归方式实现，但递归问题的解，避免重复计算逐步构造出原问题的最优解可能导致大量的重复计算，因此需要使用备忘录或记忆化技术来存储已解决的子问题动态规划的适用场景最优化问题01动态规划适用于求解最优化问题，如最大值、最小值、最长路径等子问题重叠02动态规划适用于子问题重叠的情况，即子问题之间存在共享的状态或决策状态转移方程03动态规划适用于具有状态转移方程的问题，即当前状态依赖于前一状态和当前决策02动态规划的算法流程CHAPTER阶段划分将问题划分为若干个阶段，每个阶段都有自己的状态和决策阶段划分应使问题的求解过程清晰明了，便于分析和求解状态定义定义每个阶段的状态，状态应能够完全描述该阶段的问题状态应具有可转移性，即从一个状态转移到另一个状态是可能的状态转移方程根据问题的性质和阶段划分，建立状态转移方程状态转移方程描述了从一个状态转移到另一个状态的过程和条件优化子结构将问题分解为若干个子问题，每个子问题都有自己的最优解子问题的最优解应能够通过状态转移方程相互关联，以便求解整个问题的最优解最优解的递推关系根据状态转移方程和优化子结构，建立最优解的递推关系最优解的递推关系描述了如何从子问题的最优解逐步推导出整个问题的最优解03动态规划应用举例-背包问题CHAPTER问题描述01背包问题是一个经典的优化问题，其目标是在给定一定重量的背包和一组物品的情况下，选择合适的物品放入背包，使得背包中物品的总价值最大02物品可能有不同的重量和价值，每种物品的数量也是有限的03问题是如何选择物品，使得在不超过背包承重限制的前提下，所装物品的总价值最大状态定义与状态转移方程状态定义状态转移方程dp[i][j]表示在前i个物品中选，总重量不dp[i][j]=maxdp[i-1][j],dp[i-1][j-w[i]]超过j的条件下，能够获得的最大价值+v[i]，其中w[i]表示第i个物品的重量，VS v[i]表示第i个物品的价值最优解的递推关系最优解的递推关系基于状态转移方程，在计算过程中，需要保留已经计算过通过逐步计算dp数组的值，最终得的dp值，以便在计算后续状态时使用到最大价值VS算法实现算法实现主要包括初始化dp初始化dp数组时，需要为每填充dp数组时，需要按照状返回最大价值时，返回dp[n][W]的值，其中n是物品数组、填充dp数组和返回最个物品和重量组合设置一个初态转移方程逐步计算每个状态数量，W是背包承重限制大价值三个步骤始值，通常为0或负无穷大的值04动态规划应用举例-最长公共子序列CHAPTER问题描述给出两个序列A和B，找出两个序列的最长公共子序列最长公共子序列是指两个序列中同时出现的最长的子序列状态定义与状态转移方程定义状态dp[i][j]表示A的前i个字符和B的前j状态转移方程dp[i][j]=maxdp[i-1][j-个字符的最长公共子序列的长度1],dp[i][j-1],dp[i-1][j]+1最优解的递推关系•最优解的递推关系是如果A[i-1]等于B[j-1]，则dp[i][j]=dp[i-1][j-1]+1；否则dp[i][j]=maxdp[i][j-1],dp[i-1][j]+1算法实现初始化dp数组，dp

[0][j]=0，dp[i]

[0]=0，dp[i][j]=-1（如果A[i]和B[j]不相等）从i=1到m，j=1到n，根据状在dp数组中，最长公共子序列态转移方程更新dp数组的长度即为dp[m][n]，回溯dp数组找出最长公共子序列的具体字符05动态规划应用举例-斐波那契数列CHAPTER问题描述•斐波那契数列是一个经典的数列问题，其中每个数字是前两个数字的和给定一个正整数n，要求找出斐波那契数列的第n项状态定义与状态转移方程为了解决这个问题，我们可以使用动态规划来定义状态和状态转移方程假设01dp[i]表示斐波那契数列的第i项，则状态转移方程如下dp[i]=dp[i-1]+dp[i-2]02初始条件为dp

[0]=0，dp

[1]=103最优解的递推关系•通过状态转移方程，我们可以推导出最优解的递推关系由于dp[i]=dp[i-1]+dp[i-2]，我们可以发现dp[i]的值依赖于dp[i-1]和dp[i-2]因此，我们可以使用最优子结构的方法来递推求解算法实现•以下是使用Python实现的动态规划算法算法实现dp=[0,1]+

[0]*n-1#初始化状态数组03def fibonaccin02```python01算法实现for iin range2,n+1dp[i]=dp[i-1]+dp[i-2]#状态转移方程return dp[n]#返回第n项的值算法实现```这个算法的时间复杂度为On，空间复杂度也为On06动态规划应用举例-树的最大/最小路径和问题CHAPTER问题描述•树的最大/最小路径和问题是指给定一棵树，找出从根节点到叶子节点的最大/最小路径和这里的路径是指从根节点到叶子节点的所有节点连成的序列，路径和是指该路径上所有节点的值之和状态定义与状态转移方程•对于树中的每个节点，我们定义其状态为该节点到叶子节点的路径和对于根节点，其状态为该节点的值对于其他节点，其状态为其子节点的状态中的最大/最小值加上该节点的值状态转移方程为dp[i]=max/mindp[j]+v[i]，其中v[i]表示节点i的值，dp[j]表示节点j的状态，j表示节点i的子节点最优解的递推关系•最优解的递推关系为最优解=max/mindp[i]+v[i]，其中v[i]表示叶子节点的值，dp[i]表示叶子节点的状态算法实现

011.初始化对于每个节点，初始化其状态为其值

022.状态转移从根节点开始，递归地计算每个节点的状态，直到叶子节点

033.更新最优解在计算每个节点状态的同时，记录最大的/最小的路径和，并更新全局最优解

044.返回结果返回全局最优解THANKS感谢观看。