《－动态规划》课件

动态规划概述动态规划是一种算法设计技术。它将复杂问题分解成更小的子问题。通过存储子问题的解，避免重复计算，提高效率。广泛应用于计算机科学、运筹学等领域。动态规划的基本思想分解问题将复杂问题分解为更小的子问题。解决子问题从最小的子问题开始，逐步解决。存储结果将子问题的解存储起来，避免重复计算。组合结果利用子问题的解，构建最终问题的解。动态规划的适用场景优化问题求解最优解，如最短路径、最大收益、最小成本等。组合问题从多个选项中选择最佳方案，如背包问题、硬币找零问题等。博弈问题分析博弈双方策略，找到最佳策略，如棋类游戏、拍卖等。图论问题解决图相关的最优路径问题，如最短路径问题、最小生成树问题等。动态规划的工作流程1定义问题明确问题目标和约束条件2构建状态确定状态表示，将问题分解为子问题3状态转移方程定义状态之间的关系，描述如何从子问题推导出最终解4边界条件确定递归终止条件，防止无限循环5计算结果自底向上或自顶向下计算最优解记忆化搜索避免重复计算记忆化搜索是一种结合了递归和动态规划思想的优化方法，通过保存已计算结果，避免重复计算。探索路径记忆化搜索如同登山，将已登顶的路线记录下来，下次只需沿着已知路线前进。树形结构记忆化搜索在本质上类似于对树形结构的遍历，通过记忆已访问的节点，避免重复搜索相同节点。动态规划的三大要素最优子结构问题可以分解为更小的子问题，子问题的最优解可以组合成原问题的最优解。这意味着可以递归地解决问题，将复杂的问题分解成更小的、更容易解决的问题。重叠子问题在求解过程中，会重复计算相同的子问题。动态规划通过存储子问题的解，避免重复计算，提高效率。这意味着可以将子问题的解存储在一个表中，以便在需要时快速访问。状态转移方程定义一个递归关系，描述如何从子问题的解推导出原问题的解。状态转移方程是动态规划的核心，它定义了如何从子问题得到最终解。每个子问题都对应一个状态，状态转移方程描述了状态之间的转换关系。最优子结构定义如果一个问题的最优解包含其子问题的最优解，则该问题具有最优子结构性质。例如，在求解最短路径问题时，最短路径一定包含其子路径的最短路径。重要性最优子结构是动态规划问题的关键特征之一，它确保了我们可以在子问题上进行递归求解，最终得到全局最优解。应用识别问题是否具有最优子结构是应用动态规划解决问题的首要步骤。重叠子问题子问题重复出现动态规划中，同一子问题可能被多次计算。计算效率低下重复计算会导致算法效率低下，尤其当子问题规模较大时。记忆化搜索动态规划通过存储已计算过的子问题结果，避免重复计算，提高效率。状态转移方程核心公式状态转移方程是动态规划的核心，它描述了不同状态之间的关系，并定义了如何从较小的子问题推导出较大的子问题。递归定义状态转移方程通常以递归的形式定义，它将当前状态的值与先前状态的值联系起来。递推关系动态规划算法通常利用状态转移方程来构建一个递推关系，并根据该关系逐步计算出最终结果。常见的动态规划问题11.斐波那契数列动态规划可用于计算任何位置的斐波那契数。22.最长公共子序列动态规划用于找到两个字符串的最长公共子序列。33.最长递增子序列动态规划用于找到给定序列的最长递增子序列。44.0-1背包问题动态规划用于确定从给定物品集合中选择的物品的最大价值，以满足容量约束。斐波那契数列定义斐波那契数列是一个数学数列，其中每个数字都是前两个数字的总和。递归公式斐波那契数列的递归公式为：F(n)=F(n-1)+F(n-2)，其中F(0)=0，F(1)=1。应用斐波那契数列在计算机科学、数学和自然科学中都有广泛的应用。最长公共子序列定义最长公共子序列(LongestCommonSubsequence,LCS)问题是指：给定两个字符串，找到这两个字符串中最长的公共子序列。举例例如，字符串"ACGT"和"AGGTAB"的最长公共子序列是"AGT"，长度为3。最长递增子序列子序列定义子序列是从原序列中选取任意个元素，保持顺序不变。递增子序列子序列元素按顺序递增，无需连续。最长子序列在所有递增子序列中，长度最长的子序列。0-1背包问题11.问题描述给定一个背包容量和一组物品，每个物品都有重量和价值，要求选择物品放入背包，使得背包内物品的总价值最大，且总重量不超过背包容量。22.关键限制每个物品只能选择一次，即要么完全装入背包，要么不装入背包，不能将物品分割。33.解决方法动态规划方法可以有效解决0-1背包问题，通过构建状态转移方程，遍历所有物品，并记录每个状态下的最大价值。44.应用场景0-1背包问题在资源分配、投资组合优化、货物运输等领域有着广泛的应用。硬币找零问题问题描述给定不同面值的硬币和一个总金额，求解最少需要多少枚硬币来凑成该总金额。动态规划解法使用动态规划，创建一个数组存储不同金额的最小硬币数量，通过状态转移方程计算每个金额所需的最小硬币数量。应用场景常见于自动售货机、银行找零等场景，需要根据不同的金额组合提供最优的硬币数量方案。编辑距离问题概念编辑距离是指两个字符串之间，通过插入、删除、替换操作，将一个字符串转化为另一个字符串所需要的最少操作次数。应用场景编辑距离广泛应用于自然语言处理、文本匹配、拼写检查、基因序列比对等领域。动态规划求解使用动态规划算法可以有效地计算两个字符串的编辑距离，其时间复杂度为O(m*n)，其中m和n分别为两个字符串的长度。最小路径和从左上角到右下角的最小路径和。每次只能向下或向右移动一步。动态规划解决此问题，记录每个位置到终点的最小路径和。状态转移方程：dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]股票买卖问题股票价格波动股票价格会在一段时间内不断变化。买入和卖出在合适的时间买入低价股票，并在价格上涨时卖出以获取利润。最大利润动态规划可用于找到股票买卖交易的最大利润。动态规划通过记录过去交易信息来优化未来交易决策。爬楼梯问题问题描述一个人想要爬上n级台阶。每次可以爬1级或2级台阶。问有多少种不同的爬楼梯方法？动态规划思路定义dp[i]表示爬到第i级台阶的方法数量。dp[i]可以由爬到第i-1级和第i-2级台阶的方案数累加得到。打家劫舍问题问题描述假设你是一个专业的小偷，计划偷窃沿街的房屋。每间房屋都存放着特定金额的现金。你不能偷窃相邻的房屋，因为它们有安全系统连接，会报警。动态规划解法使用动态规划，定义dp[i]表示偷窃前i间房屋的最大收益。状态转移方程dp[i]=max(dp[i-1],dp[i-2]+nums[i])，表示偷窃第i间房屋或不偷窃，两种情况的收益最大值。矩阵路径问题问题描述给定一个mxn的矩阵，每个单元格都有一个非负整数，从左上角开始，每次只能向下或向右移动一步，到达右下角的最小路径和是多少？动态规划解法定义dp[i][j]为从起点到(i,j)的最小路径和，状态转移方程为dp[i][j]=min(dp[i-1][j],dp[i][j-1])+grid[i][j]。边界条件dp[0][0]=grid[0][0]，dp[i][0]=dp[i-1][0]+grid[i][0]，dp[0][j]=dp[0][j-1]+grid[0][j]。时间复杂度O(m*n)，空间复杂度可以优化为O(n)，因为只需要保存上一行的数据。子集生成问题11.递归枚举使用递归算法遍历所有可能的子集组合。22.位运算利用位运算来表示子集的选取情况。33.回溯算法逐步构建子集，并在不符合条件时回退。44.迭代方法使用循环迭代来生成所有可能的子集。最长回文子串问题回文串回文串是指正着读和反着读都一样的字符串，例如"aba"、"racecar"。最长子串给定一个字符串，找到其中最长的回文子串。动态规划使用动态规划来记录每个子串是否为回文串，并逐步构建最长回文子串。最大子数组和问题描述给定一个整数数组，找到一个具有最大和的连续子数组（至少包含一个元素）。动态规划思路定义状态dp[i]表示以第i个元素结尾的最大子数组和，通过状态转移方程dp[i]=max(dp[i-1]+nums[i],nums[i])进行迭代计算。优化可以使用一个变量记录全局最大子数组和，并不断更新。时间复杂度为O(n)，空间复杂度为O(1)。硬币兑换问题11.问题描述给定一组面值的硬币，求解用这些硬币凑成目标金额的最小硬币数量。22.问题分析可以采用动态规划的思想，将问题分解成子问题，并使用状态转移方程来进行求解。33.状态定义定义状态dp[i]表示凑成金额i所需的最小硬币数量。44.状态转移对于每个金额i，遍历所有面值的硬币，选择能够凑成金额i的最少硬币数量。数字三角形问题问题描述给定一个数字三角形，求从顶点到最底层任意一点的路径总和最大值，每次只能向下走或向右走。例如，一个数字三角形如下：7388102744从顶点7出发，可以走7->3->8->7->4，路径总和为29，为最大值。动态规划解法使用二维数组dp[i][j]表示到达第i行第j列的路径总和最大值。dp[i][j]可以从dp[i-1][j]或dp[i-1][j-1]转移而来，状态转移方程为：dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+triangle[i][j]。最后，返回dp[n-1][0]到dp[n-1][n-1]中的最大值，即为从顶点到最底层任意一点的路径总和最大值。单词拆分问题动态规划思路将原字符串拆分成子串，判断子串是否在词典中。状态转移方程dp[i]表示字符串前i个字符能否拆分成词典中的单词。区域和检索-数组不可变数组前缀和计算数组前缀和，将数组元素累加。查询优化使用前缀和数组，可以高效地查询任意子数组的和。最小编辑距离定义编辑距离是指将一个字符串转换为另一个字符串所需的最小操作次数。操作允许的操作包括插入、删除和替换字符。应