动态规划第2课后半部分PPTX

动态规划是一种解决问题的方法，常用于优化复杂度较高的计算问题，通过将大问题分解为相互重叠的子问题来求解。在本课程中，我们主要探讨了动态规划在解决两个具体问题上的应用：钱币问题和砝码问题。 钱币问题涉及到如何用最少数量的钱币组成特定的金额。例如，如果拥有面值为1、2、3、4、5、6的钱币，我们需要找出可以构成的所有不同付款额以及它们对应的最小钱币数量。动态规划在此问题中的应用通常采用自底向上的方式，从最小的金额开始逐步增加，每次尝试所有可能的钱币组合，更新当前金额下的最小钱币数量。这个过程可以通过一维数组实现，数组的每个元素代表在该金额下所能达到的最小钱币数。在遍历过程中，我们可以从右往左更新数组，这样可以避免重复计算。 砝码问题则是一个经典的动态规划实例，其目标是找到最少数量的砝码来称量所有可能的重量。问题描述中提到的算法是这样的：初始化一个数组，其中的元素表示对应重量是否可以用砝码组合出来。当新增一个砝码时，我们遍历数组，如果某个重量的组合方案不为零，那么加上新砝码的重量后，这个新的重量组合也应该标记为可行。这里同样可以使用一维或二维数组来表示状态。对于一维数组，我们可以从右到左搜索，减少重复计算；而对于二维数组，可以直观地展示每个砝码对所有重量的影响。在处理过程中，我们需要注意避免无效的更新，比如新组合的方案比原来的更少，这种情况下不应更新。 接着，我们讨论了数塔问题，这是一个典型的自顶向下动态规划问题。数塔通常指的是从上至下移动数字，使得每一步操作都是将一个数字从顶层移动到底层，目标是最小化移动次数。在这个问题中，我们初始化一个二维数组，用于存储每个位置的最优解，即到达该位置所需的最小移动次数。从顶层开始，每次移动一个数字时，我们会比较将它放在左子塔、右子塔的最优解，然后选择较小的那个，更新当前位置的最优解。 提到了贪心策略与动态规划的结合。贪心策略是在每一步都做出局部最优的选择，期望整体结果也是最优的。但在某些问题中，单纯贪心可能无法得到全局最优解，这时就需要结合动态规划。以问题中的56为例，当i=0或j=0时，放上“0”作为边界条件。每次计算a[i][j]时，取max(dp[i-1][j-1], dp[i-1][j])的值加到dp[i][j]，这确保了我们始终考虑最优路径。 动态规划是一种强大的工具，能够有效地解决许多复杂问题，包括但不限于钱币问题、砝码问题、数塔问题等。通过理解并掌握这些基础实例，我们可以逐步提升解决实际问题的能力，并将动态规划的思维应用到更广泛的领域。