动态规划与递归方法的基本思路

递归方法求解的基本思路-程序设计基础12_2_动态规划 在程序设计中，递归方法是一种常用的求解方法，但递归方法也存在一些问题，如重叠子问题等。为了解决这些问题，需要使用动态规划来优化递归方法。 **递归方法的基本思路** 递归方法的基本思路是将问题分解成更小的子问题，然后递归地解决这些子问题，最后将子问题的解组合起来得到原始问题的解。在递归方法中，每个子问题的解都需要计算多次，这将导致计算时间的增加。 **动态规划** 动态规划是一种优化递归方法的方法，它可以避免递归方法中的重叠子问题。动态规划的基本思路是将问题分解成更小的子问题，然后将每个子问题的解保存起来，最后将子问题的解组合起来得到原始问题的解。 **例子：数字三角形** 例如，数字三角形问题可以使用递归方法来解决。假设我们需要计算数字三角形的最大路径和，可以定义一个函数MaxSum(i, j)表示从第i行的第j个数字到底边的最佳路径上的数字之和。那么，我们可以使用递归方法来计算MaxSum(i, j)，即： * 如果走D(i+1, j)，那么得到的MaxSum(i, j)就是MaxSum(i+1, j) + D(i, j)； * 如果走D(i+1, j+1)，那么得到的MaxSum(i, j)就是MaxSum(i+1, j+1) + D(i, j)。 选择往哪里走，就看MaxSum(i+1, j)与MaxSum(i+1, j+1)哪一个更大。 **贪心法** 贪心法是动态规划的一种特殊情况，它是指在求解过程中，每一步都采用一种局部最优策略，逐渐缩小问题范围和规模，最后把每一步结果合并起来得到一个全局的最优解。贪心法的特点是，在求解过程中，每一步都可以选择当前的局部最优解，以便逐渐接近最优解。 **动态规划的特点** 动态规划的特点是： * 空间换时间：动态规划可以将计算时间换成空间，以避免重复计算。 * 不重复求解：动态规划可以避免递归方法中的重叠子问题。 **递归的重叠子问题** 递归的重叠子问题是指在递归调用中，计算某个值需要去计算相同的子问题，导致对同一个值计算了多次。为了避免这种情况，可以使用动态规划来保存每个子问题的解，以便下次使用时可以直接调用保存的值，而不是再计算一次。 递归方法是程序设计中的一种常用方法，但它也存在一些问题，如重叠子问题等。为了解决这些问题，需要使用动态规划来优化递归方法。动态规划可以避免递归方法中的重叠子问题，并且可以将计算时间换成空间，以提高计算效率。